Kryptosystem Gentry

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 19. december 2017; checks kræver 78 redigeringer .

Gentry-kryptosystemet (fra efternavnet på skaberen Craig Gentry) er den første mulige konstruktion for et fuldt homomorfisk kryptosystem baseret på gitterkryptografi . Det blev først foreslået af Craig Gentry i 2009 [1] og var genstand for hans doktorafhandling. Gentry-skemaet understøtter additions- og multiplikationsoperationer på chiffertekst, som giver dig mulighed for at bygge ringe til at implementere alle vilkårlige beregninger. Efterfølgende havde den mange forbedringer og modifikationer for at forbedre dens ydeevne.

Beskrivelse af algoritmen

Skemaet bruger [2] ideelle gitter J i kæder af polynomier modulo . Den hermitiske normalform af et ideelt gitter har formen [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]$ , hvor og r er roden til modulo d. $d=det(J)$ $f_{n}(x)$

Nøglegenerering [2]

Der vælges et vilkårligt n-dimensionelt heltalsgitter v, hvor hvert input er valgt tilfældigt som et t-bit tal. Med denne vektor v er polynomiet formelt defineret , såvel som den tilsvarende rotationsmatrix: $v_{i}$ ${\displaystyle 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]$

Det omvendte for beregnes modulo , det vil sige et polynomium af højst n-1, hvilket er . Så matrixen $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]$

er det omvendte af , dvs. hvor er identitetsmatrixen. $V$ $V*W=const*I$ $jeg$

Det er også verificeret, at den hermitiske normalform for har formen angivet ovenfor, nemlig at alle kolonner undtagen den venstre danner identitetsmatrixen. I dette tilfælde kan hele matrixen opnås ved hjælp af elementerne r og d. $V$ $V$

Den offentlige nøgle vil være matrixen givet af tallene r og d. Den private nøgle vil være to polynomier . $V$ $(v,w)$

Kryptering [2]

Lad det være påkrævet at kryptere lidt ${\displaystyle {m\in(0,1)))$

Der er bit b og offentlig nøgle V ved indgangen. Støjvektoren er valgt , hvis komponenter har værdierne 0,1,-1. Derefter beregnes vektoren , og chifferteksten beregnes med formlen [2] $u$ ${\displaystyle a=2*u+b*e_{1))$ $c=a{\bmod {V}}=a-([a*V^{-1}]*V)$

Her, for en basis V af rummet L og en given vektor c, bruges udtrykket til at betegne en vektor, således at [2] $c{\bmod {V}}$ $c'\in P(V)$ $cc'\in L$

Dekryptering [2]

Indgangen har en vektor C og matricerne V og W. Den oprindelige bit b opnås som et resultat af operationen:

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

Homomorfi [2]

Kryptering er homomorf med hensyn til additions- og multiplikationsoperationer. For at udføre addition eller multiplikation af chiffertekster er det nødvendigt at udføre disse operationer i basis V

Udholdenhed [3]

Gentry begrundede sikkerheden ved sit skema med to problemer: Problemet med kompleksiteten af det værste tilfælde af kryptografi på ideelle gitter og problemet med summen af delmængder. Begge problemer er -hårde, så systemets stabilitet er reduceret til et -hårdt problem. $NP$ $NP$

Fejl

En væsentlig ulempe ved denne ordning er, at udførelse af beregninger fører til akkumulering af fejl [4] , og efter at den overstiger , bliver det umuligt at dekryptere meddelelsen. En af løsningerne på dette problem er at genkryptere dataene efter et vist antal operationer, men denne mulighed reducerer udførelsen af beregninger og kræver konstant adgang til den hemmelige nøgle [3] . $s$

Forenklet diagram af Gentry

Et skema anses kun for homomorf med hensyn til additionsoperationen [4] .

Nøglegenerering

Der vælges et nummer , hvoraf modulo vil fungere. $n$
En hemmelig nøgle vælges - et tilfældigt tal, meget større , sådan at gcd $sk$ $n$ ${(sk,n)=1}$
En offentlig nøgle vælges - et sæt af store tal, således at , hvor er et lille tilfældigt tal, er et vilkårligt tilfældigt tal. $pk$ $[a_{1},..a_{i}]$ $a_{i}=r*sk+e*n$ $r$ $e$

Kryptering

Indtastningen indeholder teksten, der skal krypteres, og den offentlige nøgle. Chifferteksten vil være summen af et vilkårligt antal elementer i den offentlige nøgle og klarteksten.

