Classical hardness of learning with errors

By Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé. Symposium on the Theory of Computing, 2013

743 citations recorded by the source corpus.

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/3eaa16c314c1c4d5666dbb0459d4129d9235070c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM (2017, methodology): “One of the major achievements of Regev’s work was the introduction of an intermediate problem – the Learning With Errors (LWE) Problem – which was relatively simple to use in cryptographic constructions and asymptotically at least as hard as some standard worst-case lattice problems [23, 59].”
FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second (2015, methodology): “As a last technique, in order to contain noise generation during key switching operations, we use LWE instances with binary secrets, which were recently proved as hard as standard LWE in [7].”
Post-quantum Key Exchange - A New Hope (2016, background): “A simple security reduction to rounded Gaussians.”
Hardness of SIS and LWE with Small Parameters (2013, methodology): “In order to conclude that the LWE function is pseudorandom (under worstcase lattice assumptions) for uniformly random small errors, we combine Theorem 5 with previous hardness results [26,23,7] and search-to-decision reductions [18,19].”
Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds (2016, methodology): “For an asymptotical security analysis, since the phase is lipschitzian, TLWE samples can be equivalently mapped to their closest binLWE (or bin-RingLWE), which in turn can be reduced to standard LWE/ringLWE with full secret using the modulus-dimension reduction [6] or group-switching techniques [13]”
On the concrete hardness of Learning with Errors (2015, methodology): “On the one hand, theoretical results show that for an LWE instance with a binary secret to be as hard as general LWE in dimension n a dimension of n log q is su cient [18, 57].”
Worst-case to average-case reductions for module lattices (2014, background): “Finally, it could be of interest to adapt the main result of [8] to the M-LWE/R-LWE setting.”
Homomorphic Encryption (2017, background): “Follow-up work [79, 18] described classical reductions of some other worst-case problems to LWE with similar dependence on α.”
Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, background): “17 Recent works [1,26,70,72,86] use a small modulus and larger dimension, but our “native” modulus is already a large one.”
Efficient Secure Matrix Multiplication Over LWE-Based Homomorphic Encryption (2016, background): “According to [2], the condition q ≡ 1 mod 2n is not necessary for the construction and the security but for the efficiency of the scheme.”
Improving TFHE: faster packed homomorphic operations and efficient circuit bootstrapping (2017, methodology): “Distinguishing TLWE encryptions of 0 from random samples in TN [X] × TN [X] is equivalent to the LWE problem initially defined by Regev [28] and its ring [25] and Scale invariant [6, 11, 13] variants.”
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (2012, background): “[8] even shows the classical hardness of LWE for any polynomial q but the security losses with about a √ n factor.”