Intuisi ZKP: Gua Ali Baba

Bukti Pengetahuan Sifar (ZKP) membolehkan pembukti meyakinkan pengesah bahawa mereka mengetahui suatu rahsia (atau bahawa suatu pernyataan adalah benar) tanpa mendedahkan rahsia itu sendiri. Tiga sifatnya: Kesempurnaan, Keteguhan dan Pengetahuan Sifar.

Jika pembukti mengetahui rahsia itu, mereka sentiasa boleh meyakinkan pengesah. Pembukti jujur yang mengikuti protokol akan berjaya dengan kebarangkalian 1 (atau kebarangkalian yang amat tinggi). Pengesah tidak akan menolak bukti yang sah.

Pembukti yang menipu (yang tidak mengetahui rahsia) tidak boleh meyakinkan pengesah kecuali dengan kebarangkalian yang boleh diabaikan. Setiap pusingan interaksi mengurangkan kebarangkalian penipuan — selepas k pusingan: kebarangkalian kejayaan penipu ialah paling banyak 2^{-k}.

Pengesah tidak mempelajari apa-apa selain fakta bahawa pernyataan itu benar. Secara formal: wujud simulator yang, tanpa mengetahui rahsia, menghasilkan transkrip yang tidak dapat dibezakan daripada interaksi pembukti-pengesah sebenar. Pengesah memperoleh pengetahuan tambahan sifar.

Sebuah gua mempunyai laluan berbentuk gelang dengan pintu ajaib di tengah-tengahnya. Pembukti (Alice) mendakwa bahawa beliau mengetahui kata laluan. Pengesah (Bob) menunggu di luar. Alice masuk dan bergerak ke kiri atau kanan. Bob menjerit arah yang perlu digunakan untuk keluar. Jika Alice mengetahui kata laluan, beliau sentiasa keluar dengan betul. Kebarangkalian menipu bagi setiap pusingan: 1/2.

Selepas 20 pusingan, penipu berjaya dengan kebarangkalian 2^{-20} ≈ 1 dalam sejuta. Alice (yang mengetahui kata laluan) berjaya setiap kali. Bob tidak pernah mengetahui kata laluan — beliau hanya melihat Alice keluar dari arah yang diminta. Inilah pengetahuan sifar.

ZKP interaktif memerlukan komunikasi berbalas antara pembukti dan pengesah. ZKP Tidak Interaktif (NIZK) menggunakan transformasi Fiat-Shamir: menggantikan cabaran rawak pengesah dengan cincangan komitmen (cincangan = oracle rawak). Hasilnya ialah satu rentetan bukti yang boleh disahkan oleh sesiapa sahaja.

ZKP ialah Bukti Pengetahuan (PoK) jika strategi pembukti menunjukkan bahawa mereka boleh mengekstrak rahsia tersebut. Ini lebih kuat daripada sekadar membuktikan bahawa suatu pernyataan adalah benar. Tandatangan ECDSA dan Schnorr ialah bukti pengetahuan tidak interaktif tentang kunci peribadi.

Pengesahan kata laluan tanpa menghantar kata laluan. Pengesahan umur tanpa mendedahkan tarikh lahir. Bukti julat (gaji anda berada dalam suatu julat) tanpa mendedahkan gaji. Rantaian blok: buktikan bahawa anda mengetahui transaksi yang sah tanpa mendedahkan transaksi tersebut.

Pengetahuan sifar sempurna: output simulator adalah sama dengan transkrip sebenar. Pengetahuan sifar statistik: tidak dapat dibezakan kecuali dengan kebarangkalian yang boleh diabaikan. Pengetahuan sifar berpengiraan: tidak dapat dibezakan oleh pengesah dalam masa polinomial. Jaminan yang lebih lemah = bukti yang lebih cekap.

Gua ini menggunakan protokol 3 langkah: komit → cabaran → respons. Secara formal, ia dipanggil protokol Sigma. Kebanyakan ZKP praktikal (Schnorr, Pedersen, Fiat-Shamir) ialah protokol Sigma atau gabungan protokol tersebut. Namanya berasal daripada bentuk Σ dalam rajah aliran mesej.

ZKP membuktikan pengetahuan tentang rahsia tanpa mendedahkannya. Tiga sifatnya ialah kelengkapan, keteguhan dan pengetahuan sifar. Gua Ali Baba menggambarkan ZKP interaktif. Seterusnya: protokol Sigma dan pengenalpastian Schnorr.