GGH encryption scheme explained

The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem is an asymmetric cryptosystem based on lattices. There is also a GGH signature scheme.

The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the closest vector problem can be a hard problem. This system was published in 1997 by Oded Goldreich, Shafi Goldwasser, and Shai Halevi, and uses a trapdoor one-way function which relies on the difficulty of lattice reduction. The idea included in this trapdoor function is that, given any basis for a lattice, it is easy to generate a vector which is close to a lattice point, for example taking a lattice point and adding a small error vector. But to return from this erroneous vector to the original lattice point a special basis is needed.

The GGH encryption scheme was cryptanalyzed (broken) in 1999 by . Nguyen and Oded Regev had cryptanalyzed the related GGH signature scheme in 2006.

Operation

GGH involves a private key and a public key.

The private key is a basis

B of a lattice L with good properties (such as short nearly orthogonal vectors) and a unimodular matrix U .

The public key is another basis of the lattice

L of the form B' = UB .

For some chosen M, the message space consists of the vector

(m _{1,...,} m _{n)} in the range - M <m _{i} < M .

Encryption

Given a message

m = (m _{1,...,} m _{n)} , error e , and apublic key B' computev = \sum m _{i} b _{i'}

In matrix notation this is

v = m ⋅ B' .

Remember

m consists of integer values, and b' is a lattice point, so v is also a lattice point. The ciphertext is thenc = v + e = m ⋅ B' + e

Decryption

To decrypt the ciphertext one computes

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

The Babai rounding technique will be used to remove the term

e ⋅ B ^{-1} as long as it is small enough. Finally computem = m ⋅ U ⋅ U ^{-1}

to get the messagetext.

Example

Let

L \subset R ^{2} be a lattice with the basis B and its inverse B ^{-1} B = \begin{pmatrix} 7 & 0 \ 0 & 3 \ \end{pmatrix} and B ^{-1} = \begin{pmatrix} (1)/(7) & 0 \ 0 & (1)/(3) \ \end{pmatrix}

With

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

this gives

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

Let the message be

m = ( 3 , -7 ) and the error vector e = ( 1 , -1 ) . Then the ciphertext isc = m B' + e = ( -104 , -79 ).

To decrypt one must compute

c B ^{-1} = \left( (-104)/(7) , (-79)/(3) \right).

This is rounded to

( -15 , -26 ) and the message is recovered withm = ( -15 , -26 ) U ^{-1} = ( 3 , -7 ).

Security of the scheme

In 1999, Nguyen ^[1] 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.

Bibliography

• Book: Oded . Goldreich . Shafi . Goldwasser . Shai . Halevi . Public-key cryptosystems from lattice reduction problems . CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology . 112–131 . London . 1997 . Springer-Verlag .
• Book: Nguyen, Phong Q. . https://www.di.ens.fr/~pnguyen/pub_Ng99.htm . Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97 . CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology . 288–304 . London . 1999 . Springer-Verlag .
• Nguyen . Phong Q. . Regev . Oded . Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. Journal of Cryptology . 11 November 2008 . 22 . 2 . 139–160 . 0933-2790 . 1432-1378 . 10.1007/s00145-008-9031-0 . 2164840 . Preliminary version in EUROCRYPT 2006.

Notes and References

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