# GGH encryption scheme

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 in 1999 by Phong Q. Nguyen.

## Operation

GGH involves a private key and a public key.

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

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

For some chosen M, the message space consists of the vector $(m_{1},...,m_{n})$  in the range $-M .

### Encryption

Given a message $m=(m_{1},...,m_{n})$ , error $e$ , and a public key $B'$  compute

$v=\sum m_{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^{\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 $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

In 1999, Nguyen  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.