Puncte:5

Următoarea schemă de dovezi este zero cunoștințe?

drapel ru

Luați în considerare că doresc să dovedesc cunoștințele unei chei private RSA corespunzătoare unei chei publice $(e,N)$. O schemă de demonstrare interactivă naivă ar proceda după cum urmează:

  • $V$ generează un mesaj aleator $m$ și îl criptează, trimițând datele criptate $c$ la $P$
  • $V$ apoi cereri $m$ intors din $P$. Presupunând $P$ nu putea avea cunoștință de $m$ in afara de $c$, atunci $P$ poate dovedi cunoașterea $d$ prin răspunsul corect $m$

Acest lucru pare să fie solid și complet din ipoteza durității problemei RSA. În mod clar, acesta trebuie să fie a private-coin sistem, deoarece dacă datele aleatoare erau publice, atunci un necinstit $P$ ar putea deduce oricare $m$. Cred că avem nevoie și de presupunerea că aceasta este o schemă de verificare onest, pe baza că un oracol de decriptare ar permite o întrerupere a manualului RSA (cred). Cu toate acestea, am putea abstrage și detaliile criptosistemului asimetric folosit și să presupunem că este un criptosistem asimetric teoretic care nu poate fi spart folosind un oracol de decriptare și atunci cred că am putea renunța la această stipulație.

Intuitiv, această schemă nu este zero-cunoaștere, deoarece oferim ceva oarecum semnificativ (adică decriptarea unui $c$). Cu toate acestea, putem construi cu ușurință un simulator pentru această schemă care va alege unele aleatorii $m$, criptați-l și apoi trimiteți originalul înapoi $m$ - ceea ce implică că este de fapt zero-cunoaștere. Îmi lipsește o nuanță de aici cu ceea ce poate/nu poate face simulatorul?

Această schemă este zero cunoștințe cu RSA (de ce/de ce nu)? Dacă nu este, ar fi zero cunoștințe cu o schemă asimetrică idealizată care nu este vulnerabilă la niciun atac bazat pe oracole de decriptare (de ce/de ce nu)?

Vadym Fedyukovych avatar
drapel in
Protocolul „Monede adânci” https://crypto.stackexchange.com/questions/78176/protocol-for-proof-of-knowledge-of-l-th-root
Puncte:3
drapel ru

Am citit ceva de când am postat această întrebare și acum am o înțelegere mai bună a acesteia, așa că îmi voi răspunde singur.

Confuzia provine din diferența dintre zero-cunoaștere și cinstit-verificator zero cunoștințe. Luați în considerare verificatorul $V^0$ care va genera o aleatorie $m$, criptați-l pentru a genera un text cifrat $c$ și trimite-l prin canal către $P$. $P$ (se presupune că este și sincer) va răspunde apoi cu $m$. Această interacțiune este trivial zero cunoaștere. Intuitiv, $V^0$ nu a învățat nimic, din moment ce știau deja $m$ - în mod formal putem construi un simulator care creează o transcriere falsă a dovezii prin generarea unui $m$ și criptarea acestuia. In orice caz, $V^0$ este verificator cinstit - este un verificator care actioneaza conform protocolului.

Luați în considerare următorul verificator rău intenționat $V^*$: nu efectuează nicio criptare și pur și simplu va trimite întotdeauna un text cifrat setat, $c^*$. Acum se învață ceva - decriptarea $c^*$, care nu era cunoscută înainte de atunci $c^*$ nu este rezultatul unei criptări cunoscute, ci rezultatul unei alegeri specifice. Definiţia zero-cunoaşterii prevede că pentru toți verificatorii trebuie să existe un simulator. $V^*$ nu poti să fie simulat fără cunoașterea secretului, deoarece este ușor să verificați dacă decriptarea este corectă prin re-criptarea acesteia, deci decriptarea corectă a $c^*$ trebuie să fie cunoscut de simulator, caz în care simulatorul trebuie să poată decripta texte cifrate arbitrare, ceea ce nu este posibil fără acces la secret; astfel, schema nu este de fapt zero-cunoaștere, indiferent de criptosistemul utilizat (cu excepția cazului în care criptosistemul este stricat și, prin urmare, un simulator poate decripta mesaje arbitrare în timp polinomial, caz în care dovada este discutabilă). Rețineți aici că este esențial $V^*$ trimite de fiecare dată un text cifrat fix - dacă $c^*$ este ales la întâmplare pentru fiecare interacțiune, transcrierea poate fi ușor falsificată.

Nu face parte din întrebarea inițială, dar cred că este important să o aducem în discuție - aceasta nu este o dovadă validă a cunoștințelor, ceea ce am vrut să fie. De fapt (indicând prin $S_\mathcal{M}$ această schemă implementată cu unele criptosisteme $\mathcal{M}$), "$S_\mathcal{M}$ este o dovadă a cunoștințelor" $\implică $ „decriptare acces oracol la $\mathcal{M}$ permite exfiltrarea cheii private". Aceasta este o consecință imediată a lipsei unei etape de angajament, așa cum ar fi folosită într-un $\Sigma$-protocol. O dovadă a cunoștințelor necesită să putem scrie un extractor $E$ care poate recupera secretul de la $P$ dacă li se permite să-și dea înapoi starea. In orice caz, $P$ așa cum este descris aici, este apatrid - indiferent de interacțiunea sau când în interacțiune este trimisă o intrare, ieșirea este aceeași - deci existența unui extractor eficient pentru $P$ implică imediat că $\mathcal{M}$ este complet rupt cu accesul la oracol de decriptare. Aceasta este doar o dovadă interactivă care demonstrează (cu $\epsilon$, marja de eroare, definită vaci) că $P$ poate decripta mesaje arbitrare - nu îndeplinește cerințele pentru a dovedi cunoașterea cheii private.

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.