Puncte:5

Este „Martorul” și „Dovada” același lucru când vorbim despre Cunoașterea Zero? Dar „argument”? Și „afirmație”?

drapel in

Am văzut oameni făcând o mulțime de distincții în timp ce citeau lucrări despre cunoștințe zero.
Am văzut termenul „Argument de cunoaștere” care pare să fie folosit ca o „Dovadă de cunoaștere” mai slabă: ceea ce am înțeles este că, dacă vorbești despre proprietatea normală de soliditate, vorbești despre „argumente”, în timp ce dacă vorbești despre proprietatea de valabilitate (din Proofs of Knowledge) atunci vorbiti despre „dovezi”. Este corect?

Dar ceea ce mă încurcă cel mai mult este că am văzut termenul „martor” și „dovadă” folosiți ambele în mod diferit și pentru a exprima același concept. Știu ce este un martor (în principiu, secretul Proverului), dar am auzit și frazele:
„P nu cunoaște un martor, dar știe o dovadă”
"generarea martorului SI generarea dovezii"
„în Zk-SNARKS, succint: dimensiunea probei este mult mai mică decât dimensiunea martorului”.

„Verificarea dovezilor este mult mai rapidă decât verificarea directă a declarației, chiar și având în vedere martorul”.
Această ultimă frază este cu adevărat haotică pentru mine.

Deci ele diferă? Dacă da, care este diferența dintre „dovadă” și „afirmație”?
Engleza nu este limba mea maternă, asta ar putea fi problema, dar vă rog să îmi clarificați toți acești termeni?

Puncte:2
drapel gd

Despre câteva subiecte secundare

Cred că vorbim despre „Argument” atunci când o „Dovadă” a solidității depinde de ipotezele computaționale: deci soliditatea Arguments este mai slabă decât cea a lui Proofs, dar adesea suficient de puternică având în vedere că aplicațiile actuale ale criptografiei se bazează întotdeauna pe duritatea computațională; iar contrapartida este că, de exemplu, NP Arguments poate fi ZK este o modalitate mai puternică decât NP Proofs (statistic ZK vs computational ZK).

Sufixul „de cunoaștere” este folosit (atât pentru dovezi, cât și pentru argumente) atunci când probatorul deține informații care pot fi extrase eficient printr-o „configurare specială” (specială într-un mod analog Simulatorul este special).


Sau încercați să o gândiți în acest fel: „aroma sănătoasă” și „a ști ceva (sau nu)” sunt două proprietăți ortogonale, așa că ați putea avea un „produs cartezian” de combinații:

  1. Dovada ZK
  2. Argumentul ZK
  3. ZK Dovada de cunoștințe
  4. ZK Argument of Knowledge („ARK” în ZK-SNARK)

1 și 3 au o soliditate mai puternică(*), 2 și 4 doar computațional; pentru 3 și 4 există un Extractor (aceasta este modalitatea recunoscută de a dovedi cunoștințele) care poate obține eficient informațiile pe care le deține probatorul (și nu rupe proprietatea ZK într-un mod analog, Simulatorul nu distruge soliditatea... oprire/ derularea înapoi și toate chestiile astea..)

deci un Argument, care este mai slab decât o dovadă din punct de vedere al temeiniciei, poate avea un nivel de securitate Zero Knowledge mai puternic (statistic) decât o dovadă (computațională)? Adica este in regula...dar cum de? Nu văd de ce ar fi posibil.

Dacă înțelegeți că „soliditatea” și „cunoașterea” sunt două proprietăți distincte, veți obține, de asemenea, că o a treia proprietate distinctă este „cunoașterea zero”, care ar putea depinde de prima într-un mod care nu este ceea ce vă așteptați.

Sunt doar un tocilar și un cititor pasionat, așa că bănuiesc că ați putea primi cu ușurință multe explicații mai bune decât ale mele, totuși vreau să vă sugerez capitolul 4 din Fundamentele criptografiei Vol.1 a lui Oded Goldreich ... cu adevărat perspicace...

(*) nu numai la „nivelul” statistic, în Proofs soliditatea este dovedită prin derivarea logică din context și axiome, deci demonstrațiile comune „clasice/standard”

