GGH krypteringsskema

GGH-krypteringsskemaet ( Eng. Goldreich–Goldwasser–Halevi ) er et asymmetrisk kryptografisk system baseret på gitter . Der er også en GGH-signaturordning .

Kryptosystemet er baseret på løsninger på problemet med at finde den korteste vektor og problemet med at finde den nærmeste vektor . GGH-krypteringsskemaet, udgivet i 1997 af videnskabsmændene Oded Goldreich , Shafi Goldwasser og Shai Halevi , bruger en envejs hemmelig indtastningsfunktion , fordi givet ethvert gittergrundlag er det nemt at generere en vektor tæt på et gitterpunkt. For eksempel at tage et gitterpunkt og tilføje en lille fejlvektor. For at vende tilbage fra fejlvektoren til gitterets begyndelsespunkt er der brug for et særligt grundlag. I 1999 foretog Phong Q. Nguyen [1] en forfining af det originale GGH-krypteringsskema, som gjorde det muligt at løse fire af de fem GGH-problemer og få delvis information om sidstnævnte. Mens GGH kan være sikker med visse valg af parametre, forbliver dens effektivitet i forhold til traditionelle public-key kryptosystemer diskutabel [2] . Ofte kræver kryptering en høj gitterdimension, mens nøglestørrelsen vokser tilnærmelsesvis kvadratisk i forhold til gitterstørrelsen [2] .

Det eneste gitterskema, der kan håndtere høje dimensioner, er NTRU [3] .

Algoritme

GGH inkluderer en offentlig nøgle og en privat nøgle [4] . Den private nøgle er bunden af gitteret med en unimodulær matrix . $B$ $L$ $U$

Den offentlige nøgle er en anden base af formularens gitter . $L$ $B'=UB$

Lad meddelelsesrummet M bestå af vektorer , der hører til intervallet . $(m_{1},...,m_{n})$ $-M<m_{i}<M$

Kryptering

Givet en besked , en fejl og en offentlig nøgle : $m=(m_{1},...,m_{n})$ $e$ $B'$

v=\sum m_{i}b_{i}'

I matrixnotation:

v=m\cdot B'

Det skal huskes, at det består af heltalsværdier, er et gitterpunkt og derfor også er et gitterpunkt. Så er chifferteksten: $m$ $b'$ $v$

c=v+e=m\cdot B'+e

Afskrift

For at dekryptere chifferteksten beregnes:

c\cdot B^{-1}=(m\cdot B^{\prime }+e)B^{-1}=m\cdot U\cdot B\cdot B^{-1}+e\cdot B ^{-1}=m\cdot U+e\cdot B^{-1}

For at fjerne , hvis den er lille nok, bruges Babais afrundingsmetode [ 5] . $e\cdot B^{-1}$

Så for at få teksten:

m=m\cdot U\cdot U^{-1}

Sikkerhedsanalyse

Dette afsnit diskuterer flere måder at angribe et kryptosystem på [6] .

Angreb ved afrunding

Afrundingsangrebet er det mest oplagte angreb i dette kryptografiske system, bortset fra brute force angrebet - søgning efter fejlvektoren . Dets essens er at bruge den offentlige nøgle B til at invertere funktionen på samme måde som ved brug af den private nøgle R Nemlig at vide , at du kan beregne . Således kan du finde en vektor . Ved dimensioner under 80 LLL er algoritmen i stand til korrekt at bestemme basen, men startende fra dimensioner 100 og højere er dette angreb værre end en triviel opregning af fejlvektoren. $e.$ $c=B\cdot v+e$ $B^{-1}\cdot c=v+B^{-1}\cdot e$ $d=B^{-1}\cdot e$

Storm angreb

Denne algoritme er en åbenlys forfining af afrundingsangrebet. Her bruger vi den bedste tilnærmelsesalgoritme til det korteste vektorproblem . Især den nærmeste plan-algoritme bruges i stedet for Babai-afrundingsalgoritmen. Det fungerer sådan her. Givet et point og reduceret grundlag c = { } for LLL . Alle affine mellemrum = { + } : } tages i betragtning. For alle er der et hyperplan tættest på punktet . Yderligere projiceres et punkt på det (n - 1)-dimensionelle rum, som er dækket af = { } . Dette giver et nyt punkt og et nyt grundlag = { }. Algoritmen fortsætter nu rekursivt for at finde et punkt i dette (n - 1)-dimensionelle gitter tæt på . Til sidst sætter algoritmen . Denne metode virker meget hurtigere end den forrige. Dens arbejdsbyrde vokser dog også eksponentielt med gitterdimensionen. Eksperimenter viser, at når man bruger LLL som en gitterreduktionsalgoritme, kræves der noget søgetid, startende fra størrelserne 110-120. Angrebet bliver umuligt at starte ved størrelse 140-150. $c$ $B$ ${b_{1}},\dots {b_{n}}$ ${H_{k))$ $k\cdot {b_{n))$ $\sum _{i=0}^{n-1}{a_{i}}\cdot {b_{i}}$ ${a_{i}}\in {\mathcal {R}}$ $k\in {\mathcal {Z))$ ${H_{k))$ $c$ $B$ ${b_{1}},\dots {b_{n}}$ $ck\cdot {b_{n))$ $c'$ $B'$ ${b_{1}},\dots {b_{n}}$ $p'$ $c'$ $p=p'+k\cdot {b_{n))$

Injektionsangreb

