Reducerea cantitativă a schemei de identificare a lui Schnorr la DLP

Întrebare

caut un mai bine cantitativ demonstrarea teoremei 13.11 în cea a lui Katz și Lindell Introducere în criptografia modernă (3^rd ediție) (sau aproape echivalent, teorema 19.1 din Dan Boneh și Victor Shoup, disponibil gratuit Un curs absolvent de criptografie aplicată). Dovada este despre schema de identificare Schnorr pentru un grup generic $\mathcal G$ de ordin prim $q=\lvert\mathcal G\rvert$ si generator $g\in\mathcal G$, pentru revendicare:

Dacă problema logaritmului discret este dificilă în raport cu $\mathcal G$, atunci schema de identificare Schnorr este sigură.

Schema merge:

• Prover (P) extrage cheia privată $x\gets\mathbb Z_q$, calculează și publică cheia publică $y:=g^x$, cu integritatea asumată.
• La fiecare identificare:
  1. Prover (P) trage $k\gets\mathbb Z_q$, calculează și trimite $I:=g^k$
  2. Verificatorul (V) desenează și trimite $r\gets\mathbb Z_q$
  3. Prover (P) calculează și trimite $s:=r\,x+k\bmod q$
  4. Verificatorul (V) verifică dacă $g^s\;y^{-r}\;\overset?=\;I$

Dovada dată este prin contrapunere. Presupunem un algoritm PPT $\mathcal A$ asta, dat $y$ dar nu $x$, se identifică cu succes cu probabilitate de nedispariție. Construim următorul algoritm PPT $\mathcal A'$:

1. Alerga $\mathcal A(y)$, care are voie să interogheze și să observe transcrieri oneste $(I,r,s)$, înainte de a ajunge la pasul următor.
2. Când $\mathcal A$ iesiri $I$, alege $r_1\gets\mathbb Z_q$ și dă-i $\mathcal A$, care răspunde cu $s_1$.
3. Alerga $\mathcal A(y)$ a doua oară cu aceeași bandă aleatoare și transcrieri sincere și când iese (la fel) $I$, alege $r_2\gets\mathbb Z_q$ cu $r_2\ne r_1$ si da $r_2$ la $\mathcal A$.

   În cele din urmă, $\mathcal A$, răspunde cu $s_2$.

4. Calcula $x:=(r_1-r_2)^{-1}(s_1-s_2)\bmod q$, rezolvarea DLP.

Să spunem că pasul 2 se finalizează cu probabilitate $\epsilon$. Am înțeles că dovada cărții stabilește pasul 3 complet cu probabilitate cel puțin $\epsilon^2-1/q$, de ce pasul 4 a rezolvat DLP-ul, de ce $\epsilon^2$ apare și de ce avem nevoie de un mare $q$ a aborda asta.

Putem ajunge la o reducere mai convingătoare cantitativ a DLP?

Lucrurile nesatisfăcătoare sunt: ​​the $\epsilon^2$, ceea ce se poate traduce printr-o probabilitate scăzută de succes. Am dori o reducere în care probabilitatea de succes crește liniar cu timpul petrecut, pentru o probabilitate scăzută. De asemenea, probabilitatea de succes este obținută în medie pe ansamblu $y\în\mathcal G$, nu pentru o anumită problemă DLP.

Pentru a concretiza prima problemă: dacă $\mathcal A$ reușește cu probabilitate $\epsilon=2^{-20}$ în $1$ în al doilea rând, dovada spune că putem rezolva un DLP mediu cu probabilitate ca $2^{-40}$ în $2$ secunde. Asta nu este direct util, chiar dacă l-am putea transforma în probabilitate $1/2$ în $2^{40}$ secunde (11 secole). Vrem probabilitate $1/2$ în $2^{21}$ secunde (25 de zile).

Răspuns provizoriu

Aceasta este încercarea mea, de critică. Eu susțin că putem rezolva orice DLP anume $G$ cu timpul preconizat $2t/\epsilon$ (și cu probabilitate $>4/5$ în timp $3t/\epsilon$), plus timp pentru sarcinile identificate, presupunând un algoritm $\mathcal A$ care identifică în timp pentru o cheie publică aleatorie $t$ cu probabilitate de nedisparare $\epsilon$, și $q$ suficient de mare pentru a putea reduce atingerea unei anumite valori într-o alegere aleatorie în $\mathbb Z_q$.

Dovada revendicată:

Mai întâi construim un nou algoritm $\mathcal A_0$ că la intrare descrierea setării $(\mathcal G,g,q)$ și $h\în\mathcal G$

