Transcription of On Lattices, Learning with Errors, Random Linear Codes ...
{{id}} {{{paragraph}}}
Example: marketing
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.
Blum, Kalai, and Wasserman [11] provided the first subexponential algorithm for this problem. Their algorithm requires only2O(n=logn) equations/time and is currently the best known algorithm for the problem. It is based on a clever idea that allows to find a small set S of equations (say, O(p n)) among 2O(n=logn) equations, such that P
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: