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 ${\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, ...