GGH encryption scheme

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 (m_{1},...,m_{n})}$ in the range ${\displaystyle -M<m_{i}<M}$.

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

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

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

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'=UB={\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=mB'+e=(-104,-79).\,}$

To decrypt one must compute

${\displaystyle cB^{-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).\,}$

In 1999, Nguyen ^[1] 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.

• TheGaBr0/GGH – A Python implementation of the GGH cryptosystem and its optimized variant GGH-HNF.^[2] The library includes key generation, encryption, decryption, basic lattice reduction techniques, and demonstrations of known attacks. It is intended for educational and research purposes and is available via PyPI.