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 Phong Q. Nguyen [fr]. Nguyen and Oded Regev had cryptanalyzed the related GGH signature scheme in 2006.

Operation

edit

GGH involves a private key and a public key.

The private key is a basis   of a lattice   with good properties (such as short nearly orthogonal vectors) and a unimodular matrix  .

The public key is another basis of the lattice   of the form  .

For some chosen M, the message space consists of the vector   in the range  .

Encryption

edit

Given a message  , error  , and a public key   compute

 

In matrix notation this is

 .

Remember   consists of integer values, and   is a lattice point, so v is also a lattice point. The ciphertext is then

 

Decryption

edit

To decrypt the ciphertext one computes

 

The Babai rounding technique will be used to remove the term   as long as it is small enough. Finally compute

 

to get the messagetext.

Example

edit

Let   be a lattice with the basis   and its inverse  

  and  

With

  and
 

this gives

 

Let the message be   and the error vector  . Then the ciphertext is

 

To decrypt one must compute

 

This is rounded to   and the message is recovered with

 

Security of the scheme

edit

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.

References

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

Bibliography

edit
  • 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.