GGH encryption scheme

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

The Goldreich-Goldwasser-Halevi (GGH) cryptosystem makes use of the fact that the CVP can be a hard problem. It was published in 1997 and uses a trapdoor one-way function that is relying 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 it is not known how to simply return from 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 a unimodular matrix $U$.

The public key is of the lattice $L$ of the form $B'=UB$.

For some chosen M, the message space consists of the vector $(\lambda _{1},...,\lambda _{n})$ in the range $-M<\lambda _{i}<M$.

Encryption

Given a message $m=(\lambda _{1},...,\lambda _{n})$ and a public key $B'$ compute

   $v=\sum \lambda _{i}b_{i}'$

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

  $c=v+e=m\cdot B'+e$

Decryption

To decrypt the cyphertext one computes

  $c\cdot B^{-1}=(m\cdot B+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\cdot B^{-1}$ as long as 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}$

$B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}$ and $B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}$

With

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

this gives

$B'=UB={\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 is

$c=mB'+e=(-104,-79)$.

To decrypt one must compute $cB^{-1}=\left({\frac {-104}{7}},{\frac {-79}{3}}\right)$.

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

Security 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: Pro- ceedings 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.