înregistrare Logare
Puncte:2
avatar Crypto

zkSnark: Restricționarea unui polinom

drapel et
user93353

Citesc această explicație despre zkSnark scrisă de Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Am înțeles totul în primele 15 pagini.

În 3.4 Restricționarea unui polinom (Pagina 16)

Limităm deja un probator în selectarea puterilor criptate ale lui s, dar o astfel de restricție nu este aplicată, de exemplu, s-ar putea folosi orice mijloc posibil de a găsi niște valori arbitrare $z_p$ și $z_h$ care satisface ecuația $z_p = (z_h)^{t(s)}$ și să le furnizeze verificatorului în loc de $g^p$ și $g^h$. De exemplu, pentru unele r aleatoare $z_h = g^r$ și $z_p = (g^{t(s)})^{r}$, Unde $g^{t(s)}$ pot fi calculate din puterile criptate furnizate ale $s$. De aceea, verificatorul are nevoie de dovada că a furnizat doar criptări ale puterilor $s$ au fost folosite pentru a calcula $g^p$ și $g^h$ si nimic altceva.

Nu pot să înțeleg cum un probator poate găsi niște valori arbitrare ale $z_p$ și $z_h$ care satisfac $z_p = (z_h)^{t(s)}$? De exemplu, pentru unele r aleatoare $z_h = g^r$ și $z_p = (g^{t(s)})^{r}$

Dovatorul nu știe $s$ si nici nu stie $g$, deci cum va face asta?

Pe scurt, nu pot să-mi dau seama care este atacul (de care să mă protejez) pentru care este nevoie de „restrângerea unui polinom”.

129
0 + 0
Puncte:3
Daniel S avatar Crypto
drapel ru
Daniel S

La pagina 15 a lucrării, este furnizat probator $E(s^0)=E(1)=g$ (Mă voi referi la asta ca $E_0$). La fel sunt prevazute cu $$E_1:=E(s), E_1:=E(s^2),\cdots, E_d:=E(s^d).$$ Lăsa $t(s)=\sum_{0\le i\le d}c_is^i$ (cu $c_i$ cunoscut de dovator) apoi $g^{t(s)}=E(t(s))=\prod_{0\le i\le d}E_i^{c_i}$.

Astfel, probatorul le cunoaște pe amândouă $g$ și $g^{t(s)}$ și, ca și în hârtie, ei pot alege o aleatorie $r$ a construi $z_h$ și $z_p$ prin ridicarea acestor valori la putere $r$.

Ideea atacului este că calculele de mai sus nu necesită cunoștințe $p(x)$ care este ceea ce doveditorul ar trebui să demonstreze cunoștințe. Un verificator suficient de prost încât să creadă că valoarea aleatoare $z_h$ este egal $g^{h(e)}$ și asta $z_p$ este egal $g^{p(e)}$ nu vor avea nimic care să le contrazică credința.

0 + 0
drapel et
user93353
Știu că am acceptat deja răspunsul. Totuși, am încercat un exemplu și nu a funcționat.
0
Răspunde
drapel et
user93353
E(c) = g^c mod 23. Eșantioane de verificare la s = 14 și furnizează $E(s^0) = 5$, $E(s^1) = 13$, $E(s^2) = 12 $, $E(s^3) = 3$ Cele 2 rădăcini cunoscute sunt 3 și 4, adică $t(s) = (x-3)(x-4)$. Prover alege un r aleator = 6. t(6) = 3 * 2 = 6. Prover calculează $z_h = 5^6 \pmod {23} = 8$ & $z_p = (5^6)^6 \pmod {23 } = 13$ Trimite $z_p$ și $z_h$ către verificator Verificatorul calculează t(14) = 11 * 10 = 110. Verificatorul calculează $E(h)^t = 8^{110} \pmod {23} = 1$. Deci $E(p) \ne E(h)^t$ ce fac greșit? Am înțeles greșit răspunsul tău?
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Dovatorul nu calculează $t(r)$ și apoi $g^{t(r)}$. În schimb, ei calculează $g^{t(s)}=g^{s^2â7s+12}=12Ã13^{â7}Ã5^{12}$ și ridică aceasta la valoarea putere $r$. Declanșând sagemath, vedem că $g^{t(s)}\equiv 1\pmod{23}$, deci prover setează $z_p=1^r\equiv 1\pmod{23}$ și $z_h=8$ . Apoi calculează $z_h^{110}=8^{110}\equiv 1\pmod{23}$ care este aceeași valoare.
0
Răspunde
drapel et
user93353
Ok, asta se verifică!!
0
Răspunde
drapel et
user93353
Am găsit o altă problemă cu protocolul descris în 3.3 Fie ca a treia rădăcină reală să fie 0, adică polinomul adevărat este (x)(x-3)(x-4). Chiar dacă probatorul nu cunoștea polinomul adevărat și rădăcina adevărată și a presupus că a treia rădăcină era în loc de 2 în loc de 0 și că polinomul era (x-2)(x-3)(x-4) și nu toți pașii - pașii încă se verifică și verificatorul nu ar ști că demonstratorul nu cunoaște polinomul potrivit. Mă întrebam dacă aceasta este o defecțiune separată a protocolului explicat în 3.3 sau este o variație a aceluiași lucru menționat în 3.4. Cred ca este o vina de diferenta
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Da, problema este că valoarea eșantionului aleasă, $s=14$ este o rădăcină a lui $t(x)$ modulo 22, care este ordinea grupului mod 23. Acest lucru duce la $z_p=1$ care provoacă degenerare ca ai găsit. Verificatorul ar trebui să verifice înainte de a trimite acel $t(s)\not\equiv 1\pmod{q}$ pentru un prim mare $q$ care împarte $p-1$. Acesta este foarte probabil să fie cazul dacă folosim un prim mare și puternic.
0
Răspunde
drapel et
user93353
Vrei să spui că ambele probleme (una descrisă în 3.4 și cea pe care am subliniat-o în ultimul meu comentariu) sunt pentru că $s=14$ este o rădăcină a lui $t(x) \pmod {22}$ sau este doar una dintre ele? din acest motiv?
0
Răspunde
drapel et
user93353
Deci, am încercat ambele probleme cu s = 16 care nu este o rădăcină. Și ambele probleme rămân încă. Deci, având s ca rădăcină a t(s) mod (p-1) face ca E(p) să fie întotdeauna 1, dar altfel, cum provoacă probleme cu protocolul?
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Nu am o problemă cu $s=16$. Pentru polinomul $t(x)=x(x-3)(x-4)$, $t(s)=2496$. Pentru polinomul $(x-2)(x-3)(x-4)=x^3-9x^2+26x-24$ demonstratorul ar calcula $E(s^3)E(s^2)^ {-9}E(e)^{26}E(1)^{-24}=8$. Alegerea aleatorie $r=6$ doveditor trimite $z_h=8$ și $z_p=13$. Verificatorul are atunci $z_h^{2496}=3$ care nu este același cu $z_p$.
0
Răspunde
drapel et
user93353
p(x) = x(x-3)(x-4), t(x) = (x-3)(x-4) - deci t(16) = 156 și nu 2496. $13^{156} \ pmod {23} \equiv 8$ - prin urmare se potrivește
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.