• Images
• Videos
• Documents
• Books
• Articles

Operation

GGH involves a private key and a public key.

The private key is a basis B {\displaystyle B} of a lattice L {\displaystyle L} with good properties (such as short nearly orthogonal vectors) and a unimodular matrix U {\displaystyle U} .

The public key is another basis of the lattice L {\displaystyle L} of the form B ′ = U B {\displaystyle B'=UB} .

For some chosen M, the message space consists of the vector ( m 1 , . . . , m n ) {\displaystyle (m_{1},...,m_{n})} in the range − M < m i < M {\displaystyle -M<m_{i}<M} .

Encryption

Given a message m = ( m 1 , . . . , m n ) {\displaystyle m=(m_{1},...,m_{n})} , error e {\displaystyle e} , and a public key B ′ {\displaystyle B'} compute

v = ∑ m i b i ′ {\displaystyle v=\sum m_{i}b_{i}'}

In matrix notation this is

v = m ⋅ B ′ {\displaystyle v=m\cdot B'} .

Remember m {\displaystyle m} consists of integer values, and b ′ {\displaystyle b'} is a lattice point, so v is also a lattice point. The ciphertext is then

c = v + e = m ⋅ B ′ + e {\displaystyle c=v+e=m\cdot B'+e}

Decryption

To decrypt the ciphertext one computes

c ⋅ B − 1 = ( m ⋅ B ′ + e ) B − 1 = m ⋅ U ⋅ B ⋅ B − 1 + e ⋅ B − 1 = m ⋅ U + e ⋅ B − 1 {\displaystyle 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}}

The Babai rounding technique will be used to remove the term e ⋅ B − 1 {\displaystyle e\cdot B^{-1}} as long as it is small enough. Finally compute

m = m ⋅ U ⋅ U − 1 {\displaystyle m=m\cdot U\cdot U^{-1}}

to get the message.

Example

Let L ⊂ R 2 {\displaystyle L\subset \mathbb {R} ^{2}} be a lattice with the basis B {\displaystyle B} and its inverse B − 1 {\displaystyle B^{-1}}

B = ( 7 0 0 3 ) {\displaystyle B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}} and B − 1 = ( 1 7 0 0 1 3 ) {\displaystyle B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}}

With

U = ( 2 3 3 5 ) {\displaystyle U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}} and U − 1 = ( 5 − 3 − 3 2 ) {\displaystyle U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}}

this gives

B ′ = U B = ( 14 9 21 15 ) {\displaystyle B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}}

Let the message be m = ( 3 , − 7 ) {\displaystyle m=(3,-7)} and the error vector e = ( 1 , − 1 ) {\displaystyle e=(1,-1)} . Then the ciphertext is

c = m B ′ + e = ( − 104 , − 79 ) . {\displaystyle c=mB'+e=(-104,-79).\,}

To decrypt one must compute

c B − 1 = ( − 104 7 , − 79 3 ) . {\displaystyle cB^{-1}=\left({\frac {-104}{7}},{\frac {-79}{3}}\right).}

This is rounded to ( − 15 , − 26 ) {\displaystyle (-15,-26)} and the message is recovered with

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

Security of the scheme

In 1999, Nguyen ¹ showed that the GGH encryption scheme has a flaw in the design. He showed that every ciphertext reveals information about the plaintext and that the problem of decryption could be turned into a special closest vector problem much easier to solve than the general CVP.

Implementations

• TheGaBr0/GGH – A Python implementation of the GGH cryptosystem and its optimized variant GGH-HNF². The library includes key generation, encryption, decryption, basic lattice reduction techniques, and demonstrations of known attacks. It is intended for educational and research purposes and is available via PyPI.

Bibliography

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). "Public-key cryptosystems from lattice reduction problems". CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. pp. 112–131.
• Nguyen, Phong Q. (1999). "Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto '97". CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. pp. 288–304.
• Nguyen, Phong Q.; Regev, Oded (11 November 2008). "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures" (PDF). Journal of Cryptology. 22 (2): 139–160. doi:10.1007/s00145-008-9031-0. eISSN 1432-1378. ISSN 0933-2790. S2CID 2164840.Preliminary version in EUROCRYPT 2006.
• Micciancio, Daniele (2001). Advances in Cryptology — CT-RSA 2001. Lecture Notes in Computer Science. Vol. 2146. Springer. pp. 126–145. doi:10.1007/3-540-44670-2_11.

References

1. Phong Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97. CRYPTO, 1999 ↩

2. Micciancio, Daniele. (2001). Improving Lattice Based Cryptosystems Using the Hermite Normal Form. LNCS. 2146. 10.1007/3-540-44670-2_11. ↩