Worst-case to average-case reductions based on Gaussian measures

By Daniele Micciancio, Oded Regev. 2004

1,292 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

On lattices, learning with errors, random linear codes, and cryptography (2009, methodology): “So far, such iterative techniques have been used only in the construction of lattice-based oneway functions [2, 12, 27, 29].”
Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE (2010, background): “The ﬁrst property follows from Lemma 4.4 of [MR07].”
Trapdoors for hard lattices and new cryptographic constructions (2008, methodology): “Our review of Gaussian measures over lattices follows the development by prior works [51, 2, 40].”
Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems (2009, neutral): “, [40, 46, 25]).”
Discrete Gaussian Leftover Hash Lemma over Infinite Domains (2013, background): “As in [10], for lattice L and real > 0, the smoothing parameter of L, denoted η (L), is defined as the smallest s such that ρ1/s(L ∗ \ {0}) ≤ .”
New lattice based cryptographic constructions (2003, result): “Finally, let us mention that a recent paper [24] greatly improves on our result as well as on all previous results.”
GGHLite: More Efficient Multilinear Maps from Ideal Lattices (2014, neutral): “Introduced by [15], the smoothing parameter ηε(Λ) of an n-dimensional lattice Λ and a real ε > 0 is defined as the smallest s such that ρ1/s(Λ∗ \ {0}) ≤ ε.”
Worst-case to average-case reductions for module lattices (2014, neutral): “The smoothing parameter of a lattice was introduced by [28].”
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (2009, background): “required Õ(n(2)) time and space [2,24], and in public-key cryptosystems, the keys were on the order of megabytes [3,33,34,28] (also see [25] for concrete parameter proposals for the scheme in [34]).”
Faster exponential time algorithms for the shortest vector problem (2010, methodology): “In this section we review standard definitions and notation used in the algorithmic study of lattices, mostly following [20].”
On Ideal Lattices and Learning with Errors over Rings (2010, background): “Micciancio and Regev [MR04] introduced a lattice quantity called the smoothing parameter , and related it to various lattice quantities.”
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, background): “Let Λ ⊂ R n be a lattice, let c ∈ R n , and let Σ ≥ 0 be a positive semideﬁnite matrix such that We recall the deﬁnition of the smoothing parameter from [MR04], generalized to non-spherical (and potentially degenerate) Gaussians.”
Homomorphic Signatures for Polynomial Functions (2011, methodology): “Ideal lattices also appear in the lattice-based public key encryption schemes of Stehle et al. [37] and Lyubashevsky, Peikert, and Regev [26] and in the hash functions of Lyubashevsky and Micciancio [25].”
On lattices, learning with errors, random linear codes, and cryptography (2005, methodology): “The motivation for this definition (and the name ‘smoothing parameter’) comes from the following result, shown in [16].”
Classical hardness of learning with errors (2013, methodology): “We recall the definition of the smoothing parameter from [34].”