Dovada bazată pe simulare pentru protocolul de multiplicare al lui Beaver

Înființat

Recent, m-am interesat dovezi bazate pe simulare în contextul calculării securizate în două părți. Am citit câteva capitole de carte (din MPC securizat și partajare secretă și Bazele criptografiei volumul 2), documente (cel mai important Cum să-l simulezi), și postări din schimbul de stive de criptografie, dar încă nu mă simt încrezător în aplicarea tehnicilor de demonstrare bazate pe simulare. Ca prim pas, am considerat un simplu protocol aditiv de partajare a secretelor cu părți semi-oneste. Acolo, părțile vor să-și înmulțească secretele și să folosească triplele Beaver pentru asta, astfel încât protocolul să implice o anumită interacțiune. Îl împărtășesc aici pentru că ar putea fi util pentru alți începători și aș aprecia foarte mult corecții, critici și comentarii.

Protocol de multiplicare

Presupuneți două părți care nu se complică și presupuneți intrările $x,y$ aparțin părților $P_1,P_2$, respectiv. Atunci, $P_1$ calculează acțiunile $x_1\leftarrow \mathbb{Z}_q$, $x_2 = x-x_1\,\mathrm{mod}\,q$, Unde $\leftarrow \mathbb{Z}_q$ denotă eșantionare uniform aleatorie din $\mathbb{Z}_q$, și trimite $x_2$ la $P_2$. Același lucru se întâmplă în mod analog cu $y_1,y_2$ la $P_2$ astfel încât $P_1$ are acces la $x_1,y_1$ și $P_2$ are acces la $x_2,y_2$ dupa acest pas. Pentru a calcula $xy$, părțile folosesc triple Beaver după cum urmează. Înainte de executarea protocolului, eșantionăm $(\alpha,\beta)\leftarrow \mathbb{Z}_q^2$, calculează $\alpha \beta \,\mathrm{mod}\,q = \gamma$ precum si actiunile $\alpha_i,\beta_i,\gamma_i$ cu $i\în\{1,2\}$, și le distribuie părții corespunzătoare. Apoi, $i$-partea a treia calculează \begin{align*} \delta_i=x_i-\alpha_i\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon_i=y_i-\beta_i\,\mathrm{mod}\,q \end{align*} si trimite $\delta_i$ precum și $\epsilon_i$ către cealaltă parte. Ca rezultat, ambele părți pot calcula $$ \delta=\delta_1+\delta_2\,\mathrm{mod}\,q=x-\alpha\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon=\epsilon_1+\epsilon_2\, \mathrm{mod}\,q=y-\beta\,\mathrm{mod}\,q. $$ Cu acestea la îndemână, se obține în sfârșit acțiuni de $z:=z_1+z_2\,\mathrm{mod}\,q$ prin intermediul \begin{align*} z_1=\gamma_1+\delta \beta_1 +\epsilon \alpha_1+\delta\epsilon\,\mathrm{mod}\,q \quad \text{and} \quad z_2=\gamma_2+\delta \beta_2+\epsilon \alpha_2\,\mathrm{mod}\,q. \end{align*} Noi nu dezvăluim $z_1$ sau $z_2$ (chiar daca protocolul pare inutil in acest fel).

Rețineți că $x_2,y_1,\delta_1,\delta_2,\epsilon_1,\epsilon_2$ au fost schimbate și toate aceste cantități sunt numere uniform aleatorii în $\mathbb{Z}_q$. Toate celelalte calcule sunt locale. De aici, trag concluzia că protocolul ar trebui să fie perfect sigur.

Dovada bazată pe simulare (încercare)

Din câte am înțeles, dovezile bazate pe simulare sunt deosebit de atractive pentru protocoale, unde, pe lângă criptare, și calculele și schimbul de date pot dezvălui ceva. Prin urmare, ar trebui să fie potrivit pentru protocolul specificat mai sus.

