Dalam bab 10 dari HAC (10.4.2) , kita melihat protokol identifikasi Feige-Fiat-Shamir yang terkenal berdasarkan pada bukti nol-pengetahuan menggunakan kesulitan (diduga) mengekstraksi modulo akar persegi modulo komposit yang sulit untuk faktor. Saya akan memberikan skema dengan kata-kata saya sendiri (dan mudah-mudahan bisa beres).
Mari kita mulai dengan skema yang lebih sederhana: misalkan menjadi Blum integer (jadi dan masing-masing dan adalah 3 mod 4) dengan ukuran yang cukup besar sehingga anjak piutang tidak bisa dilaksanakan. Karena adalah bilangan bulat Blum, setengah dari elemen memiliki simbol Jacobi +1 dan setengah lainnya memiliki -1. Untuk elemen +1, setengah dari elemen tersebut memiliki akar kuadrat, dan setiap elemen yang memiliki akar kuadrat memiliki empat, tepatnya satu elemen itu sendiri adalah kuadrat.
Sekarang Peggy memilih elemen acak dari dan menetapkan . Dia kemudian mengirim ke Victor. Berikutnya adalah protokol: Victor ingin memverifikasi bahwa Peggy tahu akar kuadrat dari dan Peggy ingin membuktikannya kepadanya tanpa membocorkan apa pun tentang luar fakta dia tahu .
- Peggy memilih acak di dan mengirim ke Victor.
- Victor melengkapi mengirim atau kembali ke Peggy.
- Peggy mengirimkan ke Victor.
Victor dapat memverifikasi bahwa Peggy telah mengirim jawaban yang benar dengan mengkuadratkan apa yang ia terima dan membandingkannya dengan hasil yang benar. Tentu saja, kami mengulangi interaksi ini untuk mengurangi kemungkinan bahwa Peggy hanyalah penebak keberuntungan. Protokol ini diklaim sebagai ZK; bukti dapat ditemukan di berbagai tempat (misalnya, catatan kuliah Boaz Barak ).
- Peggy memilih r acak di Z ∗ n dan mengirim r 2
Saya tidak dapat menemukan serangan yang mengekstrak apa pun dari Peggy jika dia menghilangkan tanda-tanda itu.