En anden måde, der ofte bruges til at tilnærme problemet med at finde den nærmeste vektor, er at indlejre n basisvektorer og et punkt, for hvilket det er nødvendigt at finde et tæt gitterpunkt i et (n + 1)-dimensionelt gitter $c$

$B'={\begin{pmatrix}\vdots &\vdots &\vdots &\cdots &\vdots \\c&b_{1}&b_{2}&\cdots &b_{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&0&0&\cdots &0\end{pmatrix}}$

Gitterreduktionsalgoritmen bruges derefter til at finde den korteste ikke-nul vektor i , i håb om at de første n elementer i denne vektor vil være de nærmeste punkter til . Eksperimenter udført på dette angreb (ved at bruge LLL som et værktøj til at finde korteste vektorer) indikerer, at det virker op til dimensioner omkring 110-120, hvilket er bedre end afrundingsangrebet, som bliver værre end triviel søgning efter dimension 100. $L(B')$ $c$

Estimering af effektiviteten af angreb [7]

Estimeret angreb ved afrunding

Lad fem lukkede baser skabes i hver dimension. Hver basis er valgt som = + rand , hvor I er identitetsmatrixen og rand er en kvadratisk matrix , hvis medlemmer er valgt ensartet fra området . For hvert grundlag beregnes værdien = , hvor er den euklidiske norm for den største række , og . For hver lukket basis genereres fem åbne baser $n$ ${R_{i))$ $4\left|{\sqrt {n}}\right|\cdot I$ $(\pm 4)$ $(\pm 4)$ ${-4,...,4}$ ${R_{i))$ ${\sigma _{i))$ ${\displaystyle ({\gamma _{i)){\sqrt {8\ln({2n}/{\varepsilon }))))^{-1))$ ${\gamma _{i))$ ${R_{i}}^{-1}$ $\varepsilon =10^{-5}$ ${R_{i))$ ${B_{ij))$

${work-load_{ij))$ = , hvor er den dobbelte ortogonalitetsdefekt: hvor angiver rækken af matrixen . $({\pi }e)^{n/2}$ $\cdot {\sigma _{i}^{n))$ $\cdot {\frac {orth-defekt^{*}({B_{ij)))}{det|{B_{ij}}|}}$ $orth-defekt^{*}$ $orth-defect^{*}(B)=|det(B)|\cdot \prod _{i}\|{\hat {b_{i))}\|,$ ${\displaystyle {\hat {b_{i))))$ $B^{{-1}}$

Assault score

For at evaluere overfaldsangrebet blev de samme åbne og lukkede baser brugt som ved angrebet ved afrunding.

Injection attack evaluering

Da man ikke kan tale om "arbejdsbelastningen" ved et injektionsangreb, blev den maksimale værdi (relateret til fejlvektoren), som dette angreb virker for, målt. Til disse eksperimenter blev de samme lukkede baser og åbne baser brugt som ved de to foregående angreb. Derefter blev hver åben basis brugt til at evaluere funktionen på flere punkter ved hjælp af flere forskellige værdier og kontrolleret, om injektionsangrebet genopretter den krypterede besked. ${\sigma}$ ${R}$ ${B_{ij))$ $\sigma$

Eksempel

Lad gitteret med base og dets gensidige være : $L\delsæt \mathbb {R} ^{2}$ $B$ $B^{{-1}}$

B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}

B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}

Med en unimodulær matrix:

U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}

U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}

Vi får:

B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}

Lad meddelelsen og vektoren af fejl Derefter chifferteksten: $m=(3,-7)$ $e=(1,-1).$

c=mB'+e=(-104,-79)

For at dekryptere skal du:

cB^{-1}=\venstre({\frac {-104}{7)),{\frac {-79}{3}}\right)

Dette rundes op til $(-15,-26).$

Og beskeden gendannes med:

m=(-15,-26)U^{-1}=(3,-7).\,

Kilder og videre læsning

Oded Goldreich, Shafi Goldwasser og Shai Halevi. Offentlig nøgle kryptosystemer fra gitterreduktionsproblemer. I CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, side 112-131, London, UK, 1997. Springer-Verlag.
Phong Q. Nguyen. Kryptoanalyse af Goldreich-Goldwasser-Halevi Cryptosystem fra Crypto '97. I CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, side 288-304, London, UK, 1999. Springer-Verlag.

Noter

↑ Phong Q. Nguyen. Kryptoanalyse af Goldreich-Goldwasser-Halevi Cryptosystem fra Crypto '97. . - S. 1-17 . Arkiveret fra originalen den 16. juli 2018.
↑ 1 2 Phong Q. Nguyen. Kryptoanalyse af Goldreich-Goldwasser-Halevi Cryptosystem fra Crypto '97. S. - 1-2. . Arkiveret fra originalen den 16. juli 2018. (ubestemt)
↑ Phong Q. Nguyen. Kryptoanalyse af Goldreich-Goldwasser-Halevi Cryptosystem fra Crypto '97. S. - 1. . Arkiveret fra originalen den 16. juli 2018. (ubestemt)
↑ Oded Goldreich, Shafi Goldwasser og Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problemer]. - S. 112-114 . Arkiveret 4. maj 2019.
↑ Phong Q. Nguyen. Kryptoanalyse af Goldreich-Goldwasser-Halevi Cryptosystem fra Crypto '97. . - S. 4 . Arkiveret fra originalen den 16. juli 2018.
↑ Oded Goldreich, Shafi Goldwasser og Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problemer]. — S. 122-124 . Arkiveret 4. maj 2019.
↑ Oded Goldreich, Shafi Goldwasser og Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problemer]. - S. 127-130 . Arkiveret 4. maj 2019.