Criptosistem Gentry

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

Criptosistemul Gentry (de la numele de familie al creatorului Craig Gentry) este prima construcție posibilă pentru un criptosistem complet homomorf bazat pe criptografie în rețea . A fost propus pentru prima dată de Craig Gentry în 2009 [1] și a făcut obiectul tezei sale de doctorat. Schema Gentry acceptă operațiuni de adunare și multiplicare pe text cifrat, ceea ce vă permite să construiți inele pentru a implementa orice calcul arbitrar. Ulterior, a avut multe îmbunătățiri și modificări pentru a-și îmbunătăți performanța.

Descrierea algoritmului

Schema folosește [2] rețele ideale J în lanțuri de polinoame modulo . Forma normală hermitiană a unei rețele ideale are forma [2] : $f_{n}(x)=x^{n}+1$

$HNF(J)=\quad \left[{\begin{array}{ccccc}d&0&0&0&0\\-r&1&0&0&0\\-[r^{2}]_{d}&0&1&0&0\\-[r^{2 }]_{d}&0&0&0&0\\\vdots &&&\ddots &\\-[r^{n-1}]_{d}&0&0&0&1\end{array}}\right]$ , unde și r este rădăcina pentru modulo d. $d=det(J)$ $f_{n}(x)$

Generare cheie [2]

Este aleasă o rețea v-întreg n-dimensională arbitrară , unde fiecare intrare este aleasă la întâmplare ca număr de t-biți. Cu acest vector v, polinomul este definit formal , precum și matricea de rotație corespunzătoare: $v_{i}$ $v(x)=\sum _{i\mathop {=} 0}^{n-1}v_{i}x^{i)$

$V=\quad \left[{\begin{array}{ccccc}v_{0}&v_{1}&v_{2}&&v_{n-1}\\-v_{n-1}&v_{0} &v_{1}&&v_{n-2}\\-v_{n-2}&v_{n-1}&v_{0}&&v_{n-3}\\&&&\ddots &\\-v_{1}&- v_{2}&-v_{3}&&v_{0}\end{array}}\right]$

Inversul pentru se calculează modulo , adică un polinom de gradul cel mult n-1, care este . Apoi matricea $v(x)$ $f_{n}(x)$ $w(x)$ $v(x)*w(x)=const{\bmod {f}}_{n}(x)$

$W=\quad \left[{\begin{array}{ccccc}w_{0}&w_{1}&w_{2}&&w_{n-1}\\-w_{n-1}&w_{0} &w_{1}&&w_{n-2}\\-w_{n-2}&w_{n-1}&w_{0}&&w_{n-3}\\&&&\ddots &\\-w_{1}&- w_{2}&-w_{3}&&w_{0}\end{array}}\right]$

este inversul lui , adică unde este matricea de identitate. $V$ $V*W=const*I$ $eu$

De asemenea, se verifică că forma normală hermitiană pentru are forma indicată mai sus și anume, toate coloanele cu excepția celei din stânga formează matricea de identitate. În acest caz, întreaga matrice poate fi obținută folosind elementele r și d. $V$ $V$

Cheia publică va fi matricea dată de numerele r și d. Cheia privată va fi două polinoame . $V$ $(v,w)$

Criptare [2]

Lăsați să fie necesar să criptați puțin ${m\in(0,1))$

La intrare există bit b și cheia publică V. Se alege vectorul de zgomot , ale cărui componente iau valori 0,1,-1. Apoi se calculează vectorul , iar textul cifrat este calculat cu formula [2] $u$ $a=2*u+b*e_{1)$ $c=a{\bmod {V}}=a-([a*V^{-1}]*V)$

Aici, pentru o bază V a spațiului L și un vector dat c, expresia este folosită pentru a desemna un vector astfel încât [2] $c{\bmod {V}}$ $c'\in P(V)$ $cc'\in L$

Decriptare [2]

Intrarea are un vector C și matrice V și W. Bitul original b este obținut ca rezultat al operației:

$b=a{\bmod {2}}=(c{\bmod {V}}){\bmod {2}}=(c*(L/d)){\bmod {2}}$

Omomorfism [2]

Criptarea este omomorfă în ceea ce privește operațiile de adunare și înmulțire. Pentru a efectua adunarea sau înmulțirea textelor cifrate, este necesar să se efectueze aceste operații în baza V

Rezistenta [3]

Gentry a justificat securitatea schemei sale cu două probleme: problema complexității celui mai rău caz al criptografiei pe rețelele ideale și problema sumei submulților. Ambele probleme sunt -grele, astfel încât stabilitatea sistemului este redusă la o problemă -hard. $NP$ $NP$

Defecte

Un dezavantaj semnificativ al acestei scheme este că executarea calculelor duce la acumularea de erori [4] și, după ce depășește , devine imposibilă decriptarea mesajului. Una dintre soluțiile la această problemă este recriptarea datelor după un anumit număr de operații, totuși, această opțiune reduce performanța calculelor și necesită acces constant la cheia secretă [3] . $p$

Diagrama simplificată a lui Gentry

Se consideră o schemă homomorfă numai în raport cu operația de adunare [4] .

Generarea cheilor

