On lattices, learning with errors, random linear codes, and cryptography
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).
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Sep 01, 2009
- Source ID
- 10.1145/1568318.1568324
Entities
People
- Oded Regev
Organizations
- Army Research Office
- Tel Aviv University