Another lattice-based public key cryptosystem was developed by Goldreich, Goldwasser, and Halevi in 1997. Let $L$ be a 300-dimensional lattice that is a subset of the points with integral coordinates in 300-dimensional real space ${\mathbb{R}}^{300}$.

The private key is a “good” basis of $L$, given by the columns of a $300\times 300$ matrix $G$, where “good” means that the entries of $G$ are small.

The public key is a “bad basis” of $L$, given by the columns of a $300\times 300$ matrix $B=GU$, where $U$ is a secret $300\times 300$ matrix with integral entries and with determinant 1. The determinant condition implies that the entries of $U^{-1}$ are also integers. “Bad” means that $B$ has many large entries.

A message is a 300-dimensional vector $\vec{m}$ with integral entries, which is encrypted to obtain the ciphertext

where $\vec{e}$ is a 300-dimensional vector whose entries are chosen randomly from $\{0\text{,}\pm 1\text{,}\pm 2\text{,}\pm 3\}$.

The decryption is carried out by computing

where $\lfloor \vec{v}\rceil$ for a vector means we round off each entry to the nearest integer (and $.5$ goes whichever way you specify). Why does this decryption work? First, $U=G^{-1}B$, so

Since $U$ and $\vec{m}$ have integral entries, so does the $U\vec{m}$. Since $G$ is good, the entries of $G^{-1}\vec{e}$ tend to be small fractions, so they disappear in the rounding. Therefore, $\lfloor G^{-1}\vec{c}\rceil$ probably equals $U\vec{m}$, so

Attacking this system involves the Closest Vector Problem: Given a point $P$ in ${\mathbf{\text{R}}}^n$, find the point in $L$ closest to $P$.

We have $B\vec{m}\in L$, and $\vec{c}$ is close to $B\vec{m}$ since it is moved off the lattice by the small vector $\vec{e}$.

For general lattices, the Closest Vector Problem is very hard. But it seems to be easier if the point is very close to a lattice point, which is the case in this cryptosystem. So the actual level of security is not yet clear.