GGH encryption scheme

Template:Short description 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 Template:Ill. Nguyen and Oded Regev had cryptanalyzed the related GGH signature scheme in 2006.

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^{\prime }=UB$.

For some chosen M, the message space consists of the vector $(m_1,...,m_n)$ in the range $-M<m_i<M$.

Encryption

Given a message $m=(m_1,...,m_n)$, error $e$, and a public key $B^{\prime }$ compute

$v=\sum m_i{b_i}^{\prime }$

In matrix notation this is

$v=m\cdot B^{\prime }$.

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

$c=v+e=m\cdot B^{\prime }+e$

Decryption

To decrypt the ciphertext 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 message.

Example

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

$B=\left(\begin{array}{cc}7& 0\\ 0& 3\end{array}\right)$ and $B^{-1}=\left(\begin{array}{cc}\frac{1}{7}& 0\\ 0& \frac{1}{3}\end{array}\right)$

With

$U=\left(\begin{array}{cc}2& 3\\ 3& 5\end{array}\right)$ and

$U^{-1}=\left(\begin{array}{cc}5& -3\\ -3& 2\end{array}\right)$

this gives

$B^{\prime }=UB=\left(\begin{array}{cc}14& 9\\ 21& 15\end{array}\right)$

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

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

To decrypt one must compute

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

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.

Bibliography

• Template:Cite book
• Template:Cite book
• Template:Cite journalPreliminary version in EUROCRYPT 2006.