Schéma šifrování GGH - GGH encryption scheme

The Goldreich – Goldwasser – Halevi (GGH) na mřížce kryptosystém je asymetrický kryptosystém založený na mříže. Je tam také Schéma podpisu GGH.

Kryptosystém Goldreich – Goldwasser – Halevi (GGH) využívá skutečnosti, že nejbližší vektorový problém může být těžký problém. Tento systém byl publikován v roce 1997 autorem Oded Goldreich, Shafi Goldwasser, a Shai Halevi, a používá jednosměrnou funkci padacích dveří, která se spoléhá na obtížnost redukce mřížky. Myšlenka zahrnutá do této funkce padacích dveří spočívá v tom, že vzhledem k jakémukoli základu pro mřížku je snadné generovat vektor, který je blízký mřížovému bodu, například vzít mřížkový bod a přidat malý vektor chyby. Ale pro návrat z tohoto chybného vektoru do původního bodu mřížky je zapotřebí speciální základ.

Šifrovací schéma GGH bylo dešifrováno v roce 1999 Phongem Q. Nguyenem.

Úkon

GGH zahrnuje a soukromý klíč a a veřejný klíč.

Soukromý klíč je základ ${displaystyle B}$ mříže ${displaystyle L}$ s dobrými vlastnostmi (například krátké téměř ortogonální vektory) a a unimodulární matice ${displaystyle U}$.

Veřejný klíč je dalším základem mřížky ${displaystyle L}$ formuláře ${displaystyle B '= UB}$.

U některých vybraných M se prostor pro zprávy skládá z vektoru ${displaystyle (m_ {1}, ..., m_ {n})}$ v dosahu ${displaystyle -M$.

Šifrování

Dostal zprávu ${displaystyle m = (m_ {1}, ..., m_ {n})}$, chyba ${displaystyle e}$a klíč republiky ${displaystyle B '}$ vypočítat

${displaystyle v = součet m_ {i} b_ {i} '}$

V maticové notaci to je

${displaystyle v = mcdot B '}$.

Pamatuj si ${displaystyle m}$ se skládá z celočíselných hodnot a ${displaystyle b '}$ je mřížkový bod, takže v je také mřížkový bod. Šifrovací text tedy je

${displaystyle c = v + e = mcdot B '+ e}$

Dešifrování

K dešifrování cyphertextu se počítá

${displaystyle ccdot B ^ {- 1} = (mcdot B ^ {prime} + e) ​​B ^ {- 1} = mcdot Ucdot Bcdot B ^ {- 1} + ecdot B ^ {- 1} = mcdot U + ecdot B ^ {- 1}}$

K odstranění výrazu bude použita metoda zaoblení Babai ${displaystyle ecdot B ^ {- 1}}$ pokud je dostatečně malý. Nakonec spočítejte

${displaystyle m = mcdot Ucdot U ^ {- 1}}$

získat text zprávy.

Příklad

Nechat ${displaystyle Lsubset mathbb {R} ^ {2}}$ být mřížkou na základě ${displaystyle B}$ a jeho inverzní ${displaystyle B ^ {- 1}}$

${displaystyle B = {egin {pmatrix} 7 & 0 0 & 3 end {pmatrix}}}$ a ${displaystyle B ^ {- 1} = {egin {pmatrix} {frac {1} {7}} & 0 0 & {frac {1} {3}} end {pmatrix}}}$

S

${displaystyle U = {egin {pmatrix} 2 & 3 3 & 5 end {pmatrix}}}$ a

${displaystyle U ^ {- 1} = {egin {pmatrix} 5 & -3 -3 & 2 end {pmatrix}}}$

to dává

${displaystyle B '= UB = {egin {pmatrix} 14 & 9 21 & 15 end {pmatrix}}}$

Nechť je zpráva ${displaystyle m = (3, -7)}$ a vektor chyby ${displaystyle e = (1, -1)}$. Pak je šifrovací text

${displaystyle c = mB '+ e = (- 104, -79).,}$

K dešifrování je třeba počítat

${displaystyle cB ^ {- 1} = vlevo ({frac {-104} {7}}, {frac {-79} {3}} vpravo).}$

To je zaokrouhleno na ${displaystyle (-15, -26)}$ a zpráva je obnovena pomocí

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

Zabezpečení režimu

1999 Nguyen na konferenci Crypto ukázal, že schéma šifrování GGH má chybu v designu těchto schémat. Nguyen ukázal, že každý šifrový text odhaluje informace o holém textu a že problém dešifrování lze proměnit ve speciální nejbližší vektorový problém mnohem jednodušší než obecný CVP.

Bibliografie

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). "Kryptosystémy veřejného klíče z problémů s redukcí mřížky". CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. str. 112–131.
• Nguyen, Phong Q. (1999). „Kryptoanalýza kryptosystému Goldreich – Goldwasser – Halevi z kryptoměny 97“. CRYPTO ’99: Proceedings of the 19. Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. 288–304.