înregistrare Logare
Puncte:5
avatar Crypto

De ce sunt folosite protocoalele Zero-Knowledge pentru problemele NP dacă IP este clasa sistemelor de dovezi interactive de unde provin?

drapel in
Andrea Farneti

După cum se spune în titlu, studiez ZKP-urile și văd că sunt doar sisteme interactive de demonstrare care respectă proprietatea zero-cunoștințe. Acum, dacă este adevărat, de ce nu sunt ele folosite pentru problemele IP, clasa de complexitate a sistemelor de dovezi interactive care a fost introdusă inițial pentru ei? Adică, nu este mecanismul de demonstrare interactiv în ZKP-uri între Prover și Verifier? Atunci de ce vorbim despre problemele NP, care sunt opusul interactivului?

258
0 + 0
baro77 avatar
drapel gd
baro77
Din cate stiu eu 1) demonstrând ZKP pentru o anumită problemă NP-completă ca G3C, ați dovedit-o pentru fiecare problemă NP-completă (și nu știu dacă există ceva similar în sensul mai larg al IP) 2) În criptografie, problemele NP sunt de mare interes deoarece, în termeni profani, pentru un verificator sunt greu de calculat, dar ușor de verificat. 3) Din punct de vedere general, în criptografie, interactivitatea nu este atât de dorită deoarece obligă părțile să fie online în același timp: din câte știu adesea, aromele ZKP sunt cele NI obținute introducând alte modele (de ex. ROM sau CRS)
0
Răspunde
Geoffroy Couteau avatar
drapel cn
Geoffroy Couteau
De fapt, există o reducere ușoară de la ZK pentru NP la ZK pentru toată IP (ei bine, nu atât de ușoară pentru că se bazează pe dovada IP = PSPACE, dar ușoară având în vedere această dovadă). Sunt de acord cu toate celelalte puncte, totuși.
0
Răspunde
Puncte:11
Yehuda Lindell avatar Crypto
drapel us
Yehuda Lindell

Motivul este că, în esență, clasa de limbi în $\mathcal IP$ care nu sunt in $\matematic NP$ nu poate fi dovedit cu un probator eficient. Deoarece suntem de obicei interesați de contextul criptografic cu dovezi eficienți, studiul ZK se concentrează de obicei pe $\matematic NP$. (Rețineți că atunci când studiem complexitatea și adesea în bazele criptografiei, suntem cu siguranță interesați de doveditorii ineficienți.)

Pentru a vedea de ce în afara $\matematic NP$ doveditorul nu poate fi eficient, rețineți că orice dovadă interactivă cu un doveditor eficient (dat un martor) poate fi emulată de o mașină care primește martorul și rulează proba local, testând dacă rezultatul este acceptat sau respins. Aceasta este exact clasa de limbi $\mathcal MA$. În ipotezele standard de derandomizare, $\mathcal MA = NP$. Astfel, în aceste ipoteze, orice limbă care nu este în $\matematic NP$ poate fi rulat doar cu un doveditor ineficient (chiar dându-i un martor). Ca atare, este de mai puțin interes atunci când se construiesc protocoale și altele asemenea.

0 + 0
drapel in
Andrea Farneti
Multumesc mult, am acceptat raspunsul tau. Totuși, nu înțeleg de ce dacă dovezitorul este ineficient sau nu face diferența cumva. Mai ales dacă are un martor, mereu am crezut că asta este partea relevantă. Adică, când ai spus „în aceste ipoteze, orice limbaj care nu este în NP poate fi rulat doar cu un doveditor ineficient (chiar dându-i un martor)”, dacă un doveditor ineficient are încă un martor, ce diferență poate face pentru un algoritm sau o clasă de complexitate în ciuda uneia eficiente? și de ce?
0
Răspunde
Yehuda Lindell avatar
drapel us
Yehuda Lindell
Vrem ca dovatorul să fie eficient cu un martor. Ceea ce am vrut să spun este că, dacă nu suntem în NP (sau de fapt MA), atunci dovezitorul nu poate fi eficient în niciun caz (adică nu poți face probatorul eficient dându-i un martor). Răspunde asta la întrebarea ta?
0
Răspunde
drapel in
Andrea Farneti
De fapt, am înțeles partea aia, mulțumesc. Dar de ce ai nevoie de un doveditor pentru a fi și eficient dacă are deja un martor? Am crezut că partea eficientă este doar să garanteze un nivel mai mare de securitate atunci când se analizează un protocol (de exemplu, diferitele niveluri de cunoștințe zero, computaționale, statistice sau perfecte), dar de ce avem nevoie ca dovatorul să fie eficient dacă are deja un martor? Nu trebuie doar să folosească martorul pentru a dovedi o declarație și să trimită răspunsul verificatorului? Poate că răspunsul este că pentru a calcula răspunsul pentru afirmația doveditorul are nevoie în continuare de putere de calcul?
0
Răspunde
Yehuda Lindell avatar
drapel us
Yehuda Lindell
Îmi pare rău, dar îmi este greu să înțeleg întrebarea.Avem nevoie ca dovatorul să fie eficient dacă dorim să folosim demonstrația ZK într-un protocol criptografic - deoarece într-un astfel de context, toate părțile trebuie să fie timp polinomial. Nu vă înțeleg întrebarea de la sfârșit „Nu trebuie doar să folosească martorul pentru a dovedi o declarație”. Dovatorul folosește într-adevăr martorul, dar asta nu înseamnă că este neapărat un proces eficient (adică, timp polinomial).
0
Răspunde
drapel in
Andrea Farneti
Exact, așa că am înțeles bine. Mulțumesc foarte mult, engleza nu este limba mea maternă, dar acum totul este clar!
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

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.