Kriptografer Merancang Pendekatan untuk Privasi Pencarian Total | Majalah Kuanta

Kita semua tahu untuk berhati-hati dengan detail yang kita bagikan secara online, namun informasi yang kita cari juga bisa mengungkap banyak hal. Telusuri petunjuk arah mengemudi, dan lokasi kita menjadi jauh lebih mudah ditebak. Periksa kata sandi dalam kumpulan data yang telah disusupi, dan kita berisiko membocorkannya sendiri.

Situasi ini memicu pertanyaan kunci dalam kriptografi: Bagaimana Anda dapat mengambil informasi dari database publik tanpa mengungkapkan apa pun tentang apa yang telah Anda akses? Ini sama dengan memeriksa buku dari perpustakaan tanpa pustakawan mengetahui yang mana.

Merancang strategi yang memecahkan masalah ini – yang dikenal sebagai pengambilan informasi pribadi – adalah “sebuah landasan yang sangat berguna dalam sejumlah aplikasi yang menjaga privasi,” kata David Wu, seorang kriptografer di University of Texas, Austin. Sejak tahun 1990an, para peneliti telah menjawab pertanyaan tersebut dengan meningkatkan strategi untuk mengakses database secara pribadi. Salah satu tujuan utama, yang masih mustahil dilakukan dengan database besar, adalah setara dengan pencarian Google pribadi, di mana Anda dapat menyaring tumpukan data secara anonim tanpa melakukan pekerjaan komputasi yang berat.

Kini, sudah ada tiga peneliti dibuat versi pengambilan informasi pribadi yang telah lama dicari dan diperluas untuk membangun strategi privasi yang lebih umum. Karya yang mendapat a Penghargaan Kertas Terbaik pada bulan Juni di acara tahunan Simposium Teori Komputasi, meruntuhkan hambatan teoretis utama dalam perjalanan menuju penelusuran yang benar-benar pribadi.

“[Ini] sesuatu dalam kriptografi yang saya rasa kita semua inginkan tetapi tidak yakin bahwa hal itu ada,” katanya Vinod Vaikuntanathan, seorang kriptografer di Massachusetts Institute of Technology yang tidak terlibat dalam makalah ini. “Ini adalah hasil yang penting.”

Masalah akses database pribadi mulai terbentuk pada tahun 1990an. Pada awalnya, para peneliti berasumsi bahwa satu-satunya solusi adalah memindai seluruh database pada setiap pencarian, yang seperti meminta pustakawan menjelajahi setiap rak sebelum kembali membawa buku Anda. Lagi pula, jika pencarian melewatkan bagian mana pun, pustakawan akan mengetahui bahwa buku Anda tidak ada di bagian perpustakaan tersebut.

Pendekatan tersebut bekerja cukup baik pada skala yang lebih kecil, namun seiring dengan berkembangnya database, waktu yang diperlukan untuk memindainya bertambah setidaknya secara proporsional. Saat Anda membaca dari database yang lebih besar – dan internet merupakan basis data yang cukup besar – prosesnya menjadi sangat tidak efisien.

Pada awal tahun 2000-an, para peneliti mulai curiga bahwa mereka dapat menghindari hambatan pemindaian penuh dengan melakukan “pemrosesan awal” pada database. Secara kasar, ini berarti mengkodekan seluruh database sebagai struktur khusus, sehingga server dapat menjawab pertanyaan dengan membaca sebagian kecil dari struktur tersebut. Secara teori, pemrosesan awal yang cukup hati-hati dapat berarti bahwa satu server yang menghosting informasi hanya melalui proses tersebut satu kali saja, dan dengan sendirinya memungkinkan semua pengguna di masa mendatang untuk mengambil informasi secara pribadi tanpa perlu melakukan upaya apa pun lagi.

Untuk Daniel Wichs, seorang kriptografer di Universitas Northeastern dan salah satu penulis makalah baru, hal itu tampaknya terlalu bagus untuk menjadi kenyataan. Sekitar tahun 2011, ia mulai mencoba membuktikan bahwa skema semacam ini tidak mungkin dilakukan. “Saya yakin bahwa hal ini tidak mungkin dilakukan,” katanya.

Namun pada tahun 2017, dua kelompok peneliti diterbitkan hasil itu mengubah pikirannya. Mereka membangun program pertama yang dapat melakukan pengambilan informasi pribadi semacam ini, namun mereka tidak dapat menunjukkan bahwa program tersebut aman. (Kriptografer mendemonstrasikan keamanan sistem dengan menunjukkan bahwa memecahkannya sama sulitnya dengan menyelesaikan beberapa masalah sulit. Para peneliti tidak dapat membandingkannya dengan masalah sulit kanonik.)

Bahkan dengan harapannya yang diperbarui, Wichs berasumsi bahwa versi program apa pun yang aman masih jauh dari harapan. Sebaliknya, dia dan rekan penulisnya — Wei-Kai Lin, sekarang di Universitas Virginia, dan Ethan Mook, juga di Northeastern — mengerjakan masalah yang mereka anggap lebih mudah, yang melibatkan kasus di mana banyak server menghosting database.

