# 23.5 Another Lattice-Based Cryptosystem

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



# 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 ? In the present example,



and



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.