[Reg05] On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
Authors: Oded Regev | Venue: STOC 2005 | Source
Abstract
We introduce the learning with errors (LWE) problem and show that it enjoys a quantum reduction from worst-case lattice problems: any efficient algorithm for solving LWE (on average) can be converted into a quantum algorithm for approximating the shortest vector problem (GapSVP) and the shortest independent vectors problem (SIVP) in the worst case. Because GapSVP and SIVP are believed to be hard even for quantum algorithms, this gives a strong hardness guarantee for LWE. We also present a public-key encryption scheme whose security reduces to the hardness of LWE: to encrypt a bit , send a random linear combination of the LWE samples plus ; decryption uses the secret key to remove the LWE component and recover from the noise. The LWE problem has become one of the central hardness assumptions of post-quantum cryptography, underlying numerous subsequent schemes including fully homomorphic encryption, digital signatures, and oblivious transfer.