Diminta oleh pertanyaan yang diajukan Greg Kuperberg kepada saya, saya ingin tahu apakah ada makalah yang mendefinisikan dan mempelajari kompleksitas kelas bahasa yang mengakui berbagai jenis bukti pengetahuan . Kelas-kelas seperti SZK dan NISZK sangat alami dari sudut pandang kompleksitas, bahkan jika kita lupa sepenuhnya tentang nol pengetahuan dan hanya mendefinisikan mereka dalam hal masalah janji mereka yang lengkap. Sebaliknya, tentang 'bukti pengetahuan' di Google, saya terkejut tidak menemukan makalah atau catatan kuliah yang membahas konsep yang indah ini dalam hal kelas kompleksitas.
Untuk memberikan beberapa contoh: apa yang bisa dikatakan tentang subkelas SZK∩MA∩coMA yang terdiri dari semua bahasa L yang menerima bukti nol-pengetahuan statistik untuk x∈L atau x∉L, yang juga merupakan bukti pengetahuan saksi yang membuktikan x ∈L atau x∉L? Tentu saja kelas ini berisi hal-hal seperti log diskrit, tetapi kami tidak dapat membuktikan bahwa itu berisi grafik isomorfisme tanpa menempatkan GI dalam koMA. Apakah kelas mencakup semua SZK∩MA∩coMA? Seseorang juga bisa bertanya: jika fungsi satu arah ada, maka apakah setiap bahasa L∈MA∩coMA mengakui bukti nol-pengetahuan komputasi, itu juga bukti pengetahuan saksi yang membuktikan x∈L atau x∉L? (Permintaan maaf saya jika salah satu atau keduanya memiliki jawaban yang sepele --- Saya hanya mencoba menggambarkan hal-hal yang dapat dilakukan seseorang tanya, begitu seseorang memutuskan untuk melihat PoK dalam istilah kompleksitas-teoretis.)
sumber
Jawaban:
Ini bukan jawaban yang sebenarnya; Saya hanya membagikan beberapa hasil (yang tidak sesuai dalam satu komentar).
Beberapa masalah terbuka (mungkin diselesaikan, tetapi tidak saya ketahui) mengenai aspek kompleksitas-teoretis dari PoK:
Berbagai langkah-langkah efisiensi untuk ZK PoKs dari hubungan tertentu dengan kompleksitas tertentu (misalnya, hubungan di AM):
Kompleksitas hubungan yang mengakui ZK PoK dengan keterbatasan tertentu, katakanlah kompleksitas putaran terbatas (Itoh dan Sakurai hanya mempertimbangkan putaran konstan ZK PoK). Contoh lain adalah ketika pepatah adalah waktu polinomial: Ia tidak dapat menggunakan reduksi ke 3-warna, karena ia tidak dapat menyelesaikan hubungan NP-lengkap. Semua masalah NP-selesai memiliki pengurangan Cook dari pencarian ke keputusan. Namun, menurut hasil Bellare-Goldwasser yang dikutip di atas, pengurangan seperti itu tidak harus ada untuk semua bahasa / hubungan NP.
Sebelum menyimpulkan, izinkan saya menyebutkan bahwa sebenarnya ada beberapa definisi untuk PoK, beberapa di antaranya dikutip di bawah ini:
1) Upaya awal: Feige, Fiat dan Shamir ( J. Cryptology, 1988 ), Tompa dan Woll ( FOCS 1987 ), dan Feige dan Shamir ( STOC 1990 ).
2) Standar de facto: Bellare dan Goldreich ( CRYPTO '92 ). Makalah ini mensurvei upaya awal dalam mendefinisikan PoK, mengamati kekurangannya, dan menyarankan definisi baru yang dapat dianggap sebagai "definisi" dari PoK. Definisi ini memiliki sifat kotak hitam (ekstraktor pengetahuan memiliki akses kotak hitam ke prover kecurangan).
3) PoKs Konservatif: Didefinisikan oleh Halevi dan Micali ( ePrint Archive: Report 1998/015 ), definisi ini menambah definisi sebelumnya untuk menjamin kelayakan yang tepat. Ini juga memberikan definisi untuk pengetahuan tentang sebuah prover tunggal, yang baik ketika menjawab pertanyaan "apa artinya mengatakan bahwa P mengetahui sesuatu?"
4) Argumen Pengetahuan dengan Ekstraksi Non Black-Box: Seperti disebutkan di atas, definisi standar PoK adalah black box, yang membuatnya tidak mungkin untuk memiliki bukti (atau argumen) pengetahuan nol yang dapat disetel ulang untuk bahasa non-sepele. Barak et al. ( FOCS 2001 ) memberikan definisi non-kotak hitam, yang didasarkan pada (tetapi berbeda dari) definisi Feige dan Shamir (STOC 1990) yang dikutip di atas.
sumber