Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems

By Benny Applebaum, David Cash, Chris Peikert, Amit Sahai. Annual International Cryptology Conference, 2009

656 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/b428a5232b6c3e6a3abc3345df3ffbda8ed820e6

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

In Computational Theory and Mathematics

Citations in the corpus

Pseudorandom Functions: Three Decades Later (2017, background): “(LWE is no easier to solve for such short secrets [10].”
On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption (2012, neutral): “This presentation is more useful for the purposes of this paper and it turns out to be equivalent to the original one up to obtaining one additional sample [2, 35].”
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM (2017, methodology): “1It should be noted that this cryptoscheme design, as well as the result from [5] applied to the Learning Parity with Noise (LPN) problem, was already present much earlier in the work of Alekhnovich [3] in which he constructed a cryptosystem based on the hardness of the LPN problem.”
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE (2012, background): “The work of [1] shows that, when q is a prime power, then LWEn,q,χ,χ is as hard as LWEn,q,U(Zq),χ.”
Foundations of garbled circuits (2012, methodology): “In the symmetric-key setting, the LPN scheme of Applebaum, Cash, Peikert, and Sahai (ACPS) [3] is a projection-KDM secure encryption scheme.”
Public-Key Cryptosystems Resilient to Key Leakage (2009, background): “in fact satisfies this more general notion with respect to the class of all affine functions (see also [7, 17] for additional schemes that are secure against affine functions, and [6, 8, 18] for schemes that are secure against more general classes of functions).”
Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP (2012, background): “It is known (see e.g. [ACPS09]) that the hardness of LWE remains essentially the same if we sample s $ ← χ n (instead of uniformly in Z n q ).”
Homomorphic Encryption for Arithmetic of Approximate Numbers (2017, background): “It turned out to be equivalent to sample the secret s from the noise distribution χ [1, 31].”
Worst-case to average-case reductions for module lattices (2014, methodology): “Independently, many variants of LWE have been shown as hard as Regev’s original LWE: These variants may consist in sampling the secret vector s from the same distribution as the errors [3], in sampling the error vectors from other distributions [14,34] and in relaxing the conditions on the factorisa”
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (2012, methodology): “To achieve our goal, we first use the normal form of LWE problem suggested in [4] which means that the secret vector (ring element) in the LWE (RLWE) samples can be sampled from the error distribution.”