A sieve algorithm for the shortest lattice vector problem

By M. Ajtai, Ravi Kumar, D. Sivakumar. Symposium on the Theory of Computing, 2001

613 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/0e0c3c13e95d786484316ba8617f225d3d8b019a

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, background): “The best known polynomial time algorithms for them yield only mildly subexponential approximation factors [24, 38, 5].”
Efficient Fully Homomorphic Encryption from (Standard) LWE (2011, background): “We only note here that the best known algorithms for these problems run in time nearly exponential in the dimension n [3], [29].”
On agnostic boosting and parity learning (2008, methodology): “We remark that the algorithm of Blum et al [4] has been shown to have applications to a variety of other problems, such as determining the shortest lattice vector [1].”
Attribute-based encryption for circuits (2013, background): “The state-of-the-art algorithms for these lattice problems run in time nearly exponential in the dimension n [Ajtai et al. 2001; Micciancio and Voulgaris 2010]; more generally, we can get a 2 -approximation in time 2 . with the connection to LWE, this means that the dLWE n , m , q ,χ assumption is…”
Lattice Enumeration Using Extreme Pruning (2010, methodology): “An alternative algorithmic technique for solving lattice problems was suggested in 2001 by Ajtai, Kumar, and Sivakumar [4] (see also [5,26,21,29] for recent improvements).”
Generalized Compact Knapsacks Are Collision Resistant (2006, background): “The asymptotically fastest algorithm for computing the shortest vector exactly takes time 2 [3] and the best polynomial time algorithm approximates the shortest vector to within a factor of 2 n log log n log n ) [3],[20],[12].”
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions (2002, methodology): “in (probabilistic) polynomial time using more complex algorithms (Ajtai et al. 2001; Schnorr 1987), but they offer no advantages in the context of our paper.”
A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem (2003, methodology): “On the algorithm side, the sieve in Algorithm 1 is similar to a sieve algorithm for a learning problem due to Blum, Kalai, and Wasserman [5] and to a sieve to find shortest vector in a lattice due to Ajtai, Kumar, and Sivakumar [1].”
On Ideal Lattices and Learning with Errors over Rings (2010, background): “The best known algorithms for ideal lattices perform essentially no better than their generic counterparts, which require exponential time and space to achieve a poly(n) approximation factor [3].”
Faster exponential time algorithms for the shortest vector problem (2010, methodology): “2 Overview In this paper we improve on [4, 21] both in theory and in practice, proposing new variants of the sieve algorithm with better exponential worstcase running time and space complexity bounds, and better practical performance.”
Faster Fully Homomorphic Encryption (2010, background): “The best algorithms for solving them for γ = 1 ([14, 2, 3]) run in time exponential with respect to the dimension.”
(Leveled) Fully Homomorphic Encryption without Bootstrapping (2014, neutral): “We only note here that the best-known algorithms for these problems run in time nearly exponential in the dimension n [Ajtai et al. 2001; Micciancio and Voulgaris 2010].”
The Two Faces of Lattices in Cryptology (2001, methodology): “Using Schnorr's algorithm [121], this can be improved to 2 O(d(loglogd) 2 =logd) in polynomial time, and even further to 2 O(dloglogd=logd) in randomized polynomial time using [6], due to Kannan's link between CVP and SVP (see previous section).”
Efficient Public Key Encryption Based on Ideal Lattices (2009, methodology): “The best polynomial time algorithm [4,35] solves γSVP only for a slightly subexponential γ.”
Reusable garbled circuits and succinct functional encryption (2013, neutral): “The best known algorithms to solve these lattice problems with an approximation factor 2 ℓ ϵ in ℓ -dimensional lattices run in time 2 ˜ O ( ℓ 1 − ϵ ) [3, 39] for any constant 0 ϵ 1 .”
Lattice-Based Cryptography (2006, background): “This was recently improved to 2 log log n/ log n) [19].”