Să încercăm să demonstrăm mai formal intuiția menționată mai sus (că protocolul este perfect sigur) aplicând ceea ce se găsește în Cum să-l simulezi și MPC securizat și partajare secretă. În primul rând, observăm că protocolul este (aproape) simetric.Prin urmare, ar trebui să fie suficient dacă luăm în considerare numai $P_1$ a fi semi-onest. În continuare, funcționalitatea $f(x,y):=z$ a protocolului $\pi$ este deterministă și satisface corectitudinea (evaluează $z_1+z_2\,\mathrm{mod}\,q$ pentru verificare). În plus, prima componentă a $f(x,y)$ este $f_1(x,y):=z_1$ și introducem punctul de vedere al $P_1$ de \begin{align*} \mathrm{view}_1^{\pi}(x,y):=\left(x,r_1,m_1,m_2,\dots,m_t\right)\in \mathbb{Z}_q^{1\times p }, \end{align*} Unde $r_1$ este continutul de $P_1$banda internă aleatorie a lui și $m_1,m_2,\dots,m_t$ indica mesajele primite. Apoi, o demonstrație bazată pe simulare pentru o securitate perfectă necesită existența unui simulator de timp polinomial probabilistic $S_1$ astfel încât \begin{align*} \{S_1\left(x,f_1(x,y)\right)\}_{x,y\in\{0,1\}^*} \stackrel{\mathrm{perf}}{\equiv} \ {\mathrm{view}_1^{\pi}\left(x,y\right)\}_{x,y\in\{0,1\}^*}. \end{align*} Ar trebui atinsă indistingubilitatea perfectă între aceste ansambluri de probabilitate dacă este posibil $x,y\în\{0,1\}^*$ distanța statistică \begin{ecuație} \label{eq:dist} \Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y)):=\frac{1}{2} \sum_{\boldsymbol{w}\in\ mathbb{Z}_q^{1\times p}} |\mathrm{Pr}(\mathrm{view}_1^{\pi}(x,y)=\boldsymbol{w})-\mathrm{Pr}( S_1(x,f_1(x,y)=\boldsymbol{w})| \end{ecuație} dispare. Începem prin a alerga $\pi$ și, conform definiției de mai înainte, găsiți $$ \mathrm{view}_1^{\pi}\left(x,y\right)=\left(x,x_1,y_1,\alpha_1,\beta_1,\gamma_1,\delta_2,\epsilon_2\right), $$ Unde $x_1$ provine de la $P_1$sursa internă de aleatorie a lui (banda aleatorie), $\alpha_1,\beta_1,\gamma_1$ provin dintr-o sursă auxiliară offline de aleatorie (dar pot fi considerate și mesaje?) și $y_1,\delta_2,\epsilon_2$ sunt mesajele primite de la $P_2$. Rețineți că în afară de $x$ toate aceste cantități sunt uniform aleatoare în $\mathbb{Z}_q$. Mai mult, de la $\mathrm{vizualizare}_1^{\pi}(x,y)$ toate celelalte cantități, că $P_1$ are acces la, poate fi calculat. Prin urmare, $\mathrm{vizualizare}_1^{\pi}(x,y)$ conţine toate $P_1$informatiile lui. Rămâne să găsim un potrivit $S_1$. În acest scop, alegem $$ S_1(x,f_1(x,y))=\left(x,\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\ gamma}_1,\tilde{\delta}_2,\tilde{\epsilon}_2\right) $$ astfel încât fiecare componentă în $(\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\gamma}_1,\tilde{\delta}_2,\tilde{ \epsilon}_2)$ este uniform aleatorie în $\mathbb{Z}_q$ (se pare că nu avem nevoie de ieșire $f_1(x,y)$). În fine, de când $S_1$ poate imita exact distribuțiile fiecărei componente în $\mathrm{vizualizare}_1^\pi$, este ușor să vezi asta $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))=0$ pentru toți $x,y$. Cu alte cuvinte, totul în afară de $x$ (care i se acordă $P_1$) nu se distinge de gunoiul aleatoriu. Astfel, concluzionăm că protocolul este perfect sigur.

