Schema de criptare GGH

Schema de criptare GGH ( ing. Goldreich–Goldwasser–Halevi ) este un sistem criptografic asimetric bazat pe rețele . Există, de asemenea, o schemă de semnătură GGH .

Criptosistemul se bazează pe soluții la problema găsirii celui mai scurt vector și a problemei găsirii celui mai apropiat vector . Schema de criptare GGH, publicată în 1997 de oamenii de știință Oded Goldreich , Shafi Goldwasser și Shai Halevi , folosește o funcție de intrare secretă unidirecțională , deoarece având în vedere orice bază de rețea, este ușor să generați un vector aproape de un punct de rețea. De exemplu, luând un punct de rețea și adăugând un mic vector de eroare. Pentru a reveni de la vectorul de eroare la punctul inițial al rețelei, este nevoie de o bază specială. În 1999, Phong Q. Nguyen [1] a făcut o rafinare a schemei de criptare GGH inițială, ceea ce a făcut posibilă rezolvarea a patru din cele cinci probleme GGH și obținerea de informații parțiale despre acestea din urmă. În timp ce GGH poate fi sigur cu anumite alegeri de parametri, eficiența sa față de criptosistemele tradiționale cu cheie publică rămâne discutabilă [2] . Adesea, criptarea necesită o dimensiune mare a rețelei, în timp ce dimensiunea cheii crește aproximativ pătratic în raport cu dimensiunea rețelei [2] .

Singura schemă de zăbrele care poate gestiona dimensiuni mari este NTRU [3] .

Algoritm

GGH include o cheie publică și o cheie privată [4] . Cheia privată este baza rețelei cu o matrice unimodulară . $B$ $L$ $U$

Cheia publică este o altă bază a rețelei formei . $L$ $B'=UB$

Fie spațiul mesajului M format din vectori aparținând intervalului . $(m_{1},...,m_{n})$ $-M<m_{i}<M$

Criptare

Având un mesaj , o eroare și o cheie publică : $m=(m_{1},...,m_{n})$ $e$ $B'$

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

În notație matriceală:

v=m\cdot B'

Trebuie reținut că este format din valori întregi, este un punct de rețea și, prin urmare, este și un punct de rețea. Atunci textul cifrat este: $m$ $b'$ $v$

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

Transcriere

Pentru a decripta textul cifrat se calculează:

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}

Pentru a elimina , dacă este suficient de mic, se folosește metoda de rotunjire a lui Babai [5] . $e\cdot B^{-1}$

Apoi pentru a obține textul:

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

Analiza de securitate

Această secțiune discută mai multe modalități de a ataca un criptosistem [6] .

Atacul prin rotunjire

Atacul de rotunjire este cel mai evident atac al acestui sistem criptografic, cu excepția atacului de forță brută - căutarea vectorului de eroare .. Esența sa este de a folosi cheia publică B pentru a inversa funcția în același mod ca atunci când se folosește cheia privată R. Și anume, știind , puteți calcula . Astfel, puteți găsi un vector . La dimensiuni sub 80 LLL , algoritmul este capabil să determine corect baza, cu toate acestea, pornind de la dimensiunile 100 și mai mari, acest atac este mai rău decât o enumerare trivială a vectorului de eroare. $e.$ $c=B\cdot v+e$ $B^{-1}\cdot c=v+B^{-1}\cdot e$ $d=B^{-1}\cdot e$

Atacul de furtună

Acest algoritm este o rafinare evidentă a atacului de rotunjire. Aici folosim cel mai bun algoritm de aproximare pentru cea mai scurtă problemă vectorială. În special, se folosește algoritmul cel mai apropiat plan în locul algoritmului de rotunjire Babai. Funcționează așa. Dat un punct și o bază redusă c = { } pentru LLL . Toate spațiile afine = { + } : } sunt luate în considerare. Pentru toate există un hiperplan cel mai aproape de punct . În plus , un punct este proiectat pe spațiul (n - 1)-dimensional, care este acoperit de = { } . Acest lucru dă un nou punct și o nouă bază = { }. Algoritmul procedează acum recursiv pentru a găsi un punct în această rețea (n - 1)-dimensională aproape de . În cele din urmă, algoritmul stabilește . Această metodă funcționează mult mai rapid decât cea anterioară. Cu toate acestea, volumul său de lucru crește, de asemenea, exponențial odată cu dimensiunea rețelei. Experimentele arată că atunci când se utilizează LLL ca algoritm de reducere a rețelei, este necesar un anumit timp de căutare, începând de la dimensiunile 110-120. Atacul devine nerealizabil începând cu mărimea 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)}$

Atacul prin injecție

O altă modalitate care este adesea folosită pentru a aproxima problema găsirii celui mai apropiat vector este de a încorpora n vectori de bază și un punct pentru care este necesar să se găsească un punct al rețelei apropiate într-o rețea (n + 1)-dimensională. $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}}$

