Puncte:2

Modificarea ieșirii unei subrutine PPT pentru a se potrivi cu o dovadă de reducere

drapel us

Am un protocol care funcționează într-un cadru rău intenționat, care implică părți care își trimit reciproc elemente de grup $u\în \mathbb{G}$ a unui anumit formular (De exemplu, acestea sunt mesaje ale formularului $u=g^{\alpha}\cdot h^{\beta}$ cu generatoare $h,g\in \mathbb{G}$ și $\alpha, \beta \in \mathbb{Z}_q$ pentru unele prime $q$).

În plus, aceste părți atașează dovezi non-interactive de cunoștințe zero care arată că elementele grupului trimise sunt într-adevăr de acea formă (de exemplu, elementele grupului trimise nu au fost selectate în mod neglijent). Deci, dacă o parte din protocol trimite $u=g^{\alpha}\cdot h^{\beta}$ trebuie si atasat $\pi_{g,h}(u)$ care este un ZKPOK care demonstrează că $u$ este în forma dorită.

În încercările mele de a dovedi corectitudinea unui protocol, presupun în contradicție că există un adversar PPT $\mathcal{A}$ care încalcă protocolul și apoi folosesc $\mathcal{A}$ ca subrutină într-un nou PPT $\mathcal{B}$ care elimină o problemă insolubilă (în special, Logaritmul discret în $\mathbb{G}$).

Totuși, problema mea este că vreau $\mathcal{B}$ a folosi $\mathcal{A}$ într-o cutie neagră, dar vreau și eu utilizare „exponenții” săi (logaritmi discreti) $\alpha, \beta$ după alergare $\mathcal{A}$ pentru a calcula logaritmul discret al unui element de grup arbitrar $a\în \mathbb{G}$. In orice caz, $\mathcal{A}$ Poți alege $\alpha, \beta$ în orice mod care $\mathcal{B}$ alergare $\mathcal{A}$ poate să nu știe.

Cum rezolv această diferență?

Ceea ce am avut în vedere, este să am $\mathcal{A}$ ieșire $\alpha, \beta$ ca parte a producției sale și motivează că de atunci $\mathcal{A}$ trebuie să atașeze un ZKPOK de $\alpha, \beta$ la trimiterea elementelor sale de grup, a calculat $\alpha, \beta$ pe cont propriu și, prin urmare, le poate și scoate.

  1. Pot să modific $\mathcal{A}$ieșirea lui în așa fel încât să se potrivească nevoilor mele?
  2. Există o abordare diferită/mai bună pentru a rezolva problema în care am nevoie de acces la logaritmi discreti trimiși de o parte controlată de un PPT în cutie neagră?
  3. Îmi poate indica cineva o lucrare care implică o dovadă cu o tehnică similară?

Multe mulțumiri in avans.

drapel cn
O dovadă de cunoaștere prin definiție permite extragerea martorului. De ce nu poți face asta pur și simplu în reducerea ta?
yacovm avatar
drapel us
Deoarece ZKPOK este trimis în protocolul meu ca NIZK, deci nu pot folosi tehnici de „rebobinare” pe $\mathcal{A}$ care extrag martorul. Mi-am editat întrebarea pentru a sublinia că acestea sunt NIZK-uri. Mulțumesc pentru întrebare.
drapel cn
Dacă este un PoK, puteți extrage. Aceasta este pur și simplu definiția unui PoK. Cu un NIZKPoK care funcționează, în general, fie prin trapdooing-ul CRS, fie printr-o extracție de tip Lema de bifurcare.
yacovm avatar
drapel us
(1) Vă rugăm să vă conectați la un exemplu dintr-o lucrare? (2) Metoda pe care am descris-o la întrebare este ceva sunet sau nu?
Puncte:2
drapel us

Nu puteți modifica $\mathcal A$ în acest fel. Dacă aveți nevoie $\alpha$ și $\beta$ pentru reducerea, atunci va trebui să utilizați cunoștințe zero dovada cunostintelor din care le puteți extrage. Înțeleg că doriți să utilizați un NIZK. Cu toate acestea, aceasta de fapt nu este o problemă. Dacă luați un protocol Sigma (dovada în trei runde) pentru angajamentele Pedersen (care este în esență ceea ce aveți aici) și apoi aplicați transformarea Fiat-Shamir la acesta, atunci rezultatul este o dovadă a cunoștințelor non-interactivă cu zero cunoștințe de unde poți extrage martorul $\alpha,\beta$, în model aleator-oracol. Acest lucru este foarte standard. Un tutorial despre protocoalele Sigma de Ivan DamgÃ¥rd poate fi găsit Aici. Faptul că puteți extrage rezultă din lema de bifurcare pentru Fiat-Shamir de Pointcheval și Stern (vezi și această lucrare a lui Bellare și Neven despre lema de bifurcare).

yacovm avatar
drapel us
Cred că înțeleg ceea ce încercați să spuneți, totuși, ce se întâmplă dacă PPT-ul imbricat (PPT-ul adversarilor) are intrare privată și, ca urmare, cerințele pentru aplicarea lemei de bifurcare nu sunt valabile? Poate că ar trebui apoi să împart adversarul în doi algoritmi diferiți - (i) unul care produce ZKPOK și (ii) unul care primește ZKPOK NIZK ca intrare și face restul și apoi aplică bifurcarea pe primul adversar? Este ceva posibil?
Yehuda Lindell avatar
drapel us
Aplicați întotdeauna extractorul de cunoștințe la mașina care generează ZKPOK. Acest lucru este de obicei important în ceea ce privește mesajele anterioare trimise. Deci, ne uităm la „adversarul rezidual”, care este adversarul care a conectat starea adversarului până în acel moment. De fapt, nu-ți pasă ce se întâmplă după ZKPOK, deoarece nu ajungi niciodată acolo.
yacovm avatar
drapel us
Vă mulțumesc pentru răspuns (și pentru răspuns, desigur). Nu sunt sigur că am înțeles pe deplin. Poate îmi puteți indica o lucrare (sau un capitol dintr-o carte) în care este descris un astfel de adversar rezidual, astfel încât să pot învăța dintr-un exemplu concret? Multe mulțumiri in avans.
Yehuda Lindell avatar
drapel us
Consultați Secțiunea 5.3 din https://eprint.iacr.org/2016/046.pdf.Descrie un verificator rezidual utilizat pentru a demonstra ZK și modul în care funcționează din punct de vedere tehnic rebobinarea. Este același lucru de care veți avea nevoie aici.
yacovm avatar
drapel us
Multumesc pentru raspuns. Cu toate acestea, în protocolul meu, nu există nicio dezvăluire a commit-ului - toate părțile trimit mesaje însoțite de ZKPOK-uri și am probleme în a dovedi corectitudinea, nu proprietatea de cunoștințe zero. Secțiunea 5.3 se ocupă de demonstrarea proprietății zero-cunoștințe.
Yehuda Lindell avatar
drapel us
Aceeași noțiune de adversar rezidual este folosită pentru a demonstra zero cunoștințe și pentru a rula un extractor de cunoștințe. Astfel referința este relevantă.

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.