Bayangkan Anda memiliki pengetahuan yang berguna — mungkin resep rahasia, atau kunci sandi. Bisakah Anda membuktikan kepada seorang teman bahwa Anda memiliki pengetahuan itu, tanpa mengungkapkan apa pun tentangnya? Ilmuwan komputer membuktikan lebih dari 30 tahun yang lalu bahwa Anda bisa, jika Anda menggunakan apa yang disebut bukti tanpa pengetahuan.
Untuk cara sederhana untuk memahami ide ini, misalkan Anda ingin menunjukkan kepada teman Anda bahwa Anda tahu cara melewati labirin, tanpa membocorkan detail apa pun tentang jalannya. Anda cukup melintasi labirin dalam batas waktu, sementara teman Anda dilarang menonton. (Batas waktu diperlukan karena dengan waktu yang cukup, siapa pun pada akhirnya dapat menemukan jalan keluarnya melalui coba-coba.) Teman Anda akan tahu bahwa Anda dapat melakukannya, tetapi mereka tidak akan tahu caranya.
Bukti tanpa pengetahuan bermanfaat bagi kriptografer, yang bekerja dengan informasi rahasia, tetapi juga bagi peneliti kompleksitas komputasi, yang berurusan dengan klasifikasi kesulitan masalah yang berbeda. “Banyak kriptografi modern bergantung pada asumsi kompleksitas — dengan asumsi bahwa masalah tertentu sulit dipecahkan, jadi selalu ada beberapa hubungan antara dua dunia,” kata Claude Crepeau, seorang ilmuwan komputer di McGill University. “Tetapi bukti [ini] telah menciptakan seluruh dunia koneksi.”
Bukti tanpa pengetahuan termasuk dalam kategori yang dikenal sebagai bukti interaktif, jadi untuk mempelajari cara kerja yang pertama, akan membantu untuk memahami yang terakhir. Pertama dijelaskan dalam makalah tahun 1985 oleh para ilmuwan komputer Safi Goldwasser, Silvio Micali dan Charles Rackoff, bukti interaktif bekerja seperti interogasi: Melalui serangkaian pesan, satu pihak (pembukti) mencoba meyakinkan pihak lain (pemverifikasi) bahwa pernyataan yang diberikan adalah benar. Bukti interaktif harus memenuhi dua sifat. Pertama, pernyataan yang benar pada akhirnya akan selalu meyakinkan verifikator yang jujur. Kedua, jika pernyataan yang diberikan salah, tidak ada pembuktian — bahkan seseorang yang berpura-pura memiliki pengetahuan tertentu — dapat meyakinkan si pemeriksa, kecuali dengan probabilitas yang sangat kecil.
Bukti interaktif bersifat probabilistik. Prover dapat menjawab satu atau dua pertanyaan dengan benar hanya karena keberuntungan, sehingga dibutuhkan tantangan yang cukup banyak, yang semuanya harus benar oleh Prover, agar verifikator menjadi yakin bahwa Prover memang mengetahui bahwa pernyataan tersebut benar.
Ide interaksi ini muncul ketika Micali dan Goldwasser — saat itu mahasiswa pascasarjana di University of California, Berkeley — bingung melalui logistik bermain poker melalui jaringan. Bagaimana semua pemain dapat memverifikasi bahwa ketika salah satu dari mereka mendapatkan kartu dari dek virtual, hasilnya acak? Bukti interaktif bisa memimpin. Tapi kemudian, bagaimana pemain dapat memverifikasi bahwa seluruh protokol — set lengkap aturan — diikuti dengan benar, tanpa mengungkapkan tangan setiap pemain di sepanjang jalan?
Untuk mencapai tujuan ini, Micali dan Goldwasser menambahkan properti ketiga ke dua yang diperlukan untuk bukti interaktif: Bukti tidak boleh mengungkapkan apa pun tentang pengetahuan itu sendiri, hanya kebenaran pernyataan itu. “Ada gagasan melalui protokol, di mana Anda percaya bahwa [para pemain poker] tidak tahu apa-apa lebih dari apa yang seharusnya mereka ketahui,” kata Goldwasser.
Mari kita pertimbangkan contoh klasik. Alice ingin membuktikan kepada Bob bahwa grafik tertentu G — kumpulan unik dari simpul (titik) yang dihubungkan oleh tepi (garis) — memiliki “siklus Hamilton”. Ini berarti grafik memiliki jalur yang mengunjungi setiap titik tepat satu kali dan berakhir di titik yang sama dengan titik awalnya. Alice bisa melakukan ini hanya dengan menunjukkan kepada Bob jalan yang melakukan ini, tapi tentu saja dia juga tahu jalannya.
Inilah cara Alice dapat meyakinkan Bob bahwa dia tahu jalan seperti itu ada, tanpa menunjukkannya kepadanya. Pertama dia menggambar grafik baru, H, itu tidak terlihat seperti G tetapi serupa dalam cara yang penting: Ia memiliki jumlah simpul yang sama, terhubung dengan cara yang sama. (Jika G benar-benar memiliki siklus Hamilton, kesamaan ini berarti H akan juga.) Kemudian, setelah menutupi setiap tepi di H dengan selotip, dia mengunci H dalam sebuah kotak dan memberikan kotak itu kepada Bob. Ini mencegahnya untuk melihatnya secara langsung tetapi juga mencegahnya untuk mengubahnya. Kemudian Bob membuat pilihan: Entah dia bisa meminta Alice untuk menunjukkan itu H benar-benar mirip dengan G, atau dia dapat memintanya untuk menunjukkan kepadanya siklus Hamiltonian di H. Kedua permintaan itu seharusnya mudah bagi Alice, dengan asumsi bahwa H benar-benar cukup mirip dengan G, dan bahwa dia benar-benar tahu jalannya.
Tentu saja, bahkan jika Alice tidak tahu siklus Hamiltonian di G, dia bisa mencoba menipu Bob, baik dengan menggambar grafik yang tidak mirip dengan G, atau dengan mengirimkan grafik yang tidak diketahui jalurnya. Tetapi setelah mereka memainkan beberapa ronde, peluang Alice untuk menipu Bob setiap kali menjadi semakin kecil. Jika dia melakukan semuanya dengan benar, akhirnya Bob akan yakin bahwa Alice mengetahui siklus Hamilton dalam graf G, tanpa Bob pernah melihatnya.
Setelah makalah awal yang pertama kali menjelaskan bukti semacam itu, Micali dan dua matematikawan — Oded Goldreich dan Avi Wigderson — menemukan konsekuensi tak terduga dengan efek luas. Ini ada hubungannya dengan kategori utama masalah dengan tingkat kesulitan yang hampir sama, yang dikenal sebagai NP. Masalah-masalah ini sulit dipecahkan, tetapi solusinya mudah diverifikasi. Ketiga peneliti tersebut menemukan bahwa, jika enkripsi benar-benar aman adalah mungkin, maka solusi untuk setiap masalah di NP juga dapat dibuktikan dengan bukti tanpa pengetahuan. Penelitian ini membantu peneliti membayangkan varian dari bukti tanpa pengetahuan yang bahkan tidak memerlukan enkripsi aman; ini dikenal sebagai bukti interaktif multi-pembukti.
Dan pada tahun 1988, Micali dan yang lainnya menunjukkan bahwa jika seorang proofer dan verifier berbagi string pendek bit acak, tidak ada interaksi yang diperlukan. Ini secara teoritis berarti bahwa bukti tanpa pengetahuan tidak harus interaktif, yang berarti bahwa komunikasi terus-menerus antara dua pihak tidak diperlukan. Ini akan membuat mereka jauh lebih berguna bagi para peneliti, tetapi baru setelah pergantian abad ke-21 bukti-bukti semacam itu lepas landas.
“Pada akhir 2000-an, kami mulai melihat evolusi teknik yang efisien untuk membangun bukti tanpa pengetahuan,” kata Matius D. Hijau, seorang kriptografer di Universitas John Hopkins. “Kami sampai pada titik di mana kami menyadari, 'Tunggu sebentar, mungkin sebenarnya ada cara untuk menggunakan ini dalam latihan.'”
Sekarang seorang proofer dapat mengirim satu pesan ke verifier tanpa keduanya harus online, dan peneliti dapat membuat bukti yang sangat singkat yang dapat diverifikasi dengan cepat, bahkan untuk masalah yang sangat rumit. Ini telah menghasilkan beberapa kegunaan praktis, seperti kemampuan untuk memverifikasi blockchain dengan cepat setelah transaksi cryptocurrency sambil menyembunyikan detail transaksi. Dan pada tahun 2016, sekelompok fisikawan menunjukkan bagaimana bukti tanpa pengetahuan dapat membantu pelucutan senjata nuklir: Tanpa mengungkapkan rahasia apa pun tentang desain hulu ledak nuklirnya, sebuah negara sekarang dapat membuktikan kepada inspektur nuklir apakah hulu ledak itu aktif atau tidak aktif.
Baru-baru ini, kemajuan dalam komputasi kuantum telah memaksa Crepeau untuk menguji penelitian sebelumnya untuk memastikan protokol tanpa pengetahuan masih layak. Pada tahun 2021, dia membantu mendemonstrasikan bahwa bukti interaktif multi-pembukti tetap menjaga kerahasiaannya bahkan ketika komputer kuantum terlibat, tetapi mencapai tingkat keamanan yang sama membuat protokol menjadi jauh lebih lambat. Temuan itu merupakan kabar baik, katanya, tetapi kekhawatiran baru akan muncul seiring kemajuan teknologi.
“Setiap jenis komputasi yang mungkin kita lakukan di masa depan akan melibatkan komputer kuantum,” kata Crepeau. “Jadi sebagai kriptografer paranoid yang baik, setiap kali kami menilai keamanan suatu sistem, kami ingin memastikan bahwa sistem kami aman.”
Catatan editor: Shafi Goldwasser telah menerima dana dari Yayasan Simons, yang juga mendanai ini publikasi yang independen secara editorial. Keputusan pendanaan Yayasan Simons tidak berpengaruh pada liputan kami.
