Criptarea complet homomorfă este o criptare care permite unui anumit text cifrat π 1 ,…, π t oricui (nu doar deținătorul cheii) să obțină textul cifrat al oricărei funcție dorită f( π 1 ,…, π t ) , atâta timp cât aceasta funcția poate fi calculată eficient.
Ideea criptării complet homomorfe a fost propusă pentru prima dată în 1978 de către inventatorii algoritmului criptografic cu cheie publică RSA , Ronald Rivest și Adi Shamir , împreună cu Michael Dertouzos . [1] Cu toate acestea, în etapele inițiale, încercările de a crea un criptosistem cu o astfel de criptare nu au avut succes. Timp de mulți ani nu a fost clar dacă criptarea complet homomorfă a fost chiar posibilă, deși încercările de a crea un astfel de sistem au fost făcute în mod repetat. Deci, de exemplu, criptosistemul propus în 1982 de Shafi Goldwasser și Silvio Micali avea un nivel destul de ridicat de putere criptografică, dar era doar parțial homomorf (omomorf doar în plus) și putea cripta doar un bit. [2] Un alt sistem de criptare homomorf aditiv a fost propus în 1999 de Pascal Peillet . [3] O descoperire în dezvoltarea criptării complet homomorfe vine în 2009, când Craig Gentry a propus pentru prima dată o variantă a unui criptosistem complet homomorf bazat pe criptografie în rețea. [4] De atunci, au apărut un număr mare de lucrări care propun o modificare a criptosistemului Gentry pentru a-i îmbunătăți performanța.
Criptarea complet homomorfă este o primitivă criptografică care este o funcție de criptare care satisface cerința suplimentară de homomorfism cu privire la orice operațiuni pe texte clare. Funcția de criptare , unde m este textul simplu, k este cheia de criptare, este omomorfă în raport cu operațiunea pe texte clare, dacă există un algoritm eficient , care, după ce a primit ca intrare orice pereche de criptograme de forma , produce o criptogramă astfel încât la decriptare se va obține textul simplu [5] . Un homomorfism în raport cu operația este definit în mod similar .
În timp ce criptosistemele parțial homomorfe sunt homomorfe în cadrul unei singure operații de text simplu (fie adunare, fie înmulțire), sistemele complet homomorfe suportă homomorfismul în ambele operații (atât adunarea, cât și înmulțirea) [6] . Adică, sunt îndeplinite următoarele condiții pentru ei:
Mai mult, homomorfismul cu privire la operațiile de adunare și înmulțire este suficient pentru ca sistemul să fie complet homomorf. [6]
Criptosistemul creat de Craig Gentry , bazat pe criptografia latice, a descris prima construcție posibilă pentru un sistem complet homomorf. Schema lui Gentry a susținut operațiile de adunare și înmulțire prin text cifrat, ceea ce vă permite să construiți inele pentru a implementa orice calcul arbitrar.
Construcția începe cu o schemă de criptare aproape homomorfă , care este potrivită doar pentru calcularea polinoamelor de grade mici peste date criptate. (Acest lucru este limitat de faptul că textul cifrat conține ceva zgomot, care crește odată cu operațiile de adunare și multiplicare pe textul cifrat, până când zgomotul face rezultatul neinteligibil.) Gantry a arătat cum să modifice schema și să o facă flexibilă . Adică, cu ajutorul recriptării, a reușit să elimine zgomotul acumulat și să mai efectueze cel puțin o operațiune pe textul cifrat.
Adică, schema îi permite să-și evalueze algoritmul de decriptare pentru cel puțin încă o operație. La urma urmei, el a arătat că orice schemă flexibilă poate fi convertită într-o schemă complet homomorfă prin auto-încorporare recursiv.
Pentru o schemă Gentry „zgomotoasă”, procedura de modificare a unei scheme „flexibile” „actualizează” efectiv textul cifrat, aplicând acestuia o procedură de decriptare homomorfă, obținând astfel un nou text care criptează aceleași date ca înainte, dar cu mai puțin zgomot. Prin „actualizarea” periodică a textului cifrat, când se atinge un nivel ridicat de zgomot, este posibil să se efectueze un număr arbitrar de operații asupra acestuia fără interferențe. Gentry a justificat securitatea schemei sale cu două probleme: problema de complexitate a criptografiei în cel mai rău caz pe rețelele ideale și problema sumei subsetului.
Lucrarea de doctorat a lui Gentry [7] are o descriere mai detaliată.
În ciuda performanței lor, textele cifrate din schema Gentry rămân compacte, deoarece lungimile lor nu depind de complexitatea funcției care este calculată pentru datele criptate. Dar schema este nepractică din cauza creșterii dramatice a dimensiunii textului cifrat și a costurilor de calcul în funcție de nivelul de protecție. Damien Schechli și Ron Steinfeld au introdus o serie de optimizări și îmbunătățiri, [8] și, ulterior, Nigel Smart cu Frederic Verkauteren , [9] [10] și Craig Gentry cu Shai Halevi , [11] [ 12] a prezentat primele implementări de lucru ale unei scheme de criptare Gentry complet homomorfe.
În 2010, Martin van Dijk , Craig Gentry , Shai Halevi și Weedon Vaikuntanahan au prezentat un al doilea sistem complet homomorf [13] . A folosit multe dintre principiile criptosistemului lui Gentry, dar nu a necesitat rețele perfecte . În schimb, ei au arătat că este posibil să se înlocuiască componenta homomorfă pe rețelele ideale cu o schemă homomorfă simplă care să folosească numere întregi. Această schemă este conceptual mai simplă decât schema Gentry, dar are parametri similari în ceea ce privește homomorfismul și eficiența.
Componenta homomorfă din lucrarea lui Dyck este similară cu schema de criptare prezentată de Leviel și Naccaha în 2008 [14] , și similară cu cea prezentată de Brahm Cohen în 1998 [15] . Dar metoda lui Cohen nu este omomorfă în ceea ce privește operația de adunare. Schema Leviela-Naccahi acceptă doar operația de adunare și poate fi modificată pentru a suporta un număr mic de operații de înmulțire. Multe îmbunătățiri și optimizări ale circuitului au fost prezentate într-o serie de lucrări de Jen-Sebastian Corona , Tankrid Lepointe , Avradip Mandala , David Nakkhi și Mehdi Tibuhi [16] [17] [18] [19] .
Mai multe tehnici noi au fost dezvoltate din 2011-2012 de Zvik Brakerski , Craig Gentry , Widon Vaikuntanahan și alții. Aceste evoluții au condus la un număr de criptosisteme complet homomorfe mai eficiente. Printre ei:
Securitatea majorității schemelor se bazează pe dificultatea rezolvării problemei de învățare a erorilor . Doar în schema LVT, protecția este implementată pe o variantă a sarcinii de calcul NTRU . Toate aceste sisteme, spre deosebire de schemele anterioare, au o creștere mai lentă a zgomotului în timpul calculelor homomorfe. Ca urmare a optimizării suplimentare făcute de Craig Gentry , Shai Haveli și Nigel Smart , a fost obținut un criptosistem cu complexitate asimptotică aproape optimă : [25] [26] [27] Aceste optimizări se bazează pe tehnica Smart-Vercauteren, care vă permite să comprimați un set de variabile text într-un singur text cifrat și să lucrați asupra acestor variabile într-un singur flux . [10] Multe progrese de la a doua generație de sisteme complet homomorfe au fost, de asemenea, utilizate în criptosisteme pe numere întregi. [18] [19]
Zvika Brakerski și Vidon Vaikuntanahan au observat că pentru o serie de scheme, criptosistemul GSW prezintă o ușoară creștere a nivelului de zgomot și, prin urmare, o eficiență mai mare și o securitate mai mare. [28] Jakob Alperin-Sheriff și Chris Peikert au descris mai târziu o tehnică eficientă de criptare la flexibilitate care utilizează acest tip de schemă. [29] Dar acest tip de transformare nu este compatibil cu metodele de comprimare a textului cifrat și astfel nu i se pot aplica optimizări Gentry-Sahai-Waters [25] .
Toate criptosistemele de a doua generație de până acum urmează bazele designului schemei Gentry, și anume, folosesc un criptosistem aproape homomorf, cu un nivel mare de creștere a zgomotului, și apoi îl convertesc într-un criptosistem complet homomorf, modificându-l într-o schemă flexibilă.
Prima implementare a unei criptări complet homomorfe a fost schema Gentry-Halevi implementată pe baza schemei Gentry de mai sus. [12] I-au luat 30 de minute pentru a finaliza o operațiune simplă de biți. După apariția celei de-a doua generații de criptosisteme, această implementare a devenit învechită.
Există multe implementări ale sistemelor aproape homomorfe de a doua generație în literatură. Implementat de către Gentry, Haveli și Smart (GHS) [27] variația criptosistemului BGV, [20] a arătat rezultatul în 36 de ore la calcularea unei scheme complexe (implementând criptarea AES ). Folosind tehnici de compresie a textului cifrat, această implementare ar putea recalcula aceeași schemă pe 54 de intrări diferite în aceleași 36 de ore, obținând astfel un rezultat de 40 de minute per intrare. Calculul circuitului AES a fost ales ca ghid pentru mai multe lucrări ulterioare, [18] [30] [31] unde a fost posibil să se reducă semnificativ timpul de calcul la 4 ore, în timp ce se petreceau 7 secunde pe intrare.
Două implementări ale celei de-a doua generații de criptosisteme sunt disponibile pentru uz public:
Ambele biblioteci sunt implementări ale criptării complet homomorfe. HElib arată un rezultat în 5-10 minute pentru conversia textului cifrat comprimat de la aproximativ 1000 de caractere în flexibil. [34] FHEW convertește text cifrat necomprimat în text cifrat flexibil în aproximativ 1/2 secundă pe bit. [35] La sfârșitul anului 2014, o implementare actualizată a HElib a arătat un rezultat de 4 minute pentru a calcula schema AES pentru 120 de fluxuri de intrare, atingând astfel o viteză specifică de 2 secunde pe flux. [32]
Schema de criptare complet homomorfă propusă de Gentry poate fi luată în considerare folosind exemplul de calcule din . [36]
Procesul de criptare a datelor poate fi reprezentat după cum urmează:
1. Se alege un număr impar arbitrar , care este un parametru secret. Lasă .
2. Un număr este compilat astfel încât , unde este un număr arbitrar. Aceasta înseamnă că .
3. În procesul de criptare, fiecăruia i se atribuie un număr , unde este ales în mod arbitrar. Astfel, . Este ușor de observat că și, prin urmare, atacatorul va putea determina doar paritatea ieșirii de criptare.
Să fie cunoscute numărul criptat și secretul . Apoi, procesul de decriptare a datelor ar trebui să conțină următorii pași:
1. Decriptare folosind parametrul secret : , unde se numește zgomot și .
2. Obținerea bitului criptat original :
Să fie doi biți și li se atribuie o pereche de numere și . Lăsați parametrul secret să fie luat și datele criptate: și .
Se calculează suma acestor numere:
Pentru suma acestor numere, mesajul decriptat va fi suma biților originali .
Dar fără a ști , nu este posibilă decriptarea datelor: .
Operația de înmulțire se verifică în același mod:
Este necesar să se aplice procedura de decriptare rezultatelor obținute, rezultând următoarele:
.
Utilizarea acestei scheme de criptare complet homomorfă în scopuri practice nu este în prezent posibilă, deoarece, ca urmare a calculelor, eroarea acumulată atinge rapid valori suficient de mari [36] . Este chiar posibil ca datele să nu poată fi deloc decriptate corect. Acest lucru se va întâmpla dacă valoarea erorii depășește valoarea . În încercarea de a evita o astfel de problemă, Gantry a dezvoltat un mecanism de auto-corecție a textului cifrat (bootstrapping), care, din cauza imposibilității sale din cauza creșterii prea rapide a volumului de text cifrat, nu și-a găsit o aplicație largă. Este posibil să se rezolve această problemă, dar pentru a realiza sarcina stabilită este necesar să se dezvolte algoritmi de calcul mai complecși sau să se limiteze numărul de operații pe date. [36]
Una dintre cele mai importante aplicații ale criptării complet homomorfe este efectuarea diferitelor operații matematice asupra datelor stocate pe o stocare în cloud la distanță . Utilizarea unei astfel de scheme de criptare va face posibilă crearea unui serviciu cloud securizat capabil să efectueze diverse operațiuni asupra datelor utilizatorului fără a ști ce fel de date este vorba.
De exemplu, utilizatorul a criptat unele dintre datele sale și le stochează pe o stocare în cloud de la distanță. Dacă utilizatorul intenționează să schimbe cumva aceste date, el poate fie să încredințeze serverului cheia sa secretă și, în consecință, să acceseze toate informațiile sale secrete, fie să descarce datele criptate pe computerul său, să le decripteze, să facă calculele necesare și să trimită înapoi la server. Dar nici una, nici alta nu este optimă. În primul caz, este imposibil să se excludă scurgerea probabilă a datelor și accesul acestora către terți, în al doilea caz, timpul petrecut pentru efectuarea tuturor operațiunilor necesare poate fi prea mare. În plus, clientul poate pur și simplu să nu aibă resursele de calcul necesare pentru a efectua calculele de care are nevoie. [6]
De asemenea, conform companiei internaționale de cercetare IDC , care studiază piața globală a tehnologiei informației și telecomunicațiilor , multe companii sunt neîncrezători în tehnologiile cloud, asociind cu acestea, în primul rând, mari probleme privind securitatea datelor stocate. Iar compania independentă de cercetare Portio Research a publicat date conform cărora 68% dintre șefii diferitelor companii IT europene nu au încredere în astfel de servicii. Deci, de exemplu, șeful G Data Security Labs , Ralph Bentzmuller, a vorbit despre serviciile cloud după cum urmează: „Dacă nu doriți ca datele dvs. să devină publice, nu le stocați în stocarea în cloud”. Prin urmare, problema creării unei stocări securizate în cloud folosind o schemă de criptare a datelor complet homomorfă este în prezent destul de acută.. [37] .
Criptarea complet homomorfă este folosită în motoarele de căutare care necesită o „căutare privată”, adică o căutare în care serverul nu știe nimic despre conținutul interogării de căutare și returnează rezultatul utilizatorului în formă criptată. În plus față de domeniile deja acoperite, schemele de criptare complet homomorfe pot fi aplicate sistemelor de vot electronic , cum ar fi atunci când sunt utilizate semnături oarbe . [6]