Puncte:4

Relația dintre extractorul de cunoștințe și soliditatea în ZKPoK

drapel gd

Citind De ce Zk-SNARK-urile sunt Argument of Knowledge dacă există un Knowledge Extractor? Mă simt confuz de prima declarație a OP:

Din câte știu, demonstrarea existenței unui Knowledge Extractor implică o soliditate perfectă.

Răspunsul se concentrează pe faptul că soliditatea nu este neapărat perfectă, dar pare să confirme implicit implicația de soliditate de către extractor.

În primul rând, permiteți-mi să afirm că atunci când citesc „soliditatea” mă gândesc la proprietatea IP-urilor care afirmă că nicio strategie Prover nu poate convinge Verificatorul de un simbol care nu aparține Limbului cu o probabilitate mai mult decât neglijabilă... ceea ce pare cu totul diferit. „obiect” decât un extractor „vărsând” martorul, așa că îmi este greu să-mi fac o idee cel puțin naivă a acestei presupuse implicații.

Totuși am început să cred, din cauza surselor pe care le-am găsit, de exemplu:

[...] proprietatea de soliditate este înlocuită cu o proprietate de extragere a cunoștințelor [...]

Când vine vorba de demonstrarea temeiniciei unei dovezi de cunoștințe, avem o abordare formală foarte frumoasă. La fel ca și în cazul Simulatorului despre care am discutat mai sus, trebuie să demonstrăm existența unui algoritm special. Acest algoritm se numește extractor de cunoștințe și face exact ceea ce pretinde. Un extractor de cunoștințe (sau doar âExtractorâ pe scurt) este un tip special de Verificator care interacționează cu un Prover și â dacă Proverul reușește să completeze dovada â Extractorul ar trebui să poată extrage Secretul original al Proverului. Și asta răspunde la întrebarea noastră de mai sus. Pentru a dovedi temeinicia unei dovezi de cunoștințe, trebuie să arătăm că există un Extractor pentru fiecare Prover posibil.

