On Lattices, Learning with Errors, Random Linear Codes ...

On Lattices, Learning with Errors, Random Linear Codes , and CryptographyOded Regev May 2, 2009 AbstractOur main result is a reduction from worst-case lattice problems such asGAPSVPandSIVPto acertain Learning problem. This Learning problem is a natural extension of the Learning from parity witherror problem to higher moduli. It can also be viewed as the problem of decoding from a Random linearcode. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, isquantum. Hence, an efficient solution to the Learning problem implies aquantumalgorithm forGAPSVPandSIVP. A main open question is whether this reduction can be made classical ( , non-quantum).We also present a (classical) public-key cryptosystem whose security is based on the hardness of thelearning problem. By the main result, its security is also based on the worst-case quantum hardness ofGAPSVPandSIVP.

then there exists an efficient quantum algorithm that approximates the decision version of the shortest vector problem (GAPSVP) and the shortest independent vectors problem (SIVP) to within O~(n=fi) in the worst case. 2

Loading..

Tags:

  With, Learning, Then, Errors, Learning with errors

Information

Related search queries