dekryptering

Indtastningen indeholder en chiffertekst og tal og . Resten af opdelingen af chifferteksten med og efter beregnes sekventielt . Resultatet bliver den originale besked. $n$ $sk$ $n$ $sk$

homomorfi

For at få summen af tekster og , er det nok at tilføje chifferteksterne og udføre dekrypteringsoperationen. Virkelig: $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}}$

Fordelen ved denne ordning er den lette implementering og lave ressourcekrav. Ulemperne omfatter et begrænset sæt offentlige nøgler og kun delvis homomorfi.

Implementering af Smart og Wertcauteren

Det første forsøg på at implementere Gentry-ordningen blev lavet i 2010 af Smart og Werkauteren [5] . Til implementering valgte de et skema, der bruger ideelle gitter til en simpel determinant. Sådanne strukturer er repræsenteret af to heltal (uanset deres størrelse). Smart og Wertkauteren foreslog en dekrypteringsmetode, hvor den hemmelige nøgle er et enkelt heltal. Således lykkedes det forskerne at implementere et homomorft homogent kredsløb, men de kunne ikke implementere Gentry-teknikken i tilfælde af tilstrækkeligt store parametre, og derfor lykkedes det ikke at opnå et belastningsbart og fuldstændig homomorft kredsløb.

Den største hindring i denne implementering var vanskeligheden ved at generere nøgler til homogene skemaer: Først og fremmest skal skemaer generere et meget stort antal "kandidater" for at finde en nøgle, for hvilken determinanten er enkel - op til kandidater, når der arbejdes med dimensionsstrukturer . Derudover, selv efter at have fundet den optimale variant, er kompleksiteten af at beregne den hemmelige nøgle svarende til denne struktur ens, i det mindste for gitter af dimension . Af disse grunde har videnskabsmænd ikke været i stand til at generere dimensionelle nøgler . Derudover estimerede Smart og Vercauteren, at dekrypteringspolynomiet vil have en grad på flere hundrede, og dette kræver brug af et gitter af mindst dimension til proceduren med deres parametre , hvilket væsentligt overstiger beregningsevnerne for nøglegenereringsproceduren [ 2] . ${n^{1,5))$ $n$ ${{\tilde {O}}(n^{2,5}})}$ $n$ ${n>2048}$ ${n=2^{27))$ ${\displaystyle {(\ca. 1,3\ gange 10^{8))))))$

Gentrys fuldt homomorfe skema

I 2011 præsenterede Craig Gentry sammen med Shai Halevi [2] en praktisk implementering af et fuldt homomorfisk krypteringsskema, der ligner det, der blev brugt i tidligere værker af Smart og Wertcauteren. Hovedoptimeringen består i en nøglegenereringsmetode til den grundlæggende relativt homomorfe kryptering, der ikke kræver fuld polynomiel inversion. Dette reducerer den asymptotiske kompleksitet fra til ved arbejde med dimensionsgitter (og reducerer i praksis beregningstiden fra mange timer til flere minutter). ${{\tilde {O}}(n^{2,5}})}$ ${{\tilde {O}}(n^{1,5}})}$ $n$

Noter

↑ Craig Gentry. "ET FULDSTÆNDIG HOMOMORPHISK ENKRYPNINGSORDNING" Arkiveret 5. februar 2017 på Wayback Machine En afhandling indsendt til afdelingen for datalogi og udvalget for kandidatstuderende ved Standford University, 2009.
↑ 1 2 3 4 5 6 7 8 9 10 Craig Gentry og Shai Halevi. "Implementering af Gentry's Fully-Homomorphic Encryption Scheme" Arkiveret 22. december 2017 på Wayback Machine IBM research.
↑ 1 2 Trubey A.I. HOMOMORFOR KRYPTERING: CLOUD COMPUTING SIKKERHED OG ANDRE APPLIKATIONER (GENNEMGANG). Informatik. 2015;(1):90-101.
↑ 1 2 Alumyan A.S., Glazunov I.A., Tishin V.V. "Homomorf kryptering" Arkiveret 22. december 2017 på Wayback Machine -artikel til den XXI internationale videnskabelige og praktiske konference "Scientific Community of Students: INTERDISCIPLINARY RESEARCH" (Rusland, Novosibirsk, 18. maj 2017)
↑ NP SmartF. Vercauteren. "Fuldstændig homomorf kryptering med relativt små nøgle- og chiffertekststørrelser" Arkiveret 22. december 2017 på Wayback Machine , 2010.