Algoritmul de reducere a rețelei este apoi folosit pentru a găsi cel mai scurt vector diferit de zero în , în speranța că primele n elemente din acest vector vor fi cele mai apropiate puncte de . Experimentele efectuate pe acest atac (folosind LLL ca instrument pentru găsirea celor mai scurti vectori) indică faptul că funcționează până la dimensiuni în jurul valorii de 110-120, ceea ce este mai bun decât atacul de rotunjire, care devine mai rău decât căutarea trivială după dimensiunea 100. $L(B')$ $c$

Estimarea eficacității atacurilor [7]

Atacul estimat prin rotunjire

Să fie create cinci baze închise în fiecare dimensiune. Fiecare bază este aleasă ca = + rand , unde I este matricea de identitate și rand este o matrice pătrată ai cărei membri sunt aleși uniform din interval . Pentru fiecare bază se calculează valoarea = , unde este norma euclidiană a celui mai mare rând și . Pentru fiecare bază închisă sunt generate cinci baze deschise $n$ ${R_{i)}$ $4\left|{\sqrt {n}}\right|\cdot I$ $(\pm 4)$ $(\pm 4)$ ${-4,...,4}$ ${R_{i)}$ ${\sigma _{i)}$ $({\gamma _{i)} {\sqrt {8\ln({2n}/{\varepsilon }))))^{-1)$ ${\gamma _{i)}$ ${R_{i}}^{-1}$ $\varepsilon =10^{-5}$ ${R_{i)}$ ${B_{ij)}$

${sarcina de lucru_{ij)}$ = , unde este defectul de ortogonalitate dublă: unde denotă rândul matricei . $({\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))}\|,$ ${\pălărie {b_{i)})$ $B^{{-1}}$

Scorul de atac

Pentru a evalua atacul de asalt, au fost folosite aceleași baze deschise și închise ca și în atacul prin rotunjire.

Evaluarea atacului de injecție

Întrucât nu se poate vorbi de „sarcina de lucru” a unui atac de injecție, s-a măsurat valoarea maximă (legată de vectorul de eroare) pentru care funcționează acest atac. Pentru aceste experimente, au fost folosite aceleași baze închise și baze deschise ca și pentru cele două atacuri anterioare. Apoi, fiecare bază deschisă a fost folosită pentru a evalua funcția în mai multe puncte folosind mai multe valori diferite și a verificat dacă atacul de injecție recuperează mesajul criptat. ${\sigma}$ ${R}$ ${B_{ij)}$ $\sigma$

Exemplu

Fie rețeaua cu bază și reciproca sa : $L\subset \mathbb {R} ^{2}$ $B$ $B^{{-1}}$

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

și

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

Cu o matrice unimodulară:

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

și

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

Primim:

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

Fie mesajul și vectorul erorilor Apoi textul cifrat: $m=(3,-7)$ $e=(1,-1).$

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

Pentru a decripta aveți nevoie de:

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

Aceasta se rotunjește la $(-15,-26).$

Și mesajul este restabilit cu:

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

Surse și lecturi suplimentare

Oded Goldreich, Shafi Goldwasser și Shai Halevi. Criptosisteme cu cheie publică din probleme de reducere a rețelei. În CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, paginile 112-131, Londra, Marea Britanie, 1997. Springer-Verlag.
Phong Q. Nguyen. Criptoanaliza Criptosistemului Goldreich-Goldwasser-Halevi de la Crypto '97. În CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, paginile 288-304, Londra, Marea Britanie, 1999. Springer-Verlag.

Note

↑ Phong Q. Nguyen. Criptoanaliza Criptosistemului Goldreich-Goldwasser-Halevi de la Crypto '97. . - S. 1-17 . Arhivat din original pe 16 iulie 2018.
↑ 1 2 Phong Q. Nguyen. Criptoanaliza Criptosistemului Goldreich-Goldwasser-Halevi de la Crypto '97. S. - 1-2. . Arhivat din original pe 16 iulie 2018. (nedefinit)
↑ Phong Q. Nguyen. Criptoanaliza Criptosistemului Goldreich-Goldwasser-Halevi de la Crypto '97. S. - 1. . Arhivat din original pe 16 iulie 2018. (nedefinit)
↑ Oded Goldreich, Shafi Goldwasser și Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. - S. 112-114 . Arhivat 4 mai 2019.
↑ Phong Q. Nguyen. Criptoanaliza Criptosistemului Goldreich-Goldwasser-Halevi de la Crypto '97. . - S. 4 . Arhivat din original pe 16 iulie 2018.
↑ Oded Goldreich, Shafi Goldwasser și Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — S. 122-124 . Arhivat 4 mai 2019.
↑ Oded Goldreich, Shafi Goldwasser și Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. - S. 127-130 . Arhivat 4 mai 2019.