CU toate acestea, în paragraful 4.5 „Ce zici de soliditate?” de Despre definirea dovezilor de cunoaștere unde Bellare și Goldreich se ocupă de formularea lor de PoK față de cele anterioare (https://www.wisdom.weizmann.ac.il/~oded/PS/pok.ps) Am găsit aceste cuvinte:

Menționăm că definiția noastră nu impune nicio cerință pentru caz $x$ nu în $L_R$. În special, soliditatea (adică o limitare a capacității doveditorului de a-l determina pe verificator să accepte $x$ nu în $L_R$) Nu este necesar. În consecință, un verificator de cunoștințe pentru $R$ nu definește neapărat o dovadă interactivă de apartenență la $L_R$. Acest lucru este în contrast cu definițiile anterioare; aveau condiția de „validitate” implică condiția de soliditate, astfel încât aceasta din urmă a avut mereu loc. Considerăm că „decuplarea” noastră a temeiniciei de valabilitate este justificată atât conceptual, cât și în lumina anumitor aplicații.

Apropo, este același punct de vedere al celebrului Golderich „Fundarea criptografiei”, secțiunea 4.7.

Deci, din nou, sunt îndoielnic despre: Knowledge Extractor $=>$ Soliditatea

Ar putea cineva să declare explicit dovada implicației sau cel puțin să-mi dea indicii despre asta?

Sau poate că existența Knowledge Extractor evită într-un fel de la sine ca Verificatorul să fie convins de un „martor” necunoscut cu adevărat de către Prover, așa că ar putea fi considerat un fel de „proprietate sănătoasă”, chiar dacă de natură diferită față de obișnuit. cele? (acest punct de vedere pare confirmat de Geoffroy Couteau în schimbul de întrebări/răspuns citat inițial când scrie:

Da, există mai multe dimensiuni în aroma solidității: dacă aveți „soliditatea de membru” sau „soliditatea cunoștințelor” este una (de obicei spun „extractabilitatea cunoștințelor” în lucrarea mea pentru a distinge de soliditatea obișnuită)

totuși, dacă acesta este cazul, m-aș fi așteptat ca el să corecteze acest „implica” prin OP)

Scuze că am fost pronunțat, sper să fi descris îndoielile mele într-un mod de înțeles.

DiamondDuck avatar
drapel hu
Nu inteleg pe deplin intrebarea ta. Pentru IP-ul sănătos, dacă luați DLOG ca limbă, un șir gol de la prover ar trebui să convingă Verifier$(X=g^x)$ că $X$ este în limbă. Dar nu transmite ideea că probatorul știe $x$. Deci, extractorul de cunoștințe este pentru soliditatea cunoștințelor (implicând dovezitorul știe de fapt $x$ pentru a produce dovada validă).
baro77 avatar
drapel gd
IP-urile sunt bine definite de Completeness și Solidness, în timp ce pentru PoK Completeness și Knowledge Extractor Existence sunt citate. Pot exista două explicații, cred: KE => proprietatea obișnuită de soliditate sau KE reprezintă o aromă de soliditate destul de diferită, dar oricum adecvată. Literatura nu mă ajută să înțeleg care este cazul potrivit și cum să-l demonstrez (sau măcar să-l simt rezonabil)
Puncte:5
drapel cn

Cunoașterea Extractabilitatea este o proprietate strict mai puternică decât soliditatea. Mai jos, voi schița de ce extractibilitatea necondiționată a cunoștințelor implică soliditatea statistică. În termeni informali, soliditatea statistică afirmă:

„Dacă afirmația este incorectă, atunci orice doveditor rău intenționat va avea o probabilitate neglijabilă de a produce o dovadă de acceptare”

Pe de altă parte, KE afirmă:

(*) „Luați orice algoritm de demonstrare (posibil rău intenționat), care produce o dovadă de acceptare cu o probabilitate deloc neglijabilă. Apoi există un extractor (timp polinomial așteptat) care interacționează cu acest doveditor și recuperează un martor (adică, o dovadă) care afirmația este adevărată”.

Formulat ca mai sus, ar trebui să fie relativ clar că KE implică temeinicie: dacă KE este garantat că va găsi un martor pentru că declarația este adevărată, înseamnă în special că declarația este Adevărat. În alți termeni, (*) implică:

„Dacă există un algoritm de demonstrare (posibil rău intenționat) care produce o demonstrație de acceptare cu o probabilitate deloc neglijabilă, atunci afirmația este în mod necesar adevărată”

Luarea contrapoziției dă: „Dacă afirmația este incorectă, atunci niciun algoritm de demonstrare nu poate produce o demonstrație de acceptare cu probabilitate neneglijabilă”,

care este exact statistic soliditatea. Rețineți că acest lucru nu vă oferă perfect soliditate: pentru aceasta, ai avea nevoie de o formă de extragere a cunoștințelor „super puternice” care să garanteze extragerea unui martor din orice doveditor (posibil rău intenționat) care scoate o dovadă de acceptare cu orice probabilitate $p>0$.

Rețineți că există, de asemenea, situații în care putem dovedi doar o formă computațională a KE, cum ar fi „fie putem extrage un martor din acest doveditor de succes delimitat polinomial, fie putem folosi demonstratorul pentru a rezolva această problemă grea”. În acest caz, KE computațională implică soliditatea computațională.

Puncte:0
drapel gd

Mulțumesc! Acum schița ta m-a ajutat să nu mă mai pierd în detaliile formale ale FoC 4.7 și, de asemenea, să înțeleg Când temeinicia cunoașterii implică temeinicie , găsit între timp și care merită să fie citat aici, bănuiesc (de aceea scriu și asta ca răspuns)

Cred că confuzia mea a provenit în primul rând din faptul că nu sunt un specialist în acest domeniu ;-) și mai târziu de la Goldreich alegerea dornică de a nu defini KE Validitatea pentru afirmațiile false și deducția sa următoare despre faptul că nu pot face față situației de declarații false (chiar și dacă schița dvs. mă face să cred că, chiar dacă nu este definită în acest caz, pare imposibil ca un KE să poată returna martorul inexistent al unei declarații false, deci KE returnarea unui martor implică într-adevăr afirmația că este adevărată, așa că lanțul dvs. logic pare valabil și în conformitate cu Goldreich ipoteze)

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.