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.
On Lattices, Learning with Errors, Random Linear Codes, and Cryptography Oded Regev ⁄ May 2, 2009 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.
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: