Puncte:0

zkSnark Intro de Maksym Petkus: Polinomul este definit peste $Z$ sau este definit peste $Z_n$?

drapel et

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

Aici el are un polinom $p(x) = x^3 â 3x^2 + 2x$

iar criptarea homomorfă definită ca $E(c) = g^c \bmod 7$

Este puțin clar unde este definit polinomul $Z$ sau este definit peste $Z_7$ - a rămas puțin ambiguu în text.

Acest lucru contează în etapa în care verificatorul evaluează $E(h.t) = E(h)^t$. Îmi pot explica mai bine întrebarea cu $Z_{11}$ în loc de $Z_7$, deci folosesc $Z_{11}$ de mai jos.

Sa presupunem $E(c) = g^c \bmod 11$

Probe de verificare la s = 14

$E(s^0)= 5, E(s^1)= 9, E(s^2) = 5, E(s^3) = 9$

Prover calculează $E(p(s)) = (9 * 5^{-3} * 9^2) \bmod 11 = 9$

calculează $E(h(s)) = 5$. Trimite E(p)= 9 și E(h) = 9 la verificator

Verificatorul calculează t(s=14) Luați în considerare două cazuri

Cazul 1: Polinomul s-a terminat $Z$ În acest caz, t(s=14) = (13*12) = 156 Asa de $E(h)^t$ = $9^156 \bmod 11 = 9$

Deci se verifică -> $E(p) = E(h)^t$

Cazul 2: Polinomul s-a terminat $Z_{11}$ În acest caz, t(s=14) = (13*12)%11 = 2 Asa de $E(h)^t$ = $9^2 \bmod 11 = 4$. Aici nu se verifica.

Motivul pentru care nu se verifică este pentru că

$g^c \bmod m$ = $g^{c \bmod m-1} \bmod m$

adică t(s) trebuie redus cu 10 mai degrabă decât cu 11. Cu toate acestea, dacă polinomul este peste $Z_{11}$, apoi se reduce cu 11, nu cu 10.

Deci, pe baza acestui lucru, cred că polinomul este definit peste $Z$ mai degrabă decât peste $Z_7$.

Totuși, la pagina 7, scrie

în timp ce teoretic coeficienţi polinomi $c_i$ poate avea o gamă largă de valori, în realitate, ar putea fi destul de limitată (6 în exemplul anterior)

De unde au venit cei 6 de aici? Dacă s-a terminat $Z$, atunci coeficientul poate fi orice număr întreg. Dacă scrie e limitat la 6, atunci trebuie să fie peste ceva $Z_n$. Dacă s-a terminat $Z_7$, atunci ar fi limitat la 7 și nu la 6. Dacă s-ar fi terminat $Z_6$, atunci ar fi limitat la 6$.

La fel este definit polinomul sau $Z$ sau este definit peste $Z_7$ sau este definit peste $Z_6$?

Puncte:1
drapel ru

Pentru ce ne-am dori pentru cele mai generale aplicații este $p(x)$ a fi definit peste $\mathbb Z$. Cu toate acestea, nu există o schemă criptografică homomorfă generală, finită, în care să putem mapa elementele injectiv $\mathbb Z$. În schimb, trebuie să mapam într-un câmp principal mare (rețineți că secțiunea 3.2 elidează utilizarea unui domeniu integral), care ar trebui să fie suficient pentru a demonstra cunoașterea $p(x)$ construit din rădăcini întregi mici. Acest grup este reprezentat ca un subgrup de ordin prim al oricărui grup criptografic pe care îl folosim (putem lucra în grupul complet, dar după cum am menționat, acest lucru se confruntă cu problema de a nu fi un domeniu integral). În cazul grupului $(\mathbb Z/7\mathbb Z)^\times$, grupul este de ordinul 6 si ar trebui sa ne gandim ca in scop de verificare $p(x)$ este definit peste $\mathbb Z/6\mathbb Z$ dacă nu suntem preocupați să lucrăm într-un domeniu integral. Prin urmare, în exemplul dvs. mod 11 $p(x)$ ar trebui gândit ca un mod polinom 10 (ignorând din nou problemele domeniilor non-integrale). După cum vă puteți da seama, exemple mici ca acesta se confruntă cu tot felul de probleme de ambiguitate care devin din ce în ce mai puțin probabile pe măsură ce dimensiunea subgrupului crește în raport cu dimensiunea și numărul rădăcinilor.

drapel et
Că grupul polinomului este diferit de grupul de exponențiere pentru criptare este un detaliu destul de mare. Sunt foarte surprins că autorul nu a considerat că este suficient de important pentru a o pune în text. Cunoașteți alte texte, cărți sau site-uri care acoperă această parte a zkSnark mai detaliat?
Daniel S avatar
drapel ru
Cel mai bun lucru pe care îl pot gestiona este observația din partea de jos a paginii 12 a [această lucrare](https://www.iacr.org/archive/crypto2006/41170094/41170094.pdf)
drapel et
Remarca vorbește despre subgrupuri, dar în acest caz, din cauza $g^c \bmod m$ = $g^{c \bmod m-1} \bmod m$, cred că doar un subgrup va funcționa - inelul polinomial format din $\bmod {m-1}$. Sau gresesc?
Daniel S avatar
drapel ru
Aceasta va depinde de ordinea multiplicativă a $g$ modulo $m$. Vom lucra în inelul polinomial modulo această ordine. Petkus joacă puțin repede și liber aici. Secțiunea 3.2 arată clar că teorema fundamentală a algebrei este în uz, dar aceasta se aplică numai polinoamelor peste câmpuri (de exemplu $x^3-3x^2+2x$ are șase rădăcini în $\mathbb Z/\6\mathbb Z$). Pentru rigoare, ar trebui să folosiți $g$ de ordinul principal (care este cazul în aplicațiile criptografice).
drapel et
Caut reguli sau pași aici - dacă vreau să implementez această schemă pentru un polinom, atunci după ce definesc E(c) = g^c mod p, cum aleg apoi inelul peste care este definit polinomul. Dacă polinomul ar trebui definit peste mod p, mod (p-1) sau alt inel. Dacă alt inel, atunci care este acel inel?
Daniel S avatar
drapel ru
Ar trebui să alegeți un $g$ de ordin $q$ unde $q$ este cea mai mare împărțire primă $p-1$. Polinomul este apoi definit mod $q$.
drapel et
Exemplul lui Petkus nu pare să respecte această regulă. G lui este de ordinul 6. G lui nu este nici măcar de ordin prim, darămite de ordin prim cu cea mai mare împărțire a primelor p-1. Ar fi trebuit să aleagă un g de ordinul 3, nu?
drapel et
Tot în nota de subsol de la pagina 16, Petkus cere să aleagă un g care este un generator al câmpului finit. Care nu este același lucru cu „alegeți un g de ordinul q unde q este cea mai mare împărțire primă p-1”.

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.