# 23.5 Another Lattice-Based Cryptosystem

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=G\phantom{\rule{thinmathspace}{0ex}}U$, 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 $\stackrel{\u20d7}{m}$ with integral entries, which is encrypted to obtain the ciphertext

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

The decryption is carried out by computing

where $\lfloor \stackrel{\u20d7}{v}\phantom{\rule{thinmathspace}{0ex}}\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 $\stackrel{\u20d7}{m}$ have integral entries, so does the $U\stackrel{\u20d7}{m}$. Since $G$ is good, the entries of ${G}^{-1}\stackrel{\u20d7}{e}$ tend to be small fractions, so they disappear in the rounding. Therefore, $\lfloor {G}^{-1}\stackrel{\u20d7}{c}\phantom{\rule{thinmathspace}{0ex}}\rceil $ probably equals $U\stackrel{\u20d7}{m}$, so

# Example

To keep things simple, we’ll work in two-dimensional, rather than 300-dimensional, space. Let

and

Then

To decrypt, we first compute

Therefore, the decryption is

Suppose, instead, that we tried to decrypt by computing $\lfloor {B}^{-1}\stackrel{\u20d7}{c}\phantom{\rule{thinmathspace}{0ex}}\rceil $? In the present example,

and

This rounds off to $(71\text{,}\text{}26)$, which is nowhere close to the original message. The problem is that the entries of ${B}^{-1}$ are much larger than those of ${G}^{-1}$, so the small error introduced by $\stackrel{\u20d7}{e}$ is amplified by ${B}^{-1}$.

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\stackrel{\u20d7}{m}\in L$, and $\stackrel{\u20d7}{c}$ is close to $B\stackrel{\u20d7}{m}$ since it is moved off the lattice by the small vector $\stackrel{\u20d7}{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.