Aristeidis Tentes

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

Oded Regev (Proc. of STOC 2005)

Our main result is a reduction from worst-case lattice problems such as
SVP and SIVP to a certain learning problem. This learning problem is a
natural extension of the 'learning from parity with error' problem to
higher moduli. It can also be viewed as the problem of decoding from a
random linear code. This, we believe, gives a strong indication that
these problems are hard. Our reduction, however, is quantum. Hence, an
efficient solution to the learning problem implies a quantum algorithm
for SVP and SIVP. A main open question is whether this reduction can be
made classical.Using the main result, we obtain a public-key
cryptosystem whose hardness is based on the worst-case quantum hardness
of SVP and SIVP. Previous lattice-based public-key cryptosystems such as
the one by Ajtai and Dwork were only based on unique-SVP, a special case
of SVP. The new cryptosystem is much more efficient than previous
cryptosystems: the public key is of size Õ(n2) and encrypting a message
increases its size by Õ(n)(in previous cryptosystems these values are
Õ(n4) and Õ(n2), respectively). In fact, under the assumption that all
parties share a random bit string of length Õ(n2), the size of the
public key can be reduced to Õ(n).