Public-key cryptosystems from the worst-case shortest vector problem: extended abstract

By Chris Peikert. Symposium on the Theory of Computing, 2009

999 citations recorded by the source corpus.

We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

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

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

In Information Systems

Citations in the corpus

Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems (2009, background): “Recently, Peikert [43] also gave a classical reduction from GapSVP (and variants) to LWE.”
Efficient Fully Homomorphic Encryption from (Standard) LWE (2011, background): “The LWE assumption does not refer to ideals, and indeed, the LWE problem is at least as hard as finding short vectors in any lattice, as follows from the worst-case to average-case reductions of Regev [33] and Peikert [32].”
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].”
Learning Polynomials with Neural Networks (2014, background): “For example, in the boolean case (where x is distributed over the boolean cube), this is at least as hard as ”learning parity with noise” and ”learning juntas” – problems that we suspect do not admit any efficient algorithms and are even used as cryptographic primitives [1, 15, 13, 4].”
On lattices, learning with errors, random linear codes, and cryptography (2009, background): “Roughly speaking, the way Peikert circumvents the difﬁculty we described earlier is by noticing that the existence of an oracle that is able to recover y from y + z , where y is a random lattice point and z is a random perturbation of length at most d , is by itself a useful piece of information as ”
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.”
Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP (2012, methodology): “We refer the reader to [Reg05, Pei09] for more information.”
Key Homomorphic PRFs and Their Applications (2013, background): “Regev [33] shows that for a certain noise distribution χ = Ψα(1), for n polynomial in λ and q > 2 √ n/α, the LWE problem is as hard as the worst-case SIVP and GapSVP under a quantum reduction (see also [31, 13]).”
On the concrete hardness of Learning with Errors (2015, background): “One lattice problem on whose hardness several cryptographic constructions are based is the learning with errors (LWE) problem [65, 67, 69].”
Efficient Public Key Encryption Based on Ideal Lattices (2009, methodology): “Peikert [28] derived a CCA2-secure encryption scheme from the non-structured variant of the trapdoor function family Id-Trap from Figure 1, using the framework of [31,34] for building a CCA2-secure scheme from a collection of injective trapdoor functions that is secure under correlated product (i.”
(Leveled) Fully Homomorphic Encryption without Bootstrapping (2014, positive): “We now present the plain encryption scheme, which is inspired by the schemes of Regev [2005] in the LWE case, or Lyubashevsky et al.”
A Toolkit for Ring-LWE Cryptography (2013, methodology): “Such a lemma is needed for porting many applications of standard SIS and LWE to the ring setting, including SIS-based signature schemes [19, 10, 7, 28], the “primal” [31] and “dual” [19] LWE cryptosystems, chosen ciphertext-secure encryption schemes [29, 28], and (hierarchical) identity-based encryp”
Making NTRU as Secure as Worst-Case Problems over Ideal Lattices (2011, background): “These include CPA and CCA secure encryption schemes, identity-based encryption schemes, digital signatures, etc (see [31,28,11,5,1] among others, and the surveys [24,32]).”
Attribute-based encryption for circuits (2013, background): “…Gaussian error distribution χ = χ ( n ) over Z , the learning with errors assumption dLWE , , ,χ states There are known quantum [Regev 2009] and classical [Peikert 2009] reductions between dLWE n , m , q ,χ and approximating short vector problems in lattices in the worst case, where χ is a B…”