Mengapa Feige-Fiat-Shamir bukan Nol Pengetahuan tanpa bit tanda?

12

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 n menjadi Blum integer (jadi n=pq dan masing-masing p dan q adalah 3 mod 4) dengan ukuran yang cukup besar sehingga anjak piutang tidak bisa dilaksanakan. Karena n adalah bilangan bulat Blum, setengah dari elemen Zn 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 s dari Zn dan menetapkan v=s2 . Dia kemudian mengirim v ke Victor. Berikutnya adalah protokol: Victor ingin memverifikasi bahwa Peggy tahu akar kuadrat dari v dan Peggy ingin membuktikannya kepadanya tanpa membocorkan apa pun tentang s luar fakta dia tahu s .

  1. Peggy memilih acak rdi Zn dan mengirim r2 ke Victor.
  2. Victor melengkapi mengirim b=0 atau b=1 kembali ke Peggy.
  3. Peggy mengirimkan rsb 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 ).

ks1skt1=±1,tk=±1v1=t1s12,,vk=tksk2vi

  1. Peggy memilih r acak di Z ∗ n dan mengirim r 2rZnr2
  2. kbi{0,1}
  3. rΠi=1ksibi

ti

Saya tidak dapat menemukan serangan yang mengekstrak apa pun dari Peggy jika dia menghilangkan tanda-tanda itu.

Fixee
sumber

Jawaban:

8

Protokol identifikasi Feige-Fiat-Shamir (FFS) adalah bukti pengetahuan (PoK), di mana pepatah (Peggy) membuktikan pengetahuannya akar kuadrat dari input yang diberikan ke verifikasi (Victor).

FFS ingin membedakan PoK dari bukti keanggotaan bahasa , di mana Peggy membuktikan bahwa input memiliki beberapa properti (lebih formal, input milik bahasa tertentu).

Jika kita tidak menggunakan tanda-tanda negatif, ada kemungkinan bahwa input tidak memiliki akar kuadrat. Sebagai contoh, angka 20 tidak memiliki akar kuadrat mod 21. Karena membedakan kuadrat dan non-kuadrat adalah masalah sulit yang terkenal , FFS menghindarinya dengan membiarkan input menjadi nilai tambah atau minus dari beberapa angka kuadrat. Dengan kata-kata mereka sendiri (sedikit berubah):

vivi +1modnsivi

Dengan input bukti pengetahuan nol yang tidak dibatasi , mereka berarti ZK PoK yang bukti keanggotaannya sepele; yaitu V dapat dengan sendirinya memutuskan bahwa input adalah plus atau minus dari beberapa kotak (dengan hanya memeriksa simbol Jacobi).

MS Dousti
sumber
Terima kasih atas jawabannya, tapi saya masih tidak mengikuti: tanpa tanda simbol Jacobi adalah +1. Dengan tanda-tandanya, simbol Jacobi adalah +1. Anda mengatakan di atas "jika kita tidak menggunakan tanda-tanda negatif, ada kemungkinan bahwa input tidak memiliki akar kuadrat." Bagaimana mungkin? Input untuk verifikasi adalah daftar kotak yang (dengan asumsi pepatah jujur) selalu memiliki akar kuadrat.
Fixee
Pertanyaan kedua: apakah Anda mengatakan bahwa tanda-tanda itu hanya ada sebagai bukti untuk dilewati? Atau apakah ada serangan aktual jika dihilangkan?
Fixee
@Fixee: Asumsikan prover curang yang memilih kunci publiknya ( ) tidak sesuai dengan protokol; katakan nilai acak yang simbol Jaccobi-nya +1. Verifikasi (miskin) tidak memiliki cara untuk mengatakan apakah memiliki akar kuadrat atau tidak. Satu-satunya cara adalah menjalankan protokol, dan mendapatkan bantuan dari prover. Yaitu, membuktikan pengetahuannya tentang , DAN memberikan bukti keanggotaan bahasa (yaitu milik QR bahasa residu kuadratik.) Untuk beberapa alasan, FFS suka memisahkan jenis bukti ini dari bukti "input tidak dibatasi". Saya melihat ini sebagai teknis belaka. vivisivi
MS Dousti