Întrebare despre securitatea rău intenționată în protocolul folosind OT

Studiam un protocol care folosea un OT și dintr-o dată îmi dau seama că nu reușesc să-mi imaginez cum un protocol care folosea un OT poate fi securizat rău intenționat.

Să presupunem că avem un protocol P care utilizează un OT ca subrotocol. Să presupunem că se folosește OT $N$ ori. Fiecare OT are intrare $x_{0,i}$, $x_{1,i}$, Unde $i$ denotă $i-$a ista a VT, de la 1 la $N$. Este rezonabil să presupunem că, pentru fiecare situație, receptorul alege bit $0$ sau $1$ în funcție de intrarea sa (acesta este de exemplu cazul unui protocol Yao, unde pentru fiecare poartă receptorul cere 0 dacă intrarea sa este 0 sau 1 în caz contrar).

Acum să presupunem că expeditorul din OT este rău intenționat și decide, a priori, să se schimbe $x_{0,N}$ cu altceva. Ar putea fi o valoare aleatorie, valoarea $x_{1,N}$ sau orice altceva. Avem trei posibilități

1. Avortarea protocolului. Atunci expeditorul știe că în timpul ultimului OT receptorul a cerut 0.
2. Protocolul nu se anulează și intrarea este într-adevăr corectă. Expeditorul știe acum că în timpul ultimului OT, destinatarul a cerut 1.
3. Protocolul nu se întrerupe, intrarea este greșită și părțile sunt capabile să o detecteze. Expeditorul știe acum că în timpul ultimului OT receptorul a cerut 0.
4. Protocolul nu se întrerupe, intrarea este greșită, dar părțile nu sunt capabile să o detecteze. Apoi expeditorul poate face în mod arbitrar ca protocolul să scoată valori diferite față de cea prescrisă.

Dacă comportamentul este unul dintre primele trei, expeditorul poate schimba fiecare OT în acest fel și a făcut-o $\frac{1}{2^N}$ probabilitatea de a învăța toată cererea fără a merge detectat, că din moment ce $N$ este un parametri fix nu este de neglijat (cu atât mai mult dacă $N$ este mic). În celelalte cazuri, receptorul învață că expeditorul este rău intenționat, dar acest lucru nu îl împiedică pe receptor să învețe ceva.

Dacă comportamentul este ultimul, nu reușesc să înțeleg cum un astfel de protocol ar putea fi considerat „securizat”, deoarece este foarte ușor pentru un atacator să efectueze un atac „DoS”, în care fiecare ieșire este lipsită de sens.

În cazul protocolului Yao, să presupunem că expeditorul setează ultimul OT $X_{0,N}, X_{0,N}$. Cum putem preveni asta? Dacă protocolul „merge prost”, atunci expeditorul știe că ultimul bit al lui Bob este 0. Este uriaș, nu?

Și nu iau în considerare cazul simetric: ce se întâmplă dacă receptorul în loc să întrebe conform regulii, întreabă la întâmplare? Din câte înțeleg, acest comportament nu este luat în considerare în timpul probei de securitate, greșesc?

Am pierdut ceva? Sunt aceste considerații în afara domeniului de aplicare și permitem acest tip de comportament? Poate presupunem că expeditorul stabilește întotdeauna $x_0$ și $x_1$ în mod corect?

Există o mulțime de întrebări împachetate aici - pentru a răspunde complet la toate ar fi nevoie de un tutorial complet despre MPC securizat rău intenționat. Voi încerca să mă concentrez doar pe imaginea de ansamblu.

În general, dacă există o „valoare corectă” pe care expeditorul OT ar trebui să o folosească ca intrare OT, atunci da, protocolul trebuie să fie foarte atent. De obicei, există o „valoare corectă”, deoarece orice altă valoare ar determina întreruperea receptorului. Deci, valorile „incorecte” din OT vor provoca întreruperi pe baza intrării OT a receptorului - scurgerea de informații despre acele intrări OT!

Există câteva moduri de a face față acestui lucru. Iată cele mai ușor de înțeles:

• Protocolul clasic 2PC cu circuit deformat al Lindell-Pinkas 2007 face următoarele. Să presupunem că vrem cu adevărat să facem un OT pentru a selecta una dintre cele două etichete de fir $x_0, x_1$ bazat pe intrarea circuitului receptorului $b$. Să presupunem că receptorul poate verifica dacă o etichetă de fir este validă sau nu. Când receptorul întrerupe din cauza vederii unei etichete de fir nevalidă, scurge intrarea în circuit! Lindell & Pinkas abordează acest lucru modificând circuitul deranjat, astfel încât receptorul să introducă o partajare secretă $b = b_1 \oplus \cdots \oplus b_\lambda$ de intrarea sa adevărată $b$. Circuitul deformat va XOR apoi aceste acțiuni pentru a le recupera $b$ și apoi procedați ca de obicei. Deci acum, în loc de un OT pentru acest fir de intrare a circuitului, există $\lambda$ OT pentru că am crescut artificial numărul de intrări în circuit. Să presupunem că expeditorul OT trișează primul $k < \lambda$ OT-uri. Intrările receptorului la acestea mai întâi $k$ OT-urile sunt un set de acțiuni secrete, dar mai puține decât pragul de acțiuni, deci sunt distribuite independent de intrarea privată $b$! În acest caz, receptorul se va opri pur și simplu cu probabilitate $1 - 2^{-k}$, independent de intrarea lor. Dacă expeditorul OT trișează în toate $\lambda$ OT, apoi receptorul se anulează cu probabilitate fie 1, fie $1-2^{-\lambda}$, cu probabilitatea în funcție de intrarea lor privată! -- dar, deoarece acestea sunt neglijabil apropiate, nu constituie de fapt o scurgere de informații.

• Protocolul ZK al Jawurek, Kerschbaum, Orlandi se bazează și pe circuite confuze. Ei fac un OT tipic al etichetelor de fir, unde intrarea receptorului OT este martorul lor privat ZK. Ei structurează cu atenție protocolul, astfel încât expeditorul OT să poată dezvălui public ambii dintre intrările sale OT la un moment dat --- aceasta necesită o variantă de OT numită „OT angajat”. Practic, verificatorul calculează un „răspuns final” despre circuitul eronat, care scurge informații despre intrarea lor privată dacă a existat vreo înșelăciune în OT. Deci, în loc să trimiteți doar acest răspuns final, acesta comite la el. Apoi expeditorul OT dezvăluie toate intrările sale OT pentru a dovedi că nu a existat nicio înșelăciune. Dacă receptorul OT este convins, atunci își poate deschide propriul angajament față de „răspunsul final”.

• Uneori puteți proiecta protocolul astfel încât să nu existe o intrare incorectă a OT. Iată o modalitate simplă de a verifica dacă două șiruri private $x = x_1 \cdots x_n$ și $y = y_1 \cdots y_n$ sunt egali (inspirat din protocolul PSI al Pinkas-Schneider-Zohner). Alerga $n$ OTS de valori aleatoare, deci $i$OT are intrări $r_{i,0}$ și $r_{i,1}$. Receptorul OT folosește biții de intrare $x$ ca biți de alegere OT și învață valorile formei $r_{i, x_i}$. Ei pot calcula valoarea $R_x = H(x, r_{1,x_1}, r_{2,x_2}, \ldots, r_{n,x_n} )$, Unde $H$ este un oracol aleatoriu. Expeditorul OT are propria sa intrare privată $y$, și știe toate $r_{i,b}$ valorile. Deci ei pot calcula o valoare $R_y = H( y, r_{1,y_1}, r_{2,y_2}, \ldots, r_{n,y_n} )$ și trimiteți-l la receptorul OT. Dacă $R_x = R_y$ atunci $x$ și $y$ au fost egali; in caz contrar $x$ și $y$ au fost diferiți (și $R_y$ pare aleatoriu receptorului). Cum poate un expeditor OT corupt să trișeze? Ar putea trimite $H$ unora alte lucruri (adică includeți ceva care nu este egal cu oricare $r_{i,b}$ ca intrare la $H$). Dar asta ar fi pur și simplu garanție că receptorul va concluziona că „corzile nu s-au potrivit” -- indiferent ce $x$ ei țin. Acest lucru este ușor de gestionat de către simulator.

Deci avem trei abordări diferite la nivel înalt pentru problema despre care ați întrebat:

• Acest protocol aranjează ca biții de alegere OT ai receptorului să fie efectiv independenți de datele lor private --- deci dacă înșelăciunea duce la o întrerupere, probabilitatea acelui abandon nu depinde de intrarea privată a receptorului OT.

• Receptorului OT i se oferă o modalitate de a detecta înșelăciunea, astfel încât să poată opri protocolul înainte de a se vedea oricare dintre consecințele negative ale înșelăciunii.

• Celelalte părți ale protocolului pur și simplu nu au consecințe negative dacă expeditorul OT alege să acționeze în mod inconsecvent cu intrările lor OT.

Cu siguranță există și alte abordări inteligente, dar acestea sunt primele care mi-au venit în minte.

ce se întâmplă dacă receptorul în loc să întrebe conform regulii, întreabă la întâmplare? Din câte înțeleg, acest comportament nu este luat în considerare în timpul probei de securitate, greșesc?

În majoritatea protocoalelor bazate pe OT, biții de alegere OT ai receptorului sunt o codificare directă a intrării lor în protocolul principal. Acesta este cu siguranță cazul în cele 3 exemple de mai sus. Utilizarea biților de alegere OT „greșiți” este exact echivalent cu alegerea unei intrări diferite pentru protocolul principal, iar acest lucru nu este considerat un atac pentru securitate rău intenționată.