23.5 Another Lattice-Based Cryptosystem – Introduction to Cryptography with Coding Theory, 3rd Edition

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 R300.

The private key is a “good” basis of L, given by the columns of a 300×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×300 matrix B=GU, where U is a secret 300×300 matrix with integral entries and with determinant 1. The determinant condition implies that the entries of U1 are also integers. “Bad” means that B has many large entries.

A message is a 300-dimensional vector m with integral entries, which is encrypted to obtain the ciphertext

c=Bm+e, 

where e is a 300-dimensional vector whose entries are chosen randomly from {0, ±1, ±2, ±3}.

The decryption is carried out by computing

B1GG1c, 

where v 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=G1B, so

G1c=G1Bm+G1e=Um+G1e.

Since U and m have integral entries, so does the Um. Since G is good, the entries of G1e tend to be small fractions, so they disappear in the rounding. Therefore, G1c probably equals Um, so

B1GG1c=B1GUm=B1GG1Bm=m.

Example

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

G=5214andB=GU=521417181617=1171248186

and

m=5937.

Then

c=11712481865937+11=114927960.

To decrypt, we first compute

G1c=2/91/91/185/18114927960=1669.331572.67=16691573.

Therefore, the decryption is

B1GG1c=U1G1c=1718161716691573=5937=m.

Suppose, instead, that we tried to decrypt by computing B1c? In the present example,

B1=43/962/99/213/2

and

B1c=43/962/99/213/2114927960=212/326.

This rounds off to (71, 26), which is nowhere close to the original message. The problem is that the entries of B1 are much larger than those of G1, so the small error introduced by e is amplified by B1.

Attacking this system involves the Closest Vector Problem: Given a point P in Rn, find the point in L closest to P.

We have BmL, and c is close to Bm since it is moved off the lattice by the small vector 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.