GGH krypteringsschema

GGH-krypteringsschemat ( Eng. Goldreich–Goldwasser–Halevi ) är ett asymmetriskt kryptografiskt system baserat på gitter . Det finns också ett GGH-signaturschema .

Kryptosystemet bygger på lösningar på problemet att hitta den kortaste vektorn och problemet med att hitta den närmaste vektorn . GGH-krypteringsschemat, publicerat 1997 av forskarna Oded Goldreich , Shafi Goldwasser och Shai Halevi , använder en enkelriktad hemlig ingångsfunktion , eftersom det är lätt att generera en vektor nära en gitterpunkt, givet varje gitterbas. Till exempel att ta en gitterpunkt och lägga till en liten felvektor. För att återgå från felvektorn till gittrets initiala punkt behövs en speciell grund. 1999 gjorde Phong Q. Nguyen [1] en förfining av det ursprungliga GGH-krypteringsschemat, vilket gjorde det möjligt att lösa fyra av de fem GGH-problemen och få del av information om det senare. Medan GGH kan vara säker med vissa val av parametrar, är dess effektivitet gentemot traditionella kryptosystem med offentlig nyckel fortfarande diskutabel [2] . Ofta kräver kryptering en hög gitterdimension, medan nyckelstorleken växer ungefär kvadratiskt med avseende på gitterstorleken [2] .

Det enda gitterschemat som kan hantera höga dimensioner är NTRU [3] .

Algoritm

GGH inkluderar en publik nyckel och en privat nyckel [4] . Den privata nyckeln är basen av gittret med en unimodulär matris . $B$ $L$ $U$

Den publika nyckeln är en annan bas för formulärets gitter . $L$ $B'=UB$

Låt meddelandeutrymmet M bestå av vektorer som hör till intervallet . $(m_{1},...,m_{n})$ $-M<m_{i}<M$

Kryptering

Givet ett meddelande , ett fel och en offentlig nyckel : $m=(m_{1},...,m_{n})$ $e$ $B'$

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

I matrisnotation:

v=m\cdot B'

Man måste komma ihåg att den består av heltalsvärden, är en gitterpunkt och därför också är en gitterpunkt. Då är chiffertexten: $m$ $b'$ $v$

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

Avskrift

För att dekryptera chiffertexten beräknas:

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}

För att ta bort , om den är tillräckligt liten, används Babais avrundningsmetod [ 5] . $e\cdot B^{-1}$

Sedan för att få texten:

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

Säkerhetsanalys

Det här avsnittet diskuterar flera sätt att attackera ett kryptosystem [6] .

Attackera genom avrundning

Avrundningsattacken är den mest uppenbara attacken i detta kryptografiska system, förutom brute force-attacken - sökning efter felvektorn . Dess essens är att använda den publika nyckeln B för att invertera funktionen på samma sätt som när man använder den privata nyckeln R Nämligen, att veta , kan du beräkna . Således kan du hitta en vektor . Vid dimensioner under 80 LLL kan algoritmen korrekt bestämma basen, men med utgångspunkt från dimensionerna 100 och högre är denna attack värre än en trivial uppräkning av felvektorn. $e.$ $c=B\cdot v+e$ $B^{-1}\cdot c=v+B^{-1}\cdot e$ $d=B^{-1}\cdot e$

Stormattack

Denna algoritm är en uppenbar förfining av avrundningsattacken. Här använder vi den bästa approximationsalgoritmen för det kortaste vektorproblemet. I synnerhet används den närmaste planalgoritmen istället för Babai-avrundningsalgoritmen. Det fungerar så här. Givet en poäng och reducerad bas c = { } för LLL . Alla affina mellanslag = { + } : } beaktas. För alla finns det ett hyperplan närmast punkten . Vidare projiceras en punkt på det (n - 1)-dimensionella rummet, som täcks av = { } . Detta ger en ny punkt och en ny grund = { }. Algoritmen fortsätter nu rekursivt för att hitta en punkt i detta (n - 1)-dimensionella gitter nära . Slutligen ställer algoritmen in . Denna metod fungerar mycket snabbare än den föregående. Men dess arbetsbelastning växer också exponentiellt med gitterdimensionen. Experiment visar att när man använder LLL som en gitterreduktionsalgoritm krävs viss söktid, med början från storlekarna 110-120. Attacken blir omöjlig från och med storlek 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))$

Injektionsattack

