Puncte:4

Groth16 simulează dovada zero-cunoștințe pentru declarația nevalidă

drapel mx

Proprietatea zero-cunoaștere a lui Groth16 (https://eprint.iacr.org/2016/260, pagina 8) argumentul non-interactiv zero-knowledge se bazează pe existența unui simulator $\text{Sim}$ generarea de dovezi „false” pentru afirmațiile valide $(\phi, w) \in R$ fara cunostinta martorului $w$ pentru declarație $\phi$.

Întrebarea mea este dacă pentru Groth16 există și un simulator $\text{Sim}'$ pentru a genera dovezi „false” pentru invalid declarații $\phi'$, pentru care nici un martor $w'$ cu $(\phi', w') \în R$ există. Formal, Groth16 satisface următoarea noțiune?

Cunoștințe false zero: Pentru toți $\lambda \in \mathbb{N}, (R, z) \gets \mathcal{R}(1^\lambda), (\phi, w) \in R$, toate $\phi'$, și toți adversarii $\mathcal{A}$: $Pr[(\sigma, \tau) \gets \text{Setup}(R); \pi \gets \text{Prove}(R, \sigma, \phi, w): \mathcal{A}(R, z, \sigma, \tau, \pi) = 1] = Pr[(\sigma, \tau) \gets \text{Setup}(R); \pi \gets \text{Sim}'(R, \tau, \phi'): \mathcal{A}(R, z, \sigma, \tau, \pi) = 1]$

Orice răspuns ar fi util, inclusiv o dovadă pentru o falsă cunoaștere zero a Groth16 sau a altor scheme, definiții ale noțiunilor similare, dar diferite sau un rezultat imposibil.

(Încerc să construiesc o dovadă de securitate în care generarea unor astfel de dovezi false pare necesară. Nu am văzut niciodată noțiunea de mai sus, dar mi se pare că $\text{Sim}'$ ar trebui să existe pentru unele scheme.)

Puncte:3
drapel cn

„Fake zero-knowledge” decurge întotdeauna din conjuncția a două proprietăți:

  • Cunoștințe standard zero: există un Simulator Sim care poate genera dovezi (care nu se pot distinge de dovezi oneste) pentru afirmații valide și

  • Apartenența la subset dur: există un algoritm de eșantionare pentru limbaj, iar declarațiile greșite eșantionate aleatoriu nu se pot distinge de afirmațiile adevărate eșantionate aleatoriu (există și variante ale noțiunii).

Combinarea celor de mai sus dă noțiunea „corectă” pentru „cunoștințe false zero”: eșantionarea unei afirmații adevărate și construirea unui NIZK cinstit, deoarece nu se poate distinge de eșantionarea unei declarații false și simularea unui NIZK pentru aceasta.

Nota 1

Noțiunea de fals zero-cunoștințe din întrebarea dvs. este diferită (nu face nicio referire la un algoritm de eșantionare pentru limbaj): spuneți că pentru orice afirmație adevărată $(\phi, w)$ și orice afirmatie falsa $\phi'$, NIZK cinstiți cu $(\phi,w)$ ar trebui să fie imposibil de distins de NIZK-urile simulate cu $\phi'$. Acesta este mult prea puternic și nu poate rezista niciodată. Motivul este că algoritmul de atac $\mathcal{A}$ poate avea $\phi, \phi'$ codificat în descrierea sa (deoarece proprietatea este pentru toți $\phi,\phi'$ și toți adversarii $\mathcal{A}$) și pot încerca pur și simplu algoritmul de verificare pe NIZK. Acum, din moment ce algoritmul de verificare ia $\phi$ (sau $\phi'$) ca intrare, adversarul va distinge întotdeauna cele două situații (dacă verificarea trece cu $\phi'$, era o dovadă falsă, altfel era o dovadă reală; rețineți că prin temeinicie, verificarea unei dovezi reale generate de un doveditor onest nu poate avea succes în ceea ce privește o declarație nevalidă $\phi'$, prin urmare atacul distinctiv pe care tocmai l-am descris funcționează cu o probabilitate covârșitoare).

Nota 2

Apartenența la subsetul dur este necesară pentru „cunoștințe false zero”: dacă nu este greu să distingem afirmațiile adevărate de afirmațiile greșite, nu putem formula nicio noțiune utilă și netrivială de cunoștințe false zero. Dar este valabil pentru majoritatea limbilor criptografice de interes - de obicei, suntem interesați să facem NIZK-uri pentru declarații pe care verificatorul nu le-a putut verifica de unul singur.

Anakin Charles avatar
drapel mx
Mulțumesc, înțeleg de ce noțiunea mea propusă este prea puternică. După cum spuneți „urmează întotdeauna”: există o referință care să arate că standard-zk + hard-subset-membership permite dovezi simulate ale declarațiilor false?
Geoffroy Couteau avatar
drapel cn
Nu-mi vine în minte o referință standard, este mai degrabă o observație directă a folclorului. Dacă scrieți definiția apartenenței hard subset și a cunoștințelor zero, atunci urmează imediat „cunoștințe false zero” prin aplicarea secvențială a ambelor: începeți cu o dovadă sinceră pe o afirmație adevărată, aplicați mai întâi cunoștințele zero pentru a înlocui probatorul cu un simulator, apoi aplicați apartenența la subsetul dur pentru a comuta în mod indistinguitor declarația adevărată la o declarație falsă (ceea ce se poate face în această etapă deoarece Sim nu are nevoie de martor).
Anakin Charles avatar
drapel mx
Văd. Da, o astfel de dovadă a jocului ar trebui să fie ușor de construit. Mulțumiri!

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.