• alege uniform aleatoriu $u\gets\mathbb Z_q$
• calculează $y:=h\;g^u$
• rulează algoritmul $\mathcal A$ cu intrare $y$ servind ca cheie publică aleatorie
• oricând $\mathcal A$ solicită o transcriere sinceră $(I,r,s)$
  • alege uniform aleatoriu $r\gets\mathbb Z_q$ și $s\gets\mathbb Z_q$
  • calcula $I:=g^s\;y^{-r}$
  • livra $(I,r,s)$ la $\mathcal A$, care se distinge de o transcriere sinceră pentru cheia publică $y$
• dacă $\mathcal A$ iesiri $I$ în timpul de rulare alocat $t$, făcând o încercare de autentificare
  • (notă: vom reporni de aici)
  • alege uniform aleatoriu $r\gets\mathbb Z_q$ și îl transmite către $\mathcal A$
  • dacă $\mathcal A$ iesiri $s$ în timpul de rulare alocat $t$
    • verificări $g^s\;y^{-r}\;\overset?=\;I$ iar dacă da, ieșiri $(u,r,s)$
    • în caz contrar, se anulează fără rezultat.

Algoritm $\mathcal A_0$ este un algoritm PPT care pentru orice intrare fixă $h\în\mathcal G$ are la fiecare alergare probabilitate $\epsilon$ la ieșiri $(u,r,s)$, deoarece $\mathcal A$ se desfăşoară în condiţiile definitorii $\epsilon$.

Facem un nou algoritm $\mathcal A_1$ asta la intrarea in setare $(\mathcal G,g,q)$ și $h\în\mathcal G$

• Alergați în mod repetat $\mathcal A_0$ cu acea intrare până când iese $(u,r_1,s_1)$. Fiecare alergare are probabilitate $\epsilon$ pentru a reuși, astfel încât acest pas este de așteptat să necesite $t/\epsilon$ timpul care curge $\mathcal A$.
• Repornire $\mathcal A_0$ de la punctul de repornire notat (echivalent: reluați-l de la început cu aceeași intrare și bandă aleatorie până la punctul de repornire, cu o nouă aleatorie după punctul de repornire), până când iese $(u,r_2,s_2)$. Fiecare alergare are cel puțin probabilitate $\epsilon$ a reuși (dovada rezultă din acea teoremă privind probabilitatea nedescrescătoare de succes a unui algoritm Încerc să cer o referință pentru), astfel încât acest pas este de așteptat să necesite nu mai mult de $t/\epsilon$ timpul care curge $\mathcal A$.
• În cazul (presupus copleșitor de probabil). $r_1\ne r_2$, calculați și ieșiți $z:=s_1-s_2-u\bmod q$.

În acest rezultat, ambele runde de $\mathcal A_0$ care a produs $(u,r_1,s_1)$ și $(u,r_2,s_2)$ au verificat $g^{s_i}\;y^{-{r_i}}=I$ cu $y=h^u$ Pentru același $u$ și $I$ acea $\mathcal A_0$ determinat, iar cel $h$ am dat la intrare de $\mathcal A_1$. Prin urmare $\mathcal A_1$ găsite $z$ cu $h=g^z$, rezolvând astfel DLP-ul pentru arbitrare $h$. Este timpul de rulare estimat petrecut în $\mathcal A$ este cel mult $2t/\epsilon$, iar restul face $\mathcal O(\log(q))$ operațiuni de grup pentru fiecare rulare de $\mathcal A$ și fiecare transcriere sinceră de care are nevoie.

$\lfloor3/\epsilon\rfloor$ rulează de $\mathcal A$ sunt suficiente pentru ca cel puțin doi dintre ei să reușească cu probabilitate mai bine decât $1-4\,e^{-3}>4/5$: vezi acest complot de $1-(1-\epsilon)^{\lfloor3/\epsilon\rfloor}-\lfloor3/\epsilon\rfloor\,\epsilon\,(1-\epsilon)^{\lfloor3/\epsilon\rfloor-1} $

$ \newcommand{\sR}{\mathcal{R}} \newcommand{\sG}{\mathcal{G}} \newcommand{\sB}{\mathcal{B}} $

Aceasta este cea mai bună analiză riguroasă cu care am putut veni -- folosește lema de împărțire, dar am decis să o introduc oricum în speranța că cineva o va găsi utilă (vă rugăm să nu ezitați să subliniați orice erori).

(Analiza de mai jos este pentru o instanță DLP fixă, dar ideile pot fi extinse cu ușurință.)

Lema de împărțire [Lema 1, PS]: Lăsa $\sG\subseteq\sR_-\times\sR_+$ fie astfel încât $$\Pr_{(\rho_-,\rho_+)\in\sR_-\times\sR_+}[(\rho_-,\rho_+)\in\sG]\geq\epsilon.$$ Pentru orice $\beta<\epsilon$, defini $$\sB:=\left\{(\rho_-,\rho_+)\in\sR_-\times\sR_+:\Pr_{\rho_+'\in\sR_+}[(\rho_-,\ rho_+')\în\sG\right\}.$$ Următoarea reținere:

1. $\Pr[\sB|\sG]\geq\beta/\epsilon$ și
2. $\Pr_{\rho_+'\in\sR_+}[(\rho_-,\rho_+')\in\sG|(\rho_-,\rho_+)\in\sB]\geq \epsilon-\ beta.$

Aici, $\sG$ este setul de monede aleatorii „bune” în sensul în care acestea duc la succesul adversarului și $\sB\subseteq\sG$ este subsetul de monede aleatoare „mai bune”, în sensul că o reîntoarcere și reluare folosind aceste monede este probabil să aibă succes. Prima concluzie a lemei este că o monedă bună este mai bună cu probabilitate cel puțin $\beta/\epsilon$ iar a doua concluzie este că reeșantionarea unei monede mai bune va duce la o monedă bună cu cel puțin probabilitate $\epsilon-\beta$.

Analiza primei părți a reducerii este simplă: probabilitatea ca toate $1/\epsilon$ execuțiile eșuează este $1-(1-\epsilon)^{1/\epsilon}$. Să presupunem, wlog, că ultima execuție a reușit. Să notăm monedele folosite de adversar în această execuție înainte și după punctul de derulare $\rho_-$ și $\rho_+$, respectiv. După lema de împărțire, probabilitatea ca cel puțin una dintre reluări să reușească este $$\frac{\beta}{\epsilon}\left((1-(1-(\epsilon-\beta))^{1/\epsilon}\right).$$ Aici, $\beta/\epsilon$ este probabilitatea ca ultima execuție (despre care știm că este bună) să fie mai bună (prin concluzie $1$) și $(\epsilon-\beta)$ în interiorul bretelor este probabilitatea ca o reeșantionare a monedei mai bune să conducă la o monedă bună (prin concluzie $2$).

Pentru a optimiza ecuația de mai sus, setați $\beta=\epsilon(1-\epsilon)$ (care este aproape de $\epsilon$). Acest lucru generează o probabilitate de succes $(1-\epsilon)(1-(1-\epsilon^2)^{1/\epsilon})$.

[PS]: Pointcheval și Stern, Argumente de securitate pentru semnăturile digitale și semnăturile oarbe, JoC 2000.

Lasă-mă să încerc să răspund la întrebarea ta :)

În primul rând, conform descrierii dvs. (nu aveam cartea pe care ați menționat-o), această întrebare aparține teoriei securității demonstrabile. Ideea generală de securitate demonstrabilă este că: presupunând că există un algoritm/adversar A poate rupe o schemă bazată pe cripto cu o probabilitate deloc neglijabilă e, apoi un simulator/provocator S poate rezolva o instanță a problemei matematice, schema se bazează pe interacțiunea cu A cu probabilitate deloc neglijabilă **e' <= e** determinat de probabilitatea de defectare.

Mai mult, procesul de verificare a securității ar trebui să se bazeze pe un joc/model de atac al adversarului, cum ar fi IND-CPA, EUF-CMA etc., care definește abilitățile unui adversar în acel model special. Deci, cred că dovada oferită în partea dvs. de întrebare s-a bazat pe EUF-DCMA, iar dovada din partea dvs. de răspuns s-a bazat pe EUF-CMA.

Într-o lume de simulare creată de simulator, simulatorul poate avea unele super putere, prin care ar putea rezolva o instanță a unei probleme dificile în lumea reală, în funcție de rezultatul adversarului. Superputerea din dovada de mai sus este așa-numita derulează înapoi, un faimos lema de simulare înapoi, pentru a extrage valoare secretă din rezultatele adversarului.

Acum, să aruncăm o privire la dovada originală. Pentru a rezolva DLP, simulatorul se derulează înapoi A la pasul 3. Asta este A a fost rulat de două ori, deci probabilitatea de extragere cu succes X este $e'=e*e=e^2$, deoarece acesta este un eveniment continuu. În plus, în pasul 3, probabilitatea de $r_1=r_2$ este 1 USD/q$. Deci, trebuie să facem și minus 1 USD/q$ pentru a stabili probabilitatea finală de succes $e'=e^2-1/q$.

Procesul de dovadă a securității este un fel de experiment de gândire, cum ar fi Pisica lui Schroedinger (poate nu este adecvat), nu avem nevoie să-l punem într-un experiment real. Este suficient să reducem doar securitatea schemei la una sau mai multe probleme grele.

Procesul de probă pe care l-ați susținut este foarte interesant și nu îmi cunoaștem. A fost o minunată carte pentru a înțelege în continuare securitatea demonstrabilă.