Bukti Goldreich et al. Bahwa tiga warna memiliki nol bukti pengetahuan menggunakan komitmen bit untuk seluruh pewarnaan grafik di setiap putaran [1] Jika grafik memiliki simpul dan tepi e , hash aman memiliki b bit, dan kami mencari probabilitas kesalahan p , total biaya komunikasi adalah
lebih dari putaran. Menggunakan secara bertahap mengungkapkan pohon Merkle, komunikasi total dapat dikurangi menjadi O ( b e log n log ( 1 / p ) ) pada biaya meningkatkan jumlah putaran untuk O ( log n ) .
Apakah mungkin melakukan lebih baik dari ini, baik dalam hal komunikasi total atau jumlah putaran?
Sunting : Terima kasih kepada Ricky Demer karena menunjukkan faktor yang hilang dari .
sumber
Pembaruan : Jawaban ini sudah usang oleh jawaban saya yang lain, dengan batasan polylogarithmic sepenuhnya dari referensi yang sesuai.
Setelah dipikir-pikir, tidak perlu mengungkapkan pohon Merkle secara bertahap, sehingga versi komunikasi yang lebih rendah tidak memerlukan putaran tambahan. Langkah-langkah komunikasi adalah
Di babak pertama, prover hanya mengirim nilai root, yang tidak memberikan informasi karena hash dengan nonce root. Pada ronde ketiga, tidak ada informasi yang disampaikan tentang simpul yang tidak diperluas dalam pohon biner, karena simpul seperti itu di hash dengan nonce pada simpul itu. Di sini saya mengasumsikan bahwa prover dan verifier keduanya terikat secara komputasi dan tidak dapat menghancurkan hash.
Sunting : Terima kasih kepada Ricky Demer karena menunjukkan faktor yang hilang dari ee
sumber
Ada lonjakan baru-baru ini dalam aktivitas dalam argumen tanpa pengetahuan interaktif non-interaktif singkat. Diketahui bagaimana misalnya membangun argumen NIZK untuk Circuit-SAT di mana panjang argumen adalah jumlah elemen grup yang sangat kecil (lihat Groth 2010, Lipmaa 2012, Gennaro, Gentry, dll, Eurocrypt 2013, dll). Berdasarkan pengurangan NP Anda kemudian dapat dengan jelas membangun argumen untuk 3-colorability dengan komunikasi yang sama.
Tentu saja ini adalah model yang berbeda dibandingkan dengan pertanyaan awal Anda - misalnya, dalam argumen tersebut, panjang CRS linear dalam ukuran sirkuit, dan dalam beberapa hal dapat dianggap sebagai bagian dari komunikasi (meskipun dapat digunakan kembali dalam banyak argumen berbeda).
sumber
(Ini tidak cocok dengan komentar.)
Saya pikir saya sekarang melihat bagaimana menunjukkan bahwa pengasinan Anda tidak serta merta memberikanH0
H0 H1 H0
H1 H0
|| H2
x z ((3⋅b)+6) y
m m=x||111...[b of them]...111||y||z ,
H2(m)=x||111...[b of them]...111||H1(m)||z
x r m x r m
H2(m)=x||111...[b of them]...111||H1(m)||x
m
H2(m)=
[b+3 bits whose values don't matter]||H1(m)||[3 bits whose values don't matter] .
pengetahuan nol yang jujur.
Salah satu memiliki
.
sumber