Protocol de calcul confidențial

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 27 noiembrie 2017; verificările necesită 7 modificări .

În criptografie , un protocol de calcul confidențial (de asemenea, secure, secure sau secret multi-party calcul, de exemplu, secure multi-party calcul ) este un protocol criptografic care permite mai multor participanți să efectueze un calcul care depinde de datele secrete de intrare ale fiecăruia dintre ei. , în așa fel încât niciun participant nu a putut obține informații despre intrarea secretă a altcuiva. Pentru prima dată, problema calculului confidențial a fost ridicată de Andrew Yao în 1982 în articolul [1] . Doi milionari, Alice și Bob, vor să afle care dintre ei este mai bogat, în timp ce nu vor să dezvăluie valoarea exactă a averii lor. Yao a propus în articolul său o modalitate originală de a rezolva această problemă, care mai târziu a devenit cunoscută drept problema milionarilor . Mult mai târziu, în 2004, Yehuda Lindell și Benny Pinkas au oferit o dovadă riguroasă din punct de vedere matematic a corectitudinii protocolului lui Yao în [2] . Problema calculului confidențial este strâns legată de problema partajării secretelor .

Declarație formalizată a problemei

N participanți p 1 , p 2 , …, p N participă la calculul confidențial . Fiecare participant are date secrete de intrare d 1 , d 2 , …, respectiv d N. Participanții doresc să găsească valoarea F(d 1 , d 2 , …, d N ) , unde F este o funcție calculabilă a N argumente cunoscute de toți participanții . Se presupune că printre participanți vor exista infractori semi-cinsti , adică cei care respectă cu fidelitate protocolul, dar încearcă să obțină informații suplimentare din orice date intermediare.

Cerințe de securitate

Cerințele de securitate pentru protocoalele de calcul confidențiale au de obicei cerințe de securitate diferite în funcție de situație. Iată principalele cerințe.

Confidențialitate. Niciunul dintre participanți nu ar trebui să poată primi mai multe informații decât le-au fost prescrise.
Corectitudine. Fiecare participant trebuie să fie garantat că va primi datele corecte.
Informații garantate. Participanții nu ar trebui să poată împiedica alți participanți să obțină rezultatul.

Un exemplu de soluție la problema milionarilor

Lăsați milionarii Alice și Bob să dorească să afle a cui avere este mai mare fără a dezvălui valoarea exactă a averilor lor. Pentru certitudine, să presupunem că Alice are i milion și Bob are j , unde 1<i și j<10 . În primul rând, Alice și Bob vor avea nevoie de un criptosistem puternic cu cheie publică , cum ar fi RSA [3] . Fie E a o funcție de criptare arbitrară pentru cheia a , iar D a funcția de decriptare a cheii private pentru cheia publică a . Să fie cheia publică a lui Alice. Apoi protocolul arată astfel:

Bob alege un număr întreg aleatoriu x din N biți și calculează în mod confidențial k=E a (x) ;
Bob îi trimite lui Alice un număr k-j+1 ;
Alice consideră confidențial valorile y u =D a (k-j+u) pentru u=1,2,…,10 ;
Alice alege un număr prim aleator p din N/2 biți, astfel încât numerele z u =y u mod(p) să difere cu cel puțin 2 modulo p pentru tot u și trimite numărul p lui Bob;
Alice trimite numerele z 1 , z 2 , …, z i urmate de numerele z i+1 +1, …, z 10 +1 ; numerele sunt luate modulo p;
Bob, care știe câți bani are ( j ), compară numărul j cu numărul x mod p ales în primul pas, iar dacă sunt egali, atunci Bob trage concluzia că i ⩾ j , iar i < j altfel;
Bob raportează rezultatul lui Alice.

Se poate observa că protocolul vă permite să determinați fără ambiguitate a cui stare este mai mare și, în același timp, participanții nu pot afla stările unul altuia.

Implementări