Ett annat sätt som ofta används för att approximera problemet med att hitta den närmaste vektorn är att bädda in n basvektorer och en punkt för vilken det är nödvändigt att hitta en nära gitterpunkt i ett (n + 1)-dimensionellt 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 används sedan för att hitta den kortaste icke-nollvektorn i , i hopp om att de första n elementen i denna vektor kommer att vara de närmaste punkterna till . Experiment gjorda på denna attack (med hjälp av LLL som ett verktyg för att hitta kortaste vektorer) indikerar att den fungerar upp till dimensioner runt 110-120, vilket är bättre än avrundningsattacken, som blir värre än trivial sökning efter dimension 100. $L(B')$ $c$

Uppskattning av effektiviteten av attacker [7]

Uppskattad attack genom avrundning

Låt fem slutna baser skapas i varje dimension. Varje bas väljs som = + rand , där I är identitetsmatrisen och rand är en kvadratisk matris vars medlemmar väljs enhetligt från intervallet . För varje bas beräknas värdet = , där är den euklidiska normen för den största raden , och . För varje stängd bas genereras fem öppna 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))$

${arbetsbelastning_{ij))$ = , där är den dubbla ortogonalitetsdefekten: där anger matrisens rad . $({\pi }e)^{n/2}$ $\cdot {\sigma _{i}^{n))$ $\cdot {\frac {orth-defect^{*}({B_{ij)))}{det|{B_{ij}}|}}$ $orth-defect^{*}$ $orth-defect^{*}(B)=|det(B)|\cdot \prod _{i}\|{\hat {b_{i))}\|,$ ${\displaystyle {\hat {b_{i)))))$ $B^{{-1}}$

Assault poäng

För att utvärdera anfallsattacken användes samma öppna och slutna baser som vid attacken genom avrundning.

Injektionsattack utvärdering

Eftersom man inte kan tala om "arbetsbelastningen" av en injektionsattack, mättes det maximala värdet (relaterat till felvektorn) som denna attack fungerar för. För dessa experiment användes samma slutna baser och öppna baser som för de två föregående attackerna. Sedan användes varje öppen bas för att utvärdera funktionen på flera punkter med flera olika värden och kontrollerade om injektionsattacken återställer det krypterade meddelandet. ${\sigma}$ ${R}$ ${B_{ij))$ $\sigma$

Exempel

Låt gittret med basen och dess ömsesidiga vara : $L\subset \mathbb {R} ^{2}$ $B$ $B^{{-1}}$

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

och

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

Med en unimodulär matris:

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

och

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

Vi får:

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

Låt meddelandet och vektorn av fel Sedan chiffertexten: $m=(3,-7)$ $e=(1,-1).$

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

För att dekryptera behöver du:

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

Detta avrundas till $(-15,-26).$

Och meddelandet återställs med:

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

Källor och vidare läsning

Oded Goldreich, Shafi Goldwasser och Shai Halevi. Public-key kryptosystem från gallerreduktionsproblem. I CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, sidorna 112-131, London, Storbritannien, 1997. Springer-Verlag.
Phong Q. Nguyen. Kryptoanalys av Goldreich-Goldwasser-Halevi Cryptosystem från Crypto '97. I CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, sidorna 288-304, London, Storbritannien, 1999. Springer-Verlag.

Anteckningar

↑ Phong Q. Nguyen. Kryptoanalys av Goldreich-Goldwasser-Halevi Cryptosystem från Crypto '97. . - S. 1-17 . Arkiverad från originalet den 16 juli 2018.
↑ 1 2 Phong Q. Nguyen. Kryptoanalys av Goldreich-Goldwasser-Halevi Cryptosystem från Crypto '97. S. - 1-2. . Arkiverad från originalet den 16 juli 2018. (obestämd)
↑ Phong Q. Nguyen. Kryptoanalys av Goldreich-Goldwasser-Halevi Cryptosystem från Crypto '97. S. - 1. . Arkiverad från originalet den 16 juli 2018. (obestämd)
↑ Oded Goldreich, Shafi Goldwasser och Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. - S. 112-114 . Arkiverad 4 maj 2019.
↑ Phong Q. Nguyen. Kryptoanalys av Goldreich-Goldwasser-Halevi Cryptosystem från Crypto '97. . - S. 4 . Arkiverad från originalet den 16 juli 2018.
↑ Oded Goldreich, Shafi Goldwasser och Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — S. 122-124 . Arkiverad 4 maj 2019.
↑ Oded Goldreich, Shafi Goldwasser och Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. - S. 127-130 . Arkiverad 4 maj 2019.