fundal
Următorul contraexemplu de zero-cunoștințe (ZK) este descris în lucrarea lui Canetti [Securitatea și alcătuirea protocoalelor criptografice: un tutorial, pagina 26] pentru a arăta că există un protocol care este sigur în modelul de sine stătător, dar nesigur în modelul UC:
Să presupunem că există un astfel de „sistem de puzzle” încât atât probatorul, cât și verificatorul pot genera în mod eficient puzzle-uri și
- Dovatorul poate rezolva eficient orice puzzle dat și
- Verificatorul nu poate (i) rezolva în mod eficient puzzle-uri sau (ii) distinge între o soluție validă sau una aleatorie invalidă pentru un anumit puzzle, chiar dacă puzzle-ul este generat de la sine.
Acum, având în vedere un protocol ZK $\pi$ pentru o relație NP $R$, putem construi un alt protocol $\pi'$ Unde
- Dovatorul și verificatorul fug $\pi$,
- Dovatorul trimite un puzzle aleatoriu $p$ către verificator,
- Verificatorul răspunde cu o soluție „pretinsă”. $s$ pentru $p$, plus un puzzle $p'$,
- Dacă $s$ este o solutie valabila pt $p$, dovatorul își dezvăluie martorul secret $w$ (în protocolul ZK $\pi$) către verificator. În caz contrar, probatorul trimite o soluție $s'$ pentru $p'$ către verificator.
Întrebările mele privind securitatea în modelul de sine stătător
După cum se susține în lucrarea lui Canetti, dacă $\pi$ este ZK în de sine stătătoare setare, atunci așa este $\pi'$. Pentru a vedea asta, presupun că $\pi$ realizați în siguranță funcționalitatea ZK $\mathcal{F}_{\textsf{zk}}^R: ((x, w), x) \rightarrow (\lambda, R(x, w))$ în cadrul de sine stătător și încearcă să arăți asta $\pi'$ de asemenea realizează în siguranță $\mathcal{F}_{\textsf{zk}}^R: ((x, w), x) \rightarrow (\lambda, R(x, w))$. În special, dacă verificatorul este rău intenționat în $\pi'$, pot construi următorul simulator $\mathcal{S}_V$ acea intern conduce adversarul din lumea reală $\mathcal{A}$:
- $\mathcal{S}_V$ invocă simulatorul pentru $\pi$ pentru a genera $\pi$-parte transcrieri între doveditorul cinstit și verificatorul rău intenționat (sau echivalent, putem reformula acest lucru în $\mathcal{F}_{\textsf{zk}}^R$-model hibrid),
- $\mathcal{S}_V$ trimite un puzzle aleatoriu $p$ la $\mathcal{A}$,
- $\mathcal{S}_V$ primește o pereche $(s, p')$ din $\mathcal{A}$,
- Dacă $s$ este o solutie valabila pt $p$, $\mathcal{S}_V$ avortează. In caz contrar, $\mathcal{S}_V$ trimite o solutie $s'$ pentru $p'$ la $\mathcal{A}$.
Este clar că, dacă nu $\mathcal{S}_V$ avortează, execuția ideală în prezența $\mathcal{S}_V$ nu se distinge de execuția reală în prezența $\mathcal{A}$. Cu ipoteza (i), putem vedea că această întrerupere are loc cu o probabilitate neglijabilă. Prin urmare, $\pi'$ este sigur împotriva verificatorului rău intenționat și, prin urmare, a ZK.
Intrebarea 1:
Ceea ce mă încurcă este că proba de mai sus nu necesită ipoteza (ii). Într-adevăr, Canetti a susținut că
În plus, faptul că $P$ (adică, doveditor) oferă $V$ (adică, verificator) cu o soluție $s'$ la puzzle $p'$ nu este cu adevărat o problemă într-un cadru independent, deoarece $V$ nu poate distinge $s'$ dintr-o valoare aleatorie (care $V$ ar fi putut genera de la sine).
Cum ajută această ipoteză la stabilirea proprietății ZK a $\pi'$ în cadru de sine stătător?
Înțelegerea mea:
Pentru mine, execuțiile succesive ale $\pi'$ (chiar și pentru aceleași intrări) rămâne ZK, deoarece probatorul cinstit eșantionează un puzzle aleatoriu $p$ de fiecare data.Aceste puzzle-uri sunt diferite de cele ale căror soluții sunt cunoscute verificatorului rău intenționat cu o probabilitate covârșitoare (în funcție de spațiul puzzle-urilor). Prin urmare, verificatorul nu poate folosi aceste puzzle-uri cunoscute pentru a forța probatorul să scoată martorul cu o probabilitate deloc neglijabilă în execuțiile secvențiale ale $\pi'$.
Desigur, pentru a încorpora ipoteza (ii) în dovezi, se pare că putem modifica $\mathcal{S}_V$ astfel încât în ultimul pas $\mathcal{S}_V$ trimite o soluție aleatorie $s'$ la $\mathcal{A}$ (mai degrabă decât o soluție validă pentru $p'$). Fără a pierde generalitatea, considerăm că $\mathcal{A}$ își prezintă punctul de vedere în acest caz. Apoi, putem vedea că soluția $s'$ este inclusă în $\mathcal{A}$punctul de vedere al lui. Pentru a obține securitate rău intenționată în modelul de sine stătător, soluția aleatorie $s'$ în simulare ar trebui să nu se distingă de execuția reală. Totuși, ipoteza incapacității verificatorului de a distinge soluțiile NU POATE fi tradusă în aceea pe care deosebitorul (care face distincția între execuțiile ideale și reale) nu poate face distincția între o soluție reală și una aleatorie. Prin urmare, ipoteza (ii) pare neputincioasă, deoarece deosebitorul poate încă distinge eficient cele două lumi observând soluția. $s'$ în $\mathcal{A}$punctul de vedere al lui.
În opinia mea, această problemă poate proveni din faptul că există o reducere între ipotezele (i) și (ii), ca și reducerea între ipotezele CDH și DDH. Această reducere face ca una dintre cele două ipoteze să fie redundantă. Este aceasta o înțelegere corectă?
Întrebările mele cu privire la securitatea în modelul UC
După cum se susține în lucrarea lui Canetti, $\pi'$ este nesigur în modelul UC, deoarece două execuții concurente ale $\pi'$ cu aceeași intrare $(x, w)$ poate scurge martorul $w$ către verificatorul rău intenționat. Mai precis, atacul funcționează după cum urmează:
$V$ mai întâi așteaptă să primească puzzle-urile $p_1$ și $p_2$ din $P$ în cele două sesiuni. Apoi trimite $(s, p_2)$ la $P$ în prima sesiune, pentru unii arbitrar $s$. In raspuns, $V$ primeste de la $P$ o solutie $s_2$ la $p_2$, la care se întoarce $P$ în a doua sesiune. De cand $s_2$ este o solutie corecta, $P$ va dezvălui acum $w$.
Să presupunem că $\pi$ realizează în siguranță $\mathcal{F}_{\textsf{zk}}^R$ în modelul UC și revizuiește această insecuritate din perspectiva dovezii de securitate. Acum, putem lua în considerare un simulator $\mathcal{S}_V'$ în modelul UC. Mai exact, $\mathcal{S}_V'$ este identic cu $\mathcal{S}_V$ cu excepția faptului că acesta extern interacționează cu mașina mediului $\mathcal{Z}$ care acționează ca verificator rău intenționat (mai degrabă decât intern interacționând cu $\mathcal{A}$). De cand $\pi'$ NU este UC-secure, $\mathcal{S}_V'$ ar trebui să avorteze în ultimul pas cu o probabilitate deloc neglijabilă. Cu alte cuvinte, $\mathcal{Z}$ ar trebui să poată rezolva eficient puzzle-ul $p$ eşantionat de doveditorul cinstit. $\mathcal{Z}$ este mai informat decât $\mathcal{A}$ în modelul de sine stătător de la soluție $s$ ales de $\mathcal{Z}$ depinde nu numai de viziunea sa în sesiunea curentă, ci și de celelalte concurente. Deci, se pare că există două moduri posibile pentru $\mathcal{Z}$ a rezolva $p$: (A) $\mathcal{Z}$ rezolvă $p$ de la sine sau (b) $\mathcal{Z}$ nu poate rezolva eficient $p$ dar folosește alte sesiuni pentru a o rezolva. Atacul aparține cazului (b).
Intrebarea 2:
Chiar dacă presupunem că $\mathcal{Z}$ nu poate lansa caz (b) atac, nu-i așa $\pi'$ încă nesigur în modelul UC? Pentru mine, dacă $\mathcal{Z}$ poate urma codul doveditorului cinstit pentru a rezolva $p$ iar ipoteza (i) referitoare la verificator nu se aplică $\mathcal{Z}$. În acest caz, $\mathcal{Z}$ poate folosi cazul (a) atac pentru a distinge două lumi.
Mai general, dacă facem unele ipoteze cu privire la părțile corupte în modelul UC, aceste ipoteze se aplică mașinii de mediu? $\mathcal{Z}$ care controlează aceste partide? Rețineți că, în modelul de sine stătător, distincția și adversarul sunt entități distincte. În contrast, distincția și adversarul sunt atât mașina mediului $\mathcal{Z}$ în modelul UC.
Întrebarea 3:
Pentru a argumenta în mod oficial că un protocol este sigur în modelul UC, ar trebui să enumerăm în mod explicit toate modalitățile posibile de $\mathcal{Z}$ să-și construiască mesajele de ieșire pe baza opiniilor sale despre execuțiile asincrone arbitrare ale (un număr posibil nelimitat de) sesiuni?
Am citit câteva dovezi UC, dar majoritatea nu menționează în mod explicit execuțiile asincrone ale sesiunilor. Deoarece protocoalele peste alte sesiuni pot fi arbitrare, cred că este imposibil de enumerat $\mathcal{Z}$mesajele lui bazate pe $\mathcal{Z}$opiniile lui despre toate sesiunile. Deci, cum ne putem asigura că $\mathcal{Z}$Mesajele lui transmise către simulator nu vor eșua simularea atunci când scriem o dovadă de securitate în modelul UC?
