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 .

m, for any other word s0, the Hamming distance of t from Qs0 is roughly m(1 ¡ 1=p). Hence, we obtain that approximating the nearest codeword problem to within factors smaller than (1 ¡ 1=p)=(1 ¡ 1=(fip)) on random codes is as hard as quantumly approximating worst-case lattice problems. This gives a partial

Loading..

Tags:

  With, Learning, Problem, Words, Errors, Learning with errors

Information

Related search queries