Este selectat un număr , modulo căruia va funcționa schema. $n$
Se alege o cheie secretă - un număr aleatoriu, mult mai mare , astfel încât gcd $sk$ $n$ ${(sk,n)=1}$
Se alege o cheie publică — un set de numere mari astfel încât , unde este un număr aleator mic, este un număr aleator arbitrar. $pk$ $[a_{1},..a_{i}]$ $a_{i}=r*sk+e*n$ $r$ $e$

Criptare

Intrarea conține textul de criptat și cheia publică. Textul cifrat va fi suma unui număr arbitrar de elemente ale cheii publice și textul simplu.

decriptare

Intrarea conține un text cifrat și numere și . Restul împărțirii textului cifrat la și la este calculat secvenţial . Rezultatul va fi mesajul original. $n$ $sk$ $n$ $sk$

homomorfism

Pentru a obține suma textelor și , este suficient să adăugați textele cifrate și să efectuați operația de decriptare. Într-adevăr: $m_{{1}}$ $m_{{2}}$ ${D(E(m_{1},pk)+E(m_{2},pk))=D(m_{1}+m_{2}+\sum _{i\mathop {=} 0 }^{n}C_{i}pk_{i})=D(m_{1}+m_{2}+C_{1}^{'}sk+C_{2}^{'}n)=m_{ 1}+m_{2}}$

Avantajul acestei scheme este ușurința de implementare și cerințele reduse de resurse. Dezavantajele includ un set finit de chei publice și doar homomorfism parțial.

Implementarea Smart și Wertcauteren

Prima încercare de implementare a schemei Gentry a fost făcută în 2010 de către Smart și Werkauteren [5] . Pentru implementare, au ales o schemă care folosește rețele ideale pentru un determinant simplu. Astfel de structuri sunt reprezentate de două numere întregi (indiferent de mărimea lor). Smart și Wertkauteren au propus o metodă de decriptare în care cheia secretă este un singur întreg. Astfel, oamenii de știință au reușit să implementeze un circuit omogen omomorf, dar nu au putut implementa tehnica Gentry în cazul unor parametri suficient de mari și, prin urmare, nu au reușit să obțină un circuit încărcat și complet omomorf.

Principalul obstacol în această implementare a fost dificultatea de a genera chei pentru scheme omogene: în primul rând, schemele trebuie să genereze un număr foarte mare de „candidați” pentru găsirea unei chei pentru care determinantul este simplu - până la candidați atunci când se lucrează cu structuri de dimensiune. . În plus, chiar și după găsirea variantei optime, complexitatea calculării cheii secrete corespunzătoare acestei structuri este egală, cel puțin pentru rețelele de dimensiune . Din aceste motive, oamenii de știință nu au reușit să genereze chei dimensionale . În plus, Smart și Vercauteren au estimat că polinomul de decriptare va avea un grad de câteva sute, iar acest lucru necesită utilizarea unei rețele de cel puțin dimensiune pentru procedura cu parametrii lor , care depășește semnificativ capacitățile de calcul ale procedurii de generare a cheilor . 2] . ${n^{1,5)}$ $n$ ${{\tilde {O}}(n^{2,5}})}$ $n$ ${n>2048}$ ${n=2^{27))$ ${(\aproximativ 1,3\times 10^{8)}))$

Schema complet homomorfă a lui Gentry

În 2011, Craig Gentry, împreună cu Shai Halevi, au prezentat [2] o implementare practică pentru o schemă de criptare complet homomorfă, similară cu cea folosită în lucrările anterioare de Smart și Wertcauteren. Optimizarea principală constă într-o metodă de generare a cheilor pentru criptarea de bază relativ homomorfă care nu necesită inversarea polinomială completă. Acest lucru reduce complexitatea asimptotică de la până la când lucrați cu rețele dimensionale (și în practică reduce timpul de calcul de la multe ore la câteva minute). ${{\tilde {O}}(n^{2,5}})}$ ${{\tilde {O}}(n^{1,5}})}$ $n$

Note

↑ Craig Gentry. „A FULLY HOMOMORPHIC ENCRYPTION SCHEME” Arhivat 5 februarie 2017 la Wayback Machine O disertație depusă la departamentul de informatică și la comisia pentru studenții absolvenți ai Universității Standford, 2009.
↑ 1 2 3 4 5 6 7 8 9 10 Craig Gentry și Shai Halevi. „Implementarea Schemei de criptare complet homomorfă a lui Gentry” Arhivat la 22 decembrie 2017 la cercetarea IBM Wayback Machine .
↑ 1 2 Trubey A.I. CRIPTARE HOMOMORFĂ: SECURITATE CLOUD COMPUTING ȘI ALTE APLICAȚII (REVIZIE). Informatica. 2015;(1):90-101.
↑ 1 2 Alumyan A.S., Glazunov I.A., Tishin V.V. „Criptarea homomorfă” Arhivată 22 decembrie 2017 la articolul Wayback Machine pentru a XXI-a Conferință internațională științifică și practică „Comunitatea științifică a studenților: CERCETARE INTERDISCIPLINARĂ” (Rusia, Novosibirsk, 18 mai 2017)
↑ NP SmartF. Vercauteren. „Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes” Arhivat 22 decembrie 2017 la Wayback Machine , 2010.