drapel in
Bine, atunci când vorbiți despre proprietatea de soliditate la nivel de calcul, folosiți termenul Argument, în timp ce dacă definiți un Extractor de cunoștințe și dovediți că există un martor, vorbiți despre dovezi... Sau poate vorbiți despre dovezi chiar și fără Extractoarele de cunoștințe, ci doar proprietatea solidității la un nivel statistic de securitate? În afară de asta, deci un Argument, care este mai slab decât o dovadă din punct de vedere al temeiniciei, poate avea un nivel de securitate Zero Knowledge mai puternic (statistic) decât o dovadă (computațională)? Adică, ok... dar cum de? Nu văd de ce ar fi posibil asta.
baro77 avatar
drapel gd
Am încercat să răspund cu un comentariu, dar aveam nevoie de mai mult spațiu așa că mi-am editat răspunsul anterior
drapel in
Mulțumesc foarte mult, i-am dat cel mai bun răspuns lui Yehuda, pentru că acel răspuns a fost principalul lucru de care aveam nevoie pentru a-mi limpezi mințile, dar chiar și al tău a fost de mare ajutor. Nu știam bine diferența dintre argument și dovezi înainte, dar acum știu, atât de mulți termeni diferiți pentru a învăța să înțelegi cu adevărat Zero Knowledge... Ți-am dat un vot pozitiv!
baro77 avatar
drapel gd
Ai făcut ce trebuie! :) Yehuda nu este doar proeminent în industrie, ci aparține și unui grup de profesioniști/profesori care își donează o parte din timpul lor aici în comunitate: deci oferind pastile din activitatea lor didactică în afara canalului oficial al orelor universitare, de asemenea: nu comune și demn de laudă, ajutând la răspândirea cunoștințelor de calitate. Așa că mulțumirile mele lui și altora (acum îmi amintesc de @GeoffroyCouteau , dar cu siguranță lipsesc și mulți alții). În ceea ce mă privește, învăț doar ca tine, iar încercarea de a răspunde mă ajută să consolidez concepte: mulțumesc pentru vot pozitiv!
Puncte:2
drapel us

În primul rând, este important să înțelegeți că nu toată lumea folosește terminologia corect sau în același mod. Deci, nu veți găsi o consistență deplină peste tot. Acestea fiind spuse, cred că în acest caz este destul de clar. A martor este un tip de probă foarte specific. Mai exact, este ceea ce numim o dovadă NP că $x\în L$. ($\matematic NP$ ca o clasă de complexitate poate fi privită în multe feluri. „Cel mai bun” mod conceptual, în opinia mea, este ca o clasă de limbi pentru care afirmațiile au dovezi scrise eficiente. Adică, există o mașină de verificare a timpului polinomial (deterministă). $V$ astfel încât $x\în L$ dacă și numai dacă există o $w$ astfel încât $V(x,w)=1$. Cu toate acestea, există multe alte modalități de a demonstra afirmațiile. În primul rând, există declarații despre care dovedim că nu sunt incluse $\matematic NP$. În al doilea rând, s-ar putea să dovedim o declarație NP, dar vrem alte proprietăți - cum ar fi cunoștințe zero. Într-un astfel de caz, folosim o dovadă interactivă. Dovatorul poate folosi martorul, dar nu îl trimite. În cele din urmă, pot exista cazuri (cum ar fi într-un SNARK) în care dovada poate fi mai scurtă decât martorul original NP și este posibil să dorim dovezi în care timpul necesar pentru a verifica dovada este mai scurt decât timpul de rulare. $V(x,w)$ și verificați-l în modul clasic NP și așa mai departe. Sper că acest lucru este clar.

drapel in
Mulțumesc foarte mult Yehuda, da, asta ajută foarte mult.Am crezut că un martor este un secret care îi permitea unui Prover să genereze o dovadă întotdeauna într-un mod eficient, dacă o ai, și cred că este „cam” corect (poate nu întotdeauna eficient), nu? Dar și martorul poate fi văzut ca o dovadă în sine, dar una NP, nu? Întrebarea care vine de la sine este: cum este posibil ca în contexte precum SNARK-urile o dovadă să fie mai scurtă și mai rapidă decât un martor, dacă martorul este o dovadă deterministă NP? Ce poate fi mai rapid de atât?
drapel in
Adică, cred că pentru a verifica o dovadă P mai trebuie să rulați V(x, p) așa cum ați rula V(x, w), nu? Și martorul este mult mai puternic decât o dovadă, așa că cum poate fi mai rapid? Asta e singura mea îndoială
Yehuda Lindell avatar
drapel us
Gândiți-vă că P lucrează mai mult pentru a oferi ceva care este mai ușor pentru V. De asemenea, spre deosebire de dovezile NP, permitem verificatorului să facă uneori o greșeală (cu probabilitate scăzută) și, de asemenea, îi permitem să fie probabilistic. Aceste lucruri ajută foarte mult.
drapel in
Ok, spune-mi dacă am înțeles bine pentru că este greu să vezi imaginea completă: într-un protocol interactiv, un Martor pentru acesta este o dovadă care va fi întotdeauna acceptată de la Verificator, așa că dacă ai un Martor poți dovedi întotdeauna că x este în L cu probabilitatea 1, dar nu este neapărat eficient. Dacă aveți o dovadă, în schimb, puteți demonstra că x este în L cu o anumită probabilitate (destul de mare). În acest fel, o dovadă poate fi mai rapidă decât un martor. Este acesta modul corect de a vedea diferența dintre dovadă și martor?
Yehuda Lindell avatar
drapel us
Da. Singurul lucru pe care l-aș spune diferit este în a doua jumătate în care m-aș referi la un „sistem de probă” care implică un doveditor și un verificator. Acesta este diferit de un martor care oferă analogul unei dovezi scrise.

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.