Regev: “On lattices, learning with errors, random linear codes, and cryptography"

16.05.2018, 10:00 – 11:00

2018/05/16 10:00-11:00

Speaker: Thomas Wunderer, TU Darmstadt | Location: Mornewegstraße 32 (S4|14), Room 5.3.01, Darmstadt

Organizer: Felix Günther and Christian Janson, TU Darmstadt


This talk is the second one in the seminar series “Reading the Crypto Classics” for the summer term 18. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper

Canetti: “Regev: “On lattices, learning with errors, random linear codes, and cryptography“” (STOC 2005), DOI: 10.1145/1568318.1568324

with the following abstract:

“Our main result is a reduction from worst-case lattice problems such as GapSVP 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 GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum).

We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size Õ(n^2) and encrypting a message increases its size by a factor of Õ(n) (in previous cryptosystems these values are Õ(n^4) and Õ(n^2), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n^2), the size of the public key can be reduced to Õ(n).”

See for further details.