Există două abordări diferite pentru implementarea protocolului. Prima abordare se bazează de obicei pe partajarea secretă și lucrează la reprezentarea funcției calculate sub forma unui circuit aritmetic ( ing. circuit aritmetic ), ca, de exemplu, în BGW (Ben-Or, Goldwasser și Wigderson) [ 4] și CCD (Chaum, Crepeau și Damgard [5] . Această abordare este de obicei aplicată atunci când se știe că majoritatea participanților sunt sinceri (ceea ce este posibil doar dacă numărul participanților este mai mare de doi). O altă abordare este reprezentarea funcției ca o diagramă logică . Această abordare a fost folosită de Andrew Yao la construirea unui circuit distorsionat (circuit distorsionat în engleză ) [ 6] , precum și în protocolul GMW (Goldreich, Micali și Wigderson) [7] .

Metoda schemei aritmetice este mai potrivită pentru efectuarea operațiunilor de adunare și înmulțire (unde participanții au părți ale secretului, iar secretul poate fi recreat doar dacă se primesc informații de la fiecare dintre participanți), dar este slab potrivită pentru efectuarea operațiilor de comparare. Această abordare a obținut un mare succes în proiectul SIMAP [8] .

Metoda circuitului logic efectuează adunări și înmulțiri cu o eficiență mai mică, dar poate efectua cu ușurință operații binare, cum ar fi comparațiile. Această a doua abordare, pe care se bazează sistemul cu două mâini al lui Andrew Yao , a fost implementată de Mulchy în sistemul fairplay [9 ] . Acest sistem oferă, de asemenea, capacitatea de a implementa funcționalitatea necesară, reprezentată de un limbaj de programare de nivel înalt sub forma unei bucle logice, care este apoi interpretată de mediul de execuție și executată în siguranță. Există, de asemenea, un sistem „FairplayMP” [10] , care este o extensie a „Fairplay” în cazul a mai mult de doi participanți. Un avantaj semnificativ al sistemelor bazate pe metode cu circuite logice este că acestea se realizează într-un număr constant de schimburi de informații, în timp ce avantajul sistemelor bazate pe circuite aritmetice este capacitatea de a efectua operații aritmetice (adunare și înmulțire) foarte rapid.

Exemplu de protocol

Pentru simplitate, să presupunem că doi participanți participă la calcul, adică N=2 , iar participanții trebuie să calculeze funcția F .

Să reprezentăm funcția F sub forma unui circuit logic , adică vom reprezenta datele de intrare ale funcției F în formă binară, iar funcția în sine este implementată folosind operațiile AND, OR și NOT. Apoi, biții tuturor argumentelor funcției F sunt alimentați la intrarea circuitului logic , iar circuitul însuși este format din porți logice ȘI, SAU și NU, iar la ieșire produce rezultatul funcției F în format binar.
Participantul p 1 generează pentru fiecare fir al circuitului logic două numere aleatoare diferite k 0 u k 1 . Numerele reprezintă zero și, respectiv, unu criptat pe acel fir.
Participantul p 1 creează un tabel de calcul criptat pentru fiecare schemă. Pentru o poartă OR binară, un astfel de tabel ar arăta astfel:

Firul de intrare w 1	Firul de intrare w 2	Cablul de ieșire w 3	Tabel de calcul criptat
$k_{1}^{0}$	$k_{2}^{0}$	$k_{3}^{0}$	$c_{1}=E_{k_{1}^{0}}(E_{k_{2}^{0}}(k_{3}^{0}))$
$k_{1}^{0}$	$k_{2}^{1}$	$k_{3}^{1}$	$c_{2}=E_{k_{1}^{0}}(E_{k_{2}^{1}}(k_{3}^{1}))$
$k_{1}^{1}$	$k_{2}^{0}$	$k_{3}^{1}$	$c_{3}=E_{k_{1}^{1}}(E_{k_{2}^{0}}(k_{3}^{1}))$
$k_{1}^{1}$	$k_{2}^{1}$	$k_{3}^{1}$	$c_{4}=E_{k_{1}^{1}}(E_{k_{2}^{1}}(k_{3}^{1}))$

Aici înseamnă rezultatul criptării valorii x cu cheia k , și respectiv - decriptarea textului cifrat y cu cheia k . Ar trebui să alegeți o schemă de criptare simetrică , care are o proprietate suplimentară: dacă încercați să decriptați textul cu cheia greșită, algoritmul returnează o eroare. $E_{k}(x)$ $D_{k}(y)$

Semnificația acestui tabel este următoarea: dacă cunoaștem valorile criptate ale semnalului k 1 u k 2 pe firele de intrare ale supapei w 1 u w 2 , respectiv, atunci putem calcula valoarea semnalului criptat calculând valoarea pentru tot i =1...4 . În trei cazuri din patru, ar trebui să apară o eroare, iar în al patrulea rămas, vom obține valoarea criptată k 3 a semnalului la ieșirea porții. $d_{i}=D_{k_{2}}(D_{k_{1}}(c_{i}))$

Participantul p 1 trimite circuitul logic și tabelele de calcul criptate pentru toate circuitele către participantul p 2 .
Participantul p 1 trimite participantului p 2 valorile criptate ale semnalelor de intrare pentru acele intrări care corespund datelor de intrare ale participantului p 1 .
Pentru fiecare fir de intrare w i corespunzător datelor de intrare p 2 , participantul p 1 trimite un număr participantului p 2 utilizând protocolul de transfer uitabil , unde b i este valoarea bitului secret de date de intrare al participantului p 2 . Cu un astfel de transfer, participantul p 1 nu cunoaște valoarea lui b i . Deoarece pentru fiecare fir propriile numere aleatorii, care sunt zero și unu, au fost selectate anterior aleatoriu, atunci participantul p 2 nu va putea afla care număr este zero și care este unul pentru firele de intrare ale participantului p 1 și, prin urmare, nu va putea afla datele introduse ale participantului p 1 . $k_{i}^{b_{i)}$
Acum membrul p 2 are un circuit logic criptat și valori criptate ale tuturor firelor de intrare. Acesta calculează în formă criptată (așa cum este descris mai sus) toate porțile circuitului una după alta și apoi transmite rezultatul criptat participantului p 1 .
Participantul p 1 decriptează rezultatul și îl raportează participantului p 2 .

Protocoale utilizate

Transmiterea uită poate fi o componentă importantă a protocolului de calcul confidențial .
Virtual Participant Protocol - Un protocol care ascunde identitatea participanților [11] .
Protocoalele de sumă sigure permit participanților colaboratori să calculeze unele caracteristici din informațiile lor individuale fără a dezvălui aceste informații unul altuia [12] .

Aplicație practică

Votul electronic . De exemplu, fiecare participant poate vota pentru sau împotrivă, atunci rezultatul votului a n participanți va fi funcția F(x 1 , …,x n ) , unde x i poate lua valorile 0 (împotrivă) și 1 (pentru).
Licitații electronice. Fiecare participant licitează x i , iar funcția F(x 1 , …,x n ) returnează numărul maximului x i .
Statistici. Să presupunem că studenții vor să-și cunoască nota cea mai bună sau media, fără a-și arăta notele unul altuia.
Baze de date . De exemplu, să presupunem că utilizatorul dorește să interogheze o bază de date și să obțină un răspuns fără a expune interogarea. Proprietarul serverului cu baza de date nu dorește alte informații decât răspunsul la cerere să ajungă la utilizator atunci când face cereri. În acest caz, atât utilizatorul, cât și serverul vor fi participanți la protocolul de calcul confidențial.
Autoritate de certificare distribuită . Să presupunem că trebuie să creați o autoritate de certificare care va emite certificate utilizatorilor, semnându-i cu o cheie secretă. Pentru a proteja cheia, cheia poate fi împărțită între mai multe servere, astfel încât fiecare server să-și păstreze propria parte a cheii. Atunci apare problema: cum să efectuați o operațiune criptografică (în acest exemplu, emiterea unei semnături) fără a transfera toate părțile cheii pe un singur computer. Această problemă este rezolvată prin utilizarea unui protocol de calcul privat, unde intrarea în funcția de calcul privată este părțile cheie și mesajul semnat, iar rezultatul este mesajul semnat.

Note

↑ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164
↑ Yehuda Lindell, Benny Pinkas: A Proof of Yao's Protocol for Secure Two-Party Computation, Cryptology ePrint Archive, Raport 2004/175
↑ Soluție la problema milionarului Arhivat 19 mai 2008.
↑ M. Ben-Or, S. Goldwasser și A. Wigderson. Teoreme de completitudine pentru calcul distribuit non-criptografic tolerant la erori. În al 20-lea STOC, 1-10, 1988.
↑ P. Bogetoft, D. L. Christensen, I. Damgard, M. Geisler, T. Jakobsen, M. Kroigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach și T. Toft. Calculul multipartit securizat are viață. În Criptografia financiară și securitatea datelor – FC 2009
↑ A. Yao. Cum să generați și să schimbați secrete. În 27th FOCS, 162-167, 1986.
↑ Goldreich, S. Micali și A. Wigderson. Cum să joci orice joc mental - O teoremă de completitudine pentru protocoale cu majoritate sinceră. În al 19-lea STOC, 218-229, 1987.
↑ P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. şi T. Toft. O implementare practică a licitațiilor de calcul securizate bazate pe numere întregi cu mai multe părți. În Financial Cryptography and Data Security - FC 2006, Springer-Verlag LNCS 4107, 142-147, 2006.
↑ D. Malkhi, N. Nisan, B. Pinkas și Y. Sella. Fairplay este un sistem de calcul securizat în două părți. În Proc. al 13-lea Simpozion de securitate USENIX, 2004.
↑ A. Ben-David, N. Nisan și B. Pinkas. FairplayMP: un sistem de calcul securizat cu mai multe părți. În Computer and Communications Security - CCS 2008, ACM, 257-266, 2008.
↑ Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (Tipărit) 1611-3349 (Online), ISBN 978-3-642-02616-4 , DOI 10.7803/97803 -642-02617-1
↑ Rashid Sheikh, Brijesh Kumar și Durgesh Kumar Mishra, Privacy Preserving k-secure sum protocols, International Journal of Computer Science and Information Security, ISSN 1947-5500 (Online), Vol.6, No.2, nov. 2009