Dalam metode yang mereka pelajari, informasi dalam database dapat diubah menjadi ekspresi matematika, yang dapat dievaluasi oleh server untuk mengekstrak informasi tersebut. Para penulis memperkirakan ada kemungkinan untuk membuat proses evaluasi tersebut menjadi lebih efisien. Mereka bermain-main dengan ide dari tahun 2011, ketika peneliti lain menemukan cara untuk mengevaluasi ekspresi tersebut dengan cepat dengan memprosesnya terlebih dahulu, membuat tabel nilai khusus dan ringkas yang memungkinkan Anda melewati langkah evaluasi normal.

Metode tersebut tidak menghasilkan perbaikan apa pun, dan kelompok tersebut hampir menyerah — sampai mereka bertanya-tanya apakah alat ini benar-benar dapat berfungsi dalam kasus server tunggal yang didambakan. Mereka melihat bahwa memilih polinomial dengan cukup hati-hati, dan satu server dapat memprosesnya terlebih dahulu berdasarkan hasil tahun 2011 — menghasilkan skema pencarian yang aman dan efisien yang telah direnungkan selama bertahun-tahun. Tiba-tiba, mereka berhasil memecahkan masalah yang lebih sulit.

Awalnya penulis tidak percaya. “Mari kita cari tahu apa yang salah dengan ini,” kenang Wichs sambil berpikir. “Kami terus mencoba mencari tahu di mana kerusakannya.”

Namun solusinya tetap bertahan: Mereka benar-benar menemukan cara yang aman untuk melakukan pra-proses database server tunggal sehingga siapa pun dapat mengambil informasi secara rahasia. “Ini benar-benar melampaui apa yang kami harapkan,” katanya Yuval Ishai, seorang kriptografer di Technion di Israel yang tidak terlibat dalam pekerjaan ini. Ini adalah akibat “kami bahkan tidak cukup berani untuk memintanya,” katanya.

Setelah membangun skema pencarian rahasia, penulis beralih ke tujuan dunia nyata yaitu pencarian internet pribadi, yang lebih rumit daripada mengambil sedikit informasi dari database, kata Wichs. Skema pencarian pribadi itu sendiri memungkinkan adanya versi pencarian pribadi seperti Google, tetapi ini sangat memakan banyak tenaga: Anda menjalankan sendiri algoritma Google dan secara diam-diam mengambil data dari internet bila diperlukan. Wichs mengatakan pencarian sebenarnya, di mana Anda mengirim permintaan dan duduk santai sementara server mengumpulkan hasilnya, sebenarnya merupakan target untuk pendekatan yang lebih luas yang dikenal sebagai enkripsi homomorfik, yang menyamarkan data sehingga orang lain dapat memanipulasinya tanpa mengetahui apa pun tentangnya. .

Strategi enkripsi homomorfik yang umum akan menemui hambatan yang sama seperti pengambilan informasi pribadi, yang berjalan lamban melalui seluruh konten internet untuk setiap pencarian. Namun dengan menggunakan metode pencarian pribadi sebagai perancah, penulis membangun skema baru yang menjalankan komputasi yang lebih mirip dengan program yang kita gunakan sehari-hari, menarik informasi secara diam-diam tanpa menyapu seluruh internet. Hal ini akan memberikan peningkatan efisiensi untuk pencarian internet dan program apa pun yang memerlukan akses cepat ke data.

Meskipun enkripsi homomorfik adalah perpanjangan yang berguna dari skema pencarian pribadi, kata Ishai, dia melihat pengambilan informasi pribadi sebagai masalah yang lebih mendasar. Solusi penulis adalah “blok bangunan ajaib”, dan strategi enkripsi homomorfik mereka adalah tindak lanjut yang alami.

Untuk saat ini, tidak ada skema yang secara praktis berguna: Pemrosesan awal saat ini sangat membantu, ketika ukuran database membengkak hingga tak terbatas. Namun penerapannya berarti penghematan tersebut tidak dapat terwujud, dan prosesnya akan menghabiskan terlalu banyak waktu dan ruang penyimpanan.

Untungnya, kata Vaikuntanathan, para kriptografer memiliki sejarah panjang dalam mengoptimalkan hasil yang pada awalnya tidak praktis. Jika upaya di masa depan dapat menyederhanakan pendekatan ini, dia yakin pencarian pribadi dari database raksasa mungkin dapat dijangkau. “Kami semua mengira kami terjebak di sana,” katanya. “Apa yang diberikan oleh hasil Daniel adalah harapan.”

Quanta sedang melakukan serangkaian survei untuk melayani audiens kami dengan lebih baik. Ambil milik kami survei pembaca ilmu komputer dan anda akan diikut sertakan untuk menang secara gratis Quanta dagangan.