Cateva observatii/intrebari

1. În contextul calculelor securizate în două părți, se pare că oricând $\mathrm{vizualizare}_1^\pi$ conține doar variabile aleatoare (cu excepția $x$), putem construi un simulator prin simpla alegere a variabilelor cu aceleași distribuții ca și variabilele aleatoare. Acest lucru face construcția simulatorului trivială.
2. În cazul în care, o variabilă în $\mathrm{vizualizare}_1^\pi$ acționează non-aleatoriu, trebuie să o construim din $x,f_1(x,y)$ pentru a obține un simulator valid. În acest scop, să presupunem $y_1=y$ deoarece $P_2$ a facut o greseala. În mod clar, acest lucru nu este sigur de atunci $P_1$ are acum acces la $x,y$. Cu toate acestea, numai din $x,f_1(x,y)$ nu putem construi $y$ deoarece $x$ nu are nimic de-a face cu $y$ și $f_1(x,y)$ este uniform aleatorie în $\mathbb{Z}_q$ prin constructie. Astfel, acest protocol este nesigur din cauza $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))\neq 0$.
3. Care este motivul de care are nevoie simulatorul $f_1(x,y)$?

1. În contextul calculelor securizate în două părți, se pare că oricând $\mathrm{vizualizare}_1^\pi$ conține doar variabile aleatoare (cu excepția $x$), putem construi un simulator prin pur și simplu alegerea variabilelor cu aceleași distribuții ca și variabilele aleatoare. Acest lucru face construcția simulatorului trivială.

Ce se întâmplă dacă distribuția acelor variabile aleatoare depinde $y$, pe care nu-l cunoști? Cu alte cuvinte, pentru diferite alegeri de $y$, variabilele aleatoare vor fi distribuite diferit.

2. În cazul în care, o variabilă în $\mathrm{vizualizare}_1^\pi$ acționează non-aleatoriu, trebuie să o construim din $x,f_1(x,y)$ pentru a obține un simulator valid. În acest scop, presupune $y_1=y$ deoarece $P_2$ a facut o greseala. În mod clar, acest lucru nu este sigur de cand $P_1$ are acum acces la $x,y$. Cu toate acestea, numai din $x,f_1(x,y)$ nu putem construi $y$ deoarece $x$ nu are nimic de-a face cu $y$ și $f_1(x,y)$ este uniform aleatorie în $\mathbb{Z}_q$ prin constructie. Astfel, acest protocol este nesigur din cauza $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))\neq 0$.

Dacă construiți un simulator pentru $P_1$ atunci te gândești la cazul în care $P_1$ este coruptă şi $P_2$ este sincer. Cinstit $P_2$ nu va face greșeala pe care o menționezi. În schimb, vor eșantiona $y_1$ uniform din $\mathbb{Z}_q$.

Ai dreptate că nu ar fi sigur pentru $P_2$ pentru a alege consecvent $y_1 = y$. De aceea, protocolul nu instruiește părțile cinstite să facă asta.

3. Care este motivul de care are nevoie simulatorul $f_1(x,y)$?

Dacă $P_1$ este corupt și rulează protocolul onest la intrare $x$, iar protocolul este corect, atunci $P_1$ poate ieși corect $f_1(x,y)$ la finalul protocolului. Dacă un corupt $P_1$ poate ieși $f_1(x,y)$ în interacțiunea reală, atunci simulatorul trebuie să fie capabil să iasă $f_1(x,y)$ și în interacțiunea ideală.

Nu știu ce propuneți ca alternativă la obținerea simulatorului $f_1(x,y)$. Dar dacă propuneți ca simulatorul să primească Nu informatii despre $y$, atunci simularea va fi imposibilă din cauza motivului pe care tocmai l-am declarat (cu excepția cazului în care $f_1(x,\cdot)$ ignoră complet $y$ de asemenea).