Versi asli dari cerita ini muncul di Quanta Magazine.
Kita semua tahu untuk berhati-hati tentang detail yang kita bagikan secara online, tetapi informasi yang kita cari juga bisa memberikan petunjuk. Cari petunjuk arah mengemudi, dan lokasi kita menjadi lebih mudah ditebak. Periksa kata sandi dalam sejumlah data yang terkompromi, dan kita berisiko mengungkapkannya sendiri.
Keadaan seperti ini memunculkan pertanyaan kunci dalam kriptografi: Bagaimana Anda dapat mengambil informasi dari basis data publik tanpa mengungkapkan apa pun tentang apa yang Anda akses? Ini setara dengan meminjam buku dari perpustakaan tanpa pustakawan mengetahui buku mana yang Anda ambil.
Menciptakan strategi yang memecahkan masalah ini, yang dikenal sebagai pencarian informasi pribadi, adalah “blok bangunan yang sangat berguna dalam sejumlah aplikasi yang menjaga privasi,” kata David Wu, seorang ahli kriptografi di University of Texas, Austin. Sejak tahun 1990-an, para peneliti telah melangkah maju dalam menjawab pertanyaan tersebut, meningkatkan strategi untuk mengakses basis data secara pribadi. Salah satu tujuan utama, yang masih tidak mungkin dilakukan dengan basis data besar, adalah setara dengan pencarian Google pribadi, di mana Anda dapat menyaring tumpukan data secara anonim tanpa melakukan penghitungan berat.
Sekarang, tiga peneliti telah menciptakan versi pencarian informasi pribadi yang lama dicari dan memperluasnya untuk membangun strategi privasi yang lebih umum. Karya tersebut, yang menerima Penghargaan Makalah Terbaik pada Juni 2023 di Simposium Tahunan Teori Komputasi, mengatasi hambatan teoritis utama dalam perjalanan menuju pencarian yang benar-benar pribadi.
“Ini adalah sesuatu dalam kriptografi yang saya kira kita semua inginkan tetapi tidak terlalu percaya bahwa itu ada,” kata Vinod Vaikuntanathan, seorang ahli kriptografi di Massachusetts Institute of Technology yang tidak terlibat dalam penelitian tersebut. “Ini adalah hasil terobosan.”
Masalah akses basis data pribadi terbentuk pada tahun 1990-an. Pada awalnya, para peneliti menganggap bahwa satu-satunya solusi adalah memindai seluruh basis data selama setiap pencarian, yang akan sama halnya dengan memiliki seorang pustakawan memeriksa setiap rak sebelum kembali dengan buku Anda. Lagipula, jika pencarian melewatkan bagian apa pun, pustakawan akan tahu bahwa buku Anda tidak ada di bagian perpustakaan tersebut.
Pendekatan tersebut cukup baik pada skala yang lebih kecil, tetapi seiring dengan pertumbuhan basis data, waktu yang diperlukan untuk memindainya tumbuh setidaknya sebanding. Saat Anda membaca dari basis data yang lebih besar – dan internet adalah salah satu yang cukup besar – proses tersebut menjadi sangat tidak efisien.
Pada awal tahun 2000-an, para peneliti mulai mencurigai bahwa mereka dapat menghindari hambatan pemindaian penuh dengan “pengolahan awal” basis data. Secara kasar, ini berarti mengkodekan seluruh basis data sebagai struktur khusus, sehingga server dapat menjawab permintaan dengan membaca hanya sebagian kecil dari struktur tersebut. Pengolahan awal yang cukup hati-hati bisa, dalam teori, berarti bahwa server tunggal yang menyimpan informasi hanya melewati proses ini sekali, sendirian, memungkinkan semua pengguna di masa depan untuk mengambil informasi secara pribadi tanpa usaha tambahan.
Bagi Daniel Wichs, seorang ahli kriptografi di Northeastern University dan salah satu penulis makalah baru ini, itu terlihat terlalu bagus untuk menjadi kenyataan. Sekitar tahun 2011, dia mulai mencoba membuktikan bahwa jenis skema ini tidak mungkin dilakukan. “Saya yakin bahwa tidak mungkin dilakukan,” katanya.