On lattices, learning with errors, random linear codes, and cryptography

By Oded Regev. 2005

3,832 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Privacy-Preserving Ridge Regression on Hundreds of Millions of Records (2013, methodology): “Examples include Regev's scheme [5] and Paillier's scheme [4].”
Efficient and Privacy-Enhanced Federated Learning for Industrial Artificial Intelligence (2020, background): “A LWE [28] Deﬁnition 2 (Augmented LWE (A-LWE)): Let κ, τ, p, l be integers, and let f be a function whose the outputs are indistinguishable from random ones.”
New Algorithms for Learning in Presence of Errors (2011, methodology): “We also apply the linearization technique to give a subexponential algorithm for the LWE problem with noise rate below √ n, which clarifies why existing hardness results (which show that LWE is as hard as lattice approximation [18, 16]) did not extend to this case.”
Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography (2016, unknown): “Since its introduction by Regev [27], the Learning With Errors (LWE) problem has been used as the foundation for many new lattice-based constructions with a variety of cryptographic functionalities.”
Pseudorandom Functions: Three Decades Later (2017, background): “While the dimension n is the main hardness parameter, the error rate α also plays an important role: as long as αq exceeds √ n or so, LWE is as hard as approximating conjectured hard problems on lattices to within Õ(n/α) factors in the worst case [125, 118, 97].”
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, methodology): “There are a variety of (incomparable) search/decision reductions for LWE under certain conditions on the parameters (e.g., [Reg05, Pei09b, ACPS09]); in Section 3 we give a reduction that essentially subsumes them all.”
Computational Differential Privacy from Lattice-Based Cryptography (2017, methodology): “Moreover, in [31] the average-case-hardness of the search problem was established by the construction of an eﬃcient quantum algorithm for worst-case lattice problems using an eﬃcient solver of the LWE problem if the error distribution χ is a discrete Gaussian distribution.”
Somewhat Practical Fully Homomorphic Encryption (2012, background): “The RLWE problem is simply a ring based version of the LWE problem [17] and is formulated as follows.”
Function Secret Sharing (2015, background): “We note that our barriers for general FSS from weak assumptions do not apply to FHE-based constructions, leaving open the possibility of realizing our general notion of FSS from FHE or speciﬁc assumptions such as LWE.”