A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations

By Daniele Micciancio, Panagiotis Voulgaris. Symposium on the Theory of Computing, 2010

356 citations recorded by the source corpus.

We give deterministic ~O(22n+o(n))-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP). This improves the nO(n) running time of the best previously known algorithms for CVP (Kannan, Math. Operation Research 12(3):415--440, 1987) and SIVP (Micciancio, Proc. of SODA, 2008), and gives a deterministic and asymptotically faster alternative to the 2O(n)-time (and space) randomized algorithm for SVP of (Ajtai, Kumar and Sivakumar, STOC 2001). The core of our algorithm is a new method to solve the closest vector problem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. In the process, we also give algorithms for several other lattice problems, including computing the kissing number of a lattice, and computing the set of all Voronoi relevant vectors. All our algorithms are deterministic, and have 2O(n) time and space complexity.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/30ae0cfd89512c0ea6f4f4447544a9fa2f5226a8

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 Computer Networks and Communications

Citations in the corpus

Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP (2012, methodology): “The best known algorithms for GapSVP γ ([Sch87, MV10]) require at least 2 ˜Ω( n/ log γ ) time.”
BKZ 2.0: Better Lattice Security Estimates (2011, methodology): “There are space-efficient enumeration algorithms [38,20,6,42,43,10] and exponentialspace algorithms [3,36,30,29], the latter being outperformed in practice by the former despite their better asymptotic running time 2O(n).”
Reusable garbled circuits and succinct functional encryption (2013, unknown): “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 .”
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].”
Making NTRU as Secure as Worst-Case Problems over Ideal Lattices (2011, background): “The smallest γ which is known to be achievable in polynomial time is exponential, up to poly-logarithmic factors in the exponent ([33,25]).”
Faster Fully Homomorphic Encryption (2010, background): “The best algorithms for solving them for γ =1 ([14, 22 ]) run in time exponential with respect to the dimension.”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “There are also singleexponential time algorithms for the Shortest Vector Problem [5, 27, 26 ], which can run faster in practice than Schnorr-Euchner enumeration in certain low dimensions; however, these algorithms also require exponential space.”
Locally Private k-Means in One Round (2021, result): “Using known results on lattices (Rogers, 1959; Micciancio, 2004; Micciancio and Voulgaris, 2013), Ghazi et al.”
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…”
On Ideal Lattices and Learning with Errors over Rings (2010, background): “In particular, the asymptotically fastest known algorithms for obtaining an approximation to SVP on ideal lattices to within polynomial factors require time 2 Ω( n ) , just as in the case of general lattices [AKS01, MV10].”
Lattice Enumeration Using Extreme Pruning (2010, background): “(But see [20] for a theoretically important algorithm that combines CVPP and enumeration.”