Transcription of On Lattices, Learning with Errors, Random Linear Codes ...
{{id}} {{{paragraph}}}
Example: bankruptcy
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. The new cryptosystem is much more efficient than previous lattice-based cryp-tosystems: the public key is of size O(n2)and encrypting a message increases its size by a factor of O(n)(in previous cryptosystems these values are O(n4)and O(n2), respectively).
though this is probably one of the most important open questions in the field of quantum computing.1 In fact, one could also interpret our main theorem as a way to disprove this conjecture: if one finds an efficient algorithm for LWE, then one also obtains a quantum algorithm for approximating worst-case lattice problems.
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: