Jump to content

GGH encryption scheme

From Wikipedia, the free encyclopedia

The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem is a broken asymmetric cryptosystem based on lattices. There is also a GGH signature scheme which hasn't been broken as of 2024.

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 message.

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.