Simulator yang Melelahkan dari Protokol Pengetahuan Nol dalam Model Oracle Acak

Dalam makalah berjudul "On Deniability dalam Common Reference String dan Random Oracle Model," tulis Rafael Pass:

Kami mencatat bahwa ketika membuktikan keamanan sesuai dengan definisi nol-pengetahuan standar dalam model RO [Random Oracle], simulator memiliki dua keunggulan dibandingkan simulator model biasa, yaitu,

1. Simulator dapat melihat nilai-nilai apa yang diminta pihak oracle.
2. Simulator dapat menjawab pertanyaan ini dengan cara apa pun yang dipilih selama jawaban "terlihat" OK.

Teknik pertama, yaitu kemampuan untuk "memantau" permintaan untuk RO, sangat umum di semua makalah yang mengacu pada konsep nol-pengetahuan dalam model RO.

Sekarang, pertimbangkan definisi black-box zero-knowledge ( PPT singkatan dari probabilistik, mesin poluring-time Turing ):

simulator PPT S , sehingga ∀ (mungkin curang) verifier PPT V ∗ , ∀ input umum x ∈ L , dan ∀ keacakan r , yang berikut ini tidak dapat dibedakan:$\exists$$S$$\forall$$V^*$$\forall$$x\in L$$\forall$$r$

• pandangan saat berinteraksi dengan prover P pada input x dan menggunakan keacakan r ; $V^*$$P$$x$$r$
• output pada input x dan r , ketika S diberi akses kotak hitam ke V ∗ . $S$$x$$r$$S$$V^*$

Di sini, saya ingin menunjukkan pemverifikasi kecurangan , yang tugasnya adalah menguras semua simulator yang mencoba memantau permintaan RO:$V'$

Misalkan adalah simulator yang dijamin oleh penjumlahan eksistensial dalam definisi black-box zero-knowledge, dan misalkan q ( | x | ) menjadi polinomial yang membatasi waktu berjalan S pada input x . Asumsikan bahwa S mencoba untuk memantau permintaan V ∗ ke RO.$S$$q(|x|)$$S$$x$$S$$V^*$

Sekarang, pertimbangkan kecurangan , yang pertama kali menanyakan RO untuk q $V'$ kali (pada input sewenang-wenang dari pilihannya), dan kemudian bertindak sewenang-wenang jahat.$q(|x|)+1$

Jelas, knalpot simulator S . Cara sederhana untuk S adalah menolak perilaku jahat seperti itu, namun demikian, seorang pembeda dapat dengan mudah membedakan interaksi nyata dari yang disimulasikan. (Karena dalam interaksi nyata, prover P tidak bisa memantau V ' 'query s, dan dengan demikian tidak akan menolak didasarkan pada fakta bahwa V ' adalah query terlalu banyak.)$V'$$S$$S$$P$$V'$$V'$

Apa solusinya untuk masalah di atas?

Edit:

Sumber yang baik untuk mempelajari ZK dalam model RO adalah:

Martin Gagné, Studi tentang Random Oracle Model, Ph.D. Tesis, Universitas California, Davis , 2008, 109 halaman. Tersedia di ProQuest: http://gradworks.umi.com/33/36/3336254.html

Khususnya, ini memberikan definisi ZK kotak hitam dalam Model RO di bagian 3.3 (halaman 20), dikaitkan dengan Yung dan Zhao:

Moti Yung dan Yunlei Zhao. Interaktif Tanpa Pengetahuan dengan Oracle Acak Terbatas. Dalam Teori Kriptografi - TCC 2006 , LNCS 3876, hlm. 21-40, 2006.

Ada pertanyaan mengapa seseorang ingin mendefinisikan black-box ZK dalam model oracle acak. Setidaknya ada dua alasan mengapa orang menyarankan definisi pengetahuan nol kotak hitam:

1) Untuk hasil yang positif, ketika Anda mengatakan bahwa simulator adalah "black-box zero knowledge" itu secara otomatis memberi Anda batasan waktu berjalan yang baik (yaitu, sebagai lawan dari p o l y ( t i m e ( V ∗ ) ) ) dan juga mungkin berguna untuk mengetahui bahwa simulator tidak "melihat nyali V " dan tidak peduli jika V $poly(|x|) \cdot time(V*)$$poly(time(V*))$$V*$$V*$diimplementasikan menggunakan RAM, sirkuit, dll ... Sementara simulator model acak mungkin efisien, itu jelas bukan kotak hitam, karena itu seharusnya entah bagaimana melihat eksekusi dan mengerti darinya ketika V $V*$$V*$ mengevaluasi fungsi hash. Untuk alasan ini, ada perasaan di mana tidak masuk akal untuk mengatakan bahwa simulator model oracle acak adalah "kotak hitam".

2) Untuk hasil negatif, orang menggunakan "kotak hitam simulator" untuk menangkap kelas besar teknik bukti. Dalam hal ini Anda dapat mendefinisikan simulator kotak hitam juga dalam model oracle acak dan definisi yang masuk akal adalah apa yang dikatakan David. Bahkan, untuk hasil negatif bahkan tidak dalam model oracle acak, yang terbaik jika hasilnya berlaku bahkan jika Anda mengizinkan simulator waktu berjalan. Memang, meskipun tidak selalu dinyatakan, hasil negatif yang saya sadari semua memiliki properti ini, karena verifier kecurangan V $poly(time(V*))$$V*$ biasanya merupakan algoritma polinom tetap yang menjalankan beberapa fungsi pseudorandom, sedangkan simulator dapat memiliki waktu menjalankan polinomial apa pun.

Inilah pendapat saya tentang masalah ini. Saya belum pernah membaca makalah apa pun yang berhubungan dengan black-box zero-knowledge dalam model oracle acak (RO), jadi saya hanya menebak-nebak apa artinya dan bukan pada apa yang tertulis di sana. Jawaban singkatnya (tebak) adalah bahwa BB-ZK dalam model RO harus membiarkan simulator berjalan dalam polinomial waktu di | x | dan jumlah kueri RO yang dikeluarkan oleh V *, pemverifikasi kecurangan.

Mari kita coba benarkan tebakan itu. Pengamatan awal adalah bahwa istilah "bukti nol pengetahuan kotak hitam dalam model acak" membutuhkan pandangan yang lebih dekat untuk mendefinisikan dengan benar. Simulator kotak hitam didefinisikan untuk bekerja dengan oracle apa pun (yaitu, pengecek kecurangan sebagai kotak hitam), dan satu-satunya antarmuka mereka adalah melalui input / output oracle. Jika kita hanya menambah model ini untuk memberikan RO ke semua pihak (mungkin dengan membiarkan sirkuit mereka memiliki gerbang RO), maka kita mendapatkan model di mana simulator tidak dapat memprogram RO - pada permintaan oracle, semuanya (termasuk permintaan RO) hanya terjadi "di dalam" oracle V *, dan kemudian mengembalikan pesan berikutnya. Jika kita ingin mengizinkan pemrograman RO, maka kita perlu memodifikasi antarmuka: Simulator sekarang mendapat input / output oracle untuk V * dan tidak ada oracle acak. Pada setiap panggilan ke oracle V *, alih-alih menghasilkan pesan berikutnya, oracle malah dapat menghasilkan permintaan berikutnya untuk RO, dan simulator dapat memberikannya respons RO dengan memanggil oracle lagi. Sekarang ini memungkinkan pemrograman RO, dan kami juga dapat mengizinkan waktu berjalan simulator bergantung pada jumlah kueri ke RO.

Setiap eksplorasi lebih lanjut dari arti definisi-definisi ini diserahkan kepada pembaca. Saya berpikir secara sintaksis.