GGH encryption scheme

The Goldreich-Goldwasser-Halevi (GGH) cryptosystem is a asymetriccryptosystem based on lattice.

The Goldreich-Goldwasser-Halevi (GGH) cryptosystem makes use of thefactthatthe CVP can be a hard problem. It was published in 1997 and uses atrapdoorone-way function that is relying on the difficulty of latticereduction.The ideaincluded in this trapdoor function is that, given any basis for alattice, it is easyto generate a vector which is close to a lattice point, for exampletaking a latticepoint and adding a small error vector. But it is not known how tosimplyreturnfrom this erroneous vector to the original lattice point.

Operation

GGH involves a private key and a public key.

The private key is a basis $B$ of a lattice $L$with good properties as short mostly orthogonal vectors and aunimodularmatrix $U$.

The public key is of the lattice $L$ of the form$B\text{'}=UB$.

For some chosen M, the message space consists of the vector$(lambda\_1,...,\; lambda\_n)$ in the range

Encryption

Given a message $m\; =\; (lambda\_1,...,\; lambda\_n)$ and apublickey $B\text{'}$ compute

$v\; =\; sum\; lambda\_i\; b\_i\text{'}$

In matrix notation this is $v=mcdot\; B\text{'}$. Remember $m$ consists of integer values, and $b\text{'}$ is a lattice point, so v is also a lattice point. The ciphertext is then

$c=v+e=m\; cdot\; B\text{'}\; +\; e$

Decryption

To decrypt the cyphertext one computes

$c\; cdot\; B^\{-1\}\; =\; (mcdot\; B+e)B^\{-1\}\; =\; mcdot\; Ucdot\; Bcdot\; B^\{-1\}\; +\; ecdot\; B^\{-1\}\; =\; mcdot\; U\; +\; ecdot\; B^\{-1\}$

The Babai rounding technique will be used to remove the term $e\; cdot\; B^\{-1\}$ as longas it is small enough. Finally compute $m\; =\; m\; cdot\; U\; cdot\; U^\{-1\}$

to get the messagetext.

Example

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

and

With

and

this gives

Let the message be $m\; =\; (3,\; -7)$ and the error vector $e\; =\; (1,\; -1)$. Then the ciphertext is

$c\; =\; m\; B\text{'}+e=(-104,\; -79)$.

To decrypt one must compute $c\; B^\{-1\}\; =\; left(\; frac\{-104\}\{7\},\; frac\{-79\}\{3\}\; ight)$.

This is rounded to $(-15,\; -26)$ and the message is recovered with$m=\; (-15,\; -26)\; U^\{-1\}\; =\; (3,\; -7)$.

ecurity of the Scheme

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

Bibliography

* Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.
* Phong Q. Nguyen. Cryptanalysis of the goldreich-goldwasser-halevi cryptosystem from crypto ’97. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.