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. 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 ${\displaystyle B}$ of a lattice ${\displaystyle L}$ with good properties, such as short nearly orthogonal vectors and a unimodular matrix ${\displaystyle U}$.

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

For some chosen M, the message space consists of the vector ${\displaystyle (\lambda_1,..., \lambda_n)}$ in the range ${\displaystyle -M <\lambda_i < M}$.

### Encryption

Given a message ${\displaystyle m = (\lambda_1,..., \lambda_n)}$, error ${\displaystyle e}$, and a public key ${\displaystyle B'}$ compute

${\displaystyle v = \sum \lambda_i b_i'}$

In matrix notation this is

${\displaystyle v=m\cdot B'}$.

Remember ${\displaystyle m}$ consists of integer values, and ${\displaystyle b'}$ is a lattice point, so v is also a lattice point. The ciphertext is then

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

### Decryption

To decrypt the cyphertext one computes

${\displaystyle c \cdot B^{-1} = (m\cdot B^\prime +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 ${\displaystyle e \cdot B^{-1}}$ as long as it is small enough. Finally compute

${\displaystyle m = m \cdot U \cdot U^{-1} }$

to get the messagetext.

## Example

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

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

With

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

this gives

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

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

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

To decrypt one must compute

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

This is rounded to ${\displaystyle (-15, -26)}$ and the message is recovered with

${\displaystyle 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 into 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.