Another lattice-based public key cryptosystem was developed by Goldreich, Goldwasser, and Halevi in 1997. Let be a 300-dimensional lattice that is a subset of the points with integral coordinates in 300-dimensional real space .
The private key is a “good” basis of , given by the columns of a matrix , where “good” means that the entries of are small.
The public key is a “bad basis” of , given by the columns of a matrix , where is a secret matrix with integral entries and with determinant 1. The determinant condition implies that the entries of are also integers. “Bad” means that has many large entries.
A message is a 300-dimensional vector with integral entries, which is encrypted to obtain the ciphertext
where is a 300-dimensional vector whose entries are chosen randomly from .
The decryption is carried out by computing
where for a vector means we round off each entry to the nearest integer (and goes whichever way you specify). Why does this decryption work? First, , so
Since and have integral entries, so does the . Since is good, the entries of tend to be small fractions, so they disappear in the rounding. Therefore, probably equals , so
To keep things simple, we’ll work in two-dimensional, rather than 300-dimensional, space. Let
To decrypt, we first compute
Therefore, the decryption is
Suppose, instead, that we tried to decrypt by computing ? In the present example,
This rounds off to , which is nowhere close to the original message. The problem is that the entries of are much larger than those of , so the small error introduced by is amplified by .
Attacking this system involves the Closest Vector Problem: Given a point in , find the point in closest to .
We have , and is close to since it is moved off the lattice by the small vector .
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.