pertanyaan tentang makalah ZK bersamaan oleh Prabhakaran & Sahai

Bukti Pengetahuan Concurrent Zero bersamaan dengan Logarithmic Round-Complexity

Nomor halaman berasal dari kertas itu sendiri, dan bukan pdf.


Dari halaman 3,

"Sebuah sistem bukti interaktif dikatakan kotak hitam (komputasi) nol
pengetahuan jika ada polinomial mesin waktu oracle probabilistik sehingga untuk setiap waktu polinomial probabilistik verifier dan untuk semua , distribusi output yang dihasilkan oleh pada input secara komputasi tidak dapat dibedakan dari pandangan verifier pada akhir interaksi . "$S$
$V^*$$\:x \in L\:$
$S^{V^*}$$x$
$(P,V)(x)$

Saya berasumsi mereka berarti pada akhirnya, jika tidak, ini hanya mendefinisikan Jujur Verifier Computational Zero Knowledge.$\:\left(P,V^*\right)(x)\:$

Dari halaman 7,

"Jika simulator tidak dibatalkan sampai semua sesi selesai (atau
pemverifikasi berakhir), itu mengeluarkan tampilan pemverifikasi pada titik itu."

Dari paragraf ketiga di halaman 8,

"Jika penghitung kedalaman menunjukkan bahwa kita hanya satu tingkat di atas daun, maka
simulator harus menunggu dua pesan pembukaan berikutnya, yaitu, ia harus bergerak melalui
dua daun, dan kemudian kembali. Untuk ini simulator terus memodifikasi tampilan saat ini
dengan membiarkan prover (dimodifikasi) dan verifier berjalan, sampai dua pesan pembukaan tiba. "

Bagi saya sepertinya ini tidak berhasil, karena pesan pepatah
pada tahap itu hanyalah komitmen yang mengikat secara statistik.

Biarkan menjadi polinomial yang membatasi jumlah kueri oracle yang dibuat oleh ketika hanya meminta satu bukti. Misalkan skema komitmen yang mengikat secara statistik yang digunakan adalah sedemikian rupa sehingga mudah untuk menghitung predikat yang komitmennya memiliki probabilitas sekitar memuaskan (misalnya, komitmen Naor atau komitmen dari generator pseudo-random suntik ). Minta verifikasi kecurangan meminta hanya satu bukti dan kemudian berlaku seperti verifikasi jujur ​​kecuali bahwa, pada satu tingkat di atas daun, itu akan berakhir $\: p: \omega \to \omega \:$$S$$V^*$$\:$
$\: \frac1{2\cdot p(k)} \:$$\:$$V_1$
jika komitmen pepatah tidak memenuhi predikat. Probabilitas berhasil jelas sekitar , sedangkan oleh serikat terikat, tetapi oleh serikat terikat dan independensi simulator, probabilitas bahwa output pandangan berhasil tidak non-diabaikan lebih dari . Ini berarti bahwa untuk cukup besar , probabilitas berhasil akan lebih dari lebih besar dari $\;\;$$\:\left(P,V_1\right)(x)\:$$\: \frac1{2\cdot p(k)} \:$$\:$
$S^{V_1}$
$\: \frac1{4\cdot p(k)} \:$$\;\;$
$k$$\:\left(P,V_1\right)(x)\:$$\: \frac1{5\cdot p(k)} \:$
probabilitas memiliki untuk menghasilkan tampilan berikutnya. Itu berarti distribusi dari komputasi dibedakan dari distribusi .$S^{V_1}$$\;\;$
$S^{V_1}$$\:\left(P,V_1\right)(x)\:$

Apakah ini kesalahan di koran? Jika tidak, apa yang saya lewatkan? $\:$

Saya salah satu penulisnya. Seseorang menunjuk saya ke pertanyaan ini. Berdasarkan bacaan cepat, inilah upaya menjawab kekhawatiran Anda.

Apa yang mungkin tidak begitu jelas dari versi ini dari deskripsi simulator (ini adalah pertama kalinya saya menggambarkan sebuah simulator, dan memang itu membaca agak banyak seperti bahasa mesin) adalah bahwa tampilan keluaran oleh simulator, setelah semua mendorong dan meletuskan tumpukan, hanya sesuai dengan traversal through edge berlabel L1 dan R1. Jadi, bahkan jika verifikasi dibatalkan di tempat lain, itu hanya muncul, dan simulator berlanjut.

Saya akan merekomendasikan versi proses FOCS (atau versi yang sedikit diperluas yang tersedia dari beranda saya) daripada versi e-print ini. Dalam hal deskripsi dalam versi prosiding, output simulator sesuai dengan "utas utama" dari simulasi, dan tidak termasuk aborsi yang mungkin terjadi di blok lihat-depan. (Hanya melihat kertas: lihat Gambar 3 untuk ilustrasi.)

Semoga itu bisa membantu.

-Manoj