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

DOI10.1145/1806689.1806739zbMath1293.68172OpenAlexW2000956176WikidataQ57567984 ScholiaQ57567984MaRDI QIDQ2875162

Daniele Micciancio, Panagiotis Voulgaris

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806739

zbMATH Keywords

Voronoi cellCVPSVPlattice algorithmsSIVP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (44)

Dual lattice attacks for closest vector problems (with preprocessing) ⋮ Lower bounds on lattice sieving and information set decoding ⋮ New algorithms for minimizing the weighted number of tardy jobs on a single machine ⋮ New lattice attacks on DSA schemes ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Covering convex bodies and the closest vector problem ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Improvements in closest point search based on dual HKZ-bases ⋮ Lattice Point Enumeration on Block Reduced Bases ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Correcting noisy exponentiation black-boxes modulo a prime ⋮ Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method ⋮ Individual discrete logarithm with sublattice reduction ⋮ From approximate to exact integer programming ⋮ On the asymptotic complexity of solving LWE ⋮ The closest vector problem in tensored root lattices of type A and in their duals ⋮ On the complexity of quasiconvex integer minimization problem ⋮ On the modular inversion hidden number problem ⋮ Complexity of optimizing over the integers ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ On lattice-based algebraic feedback shift registers synthesis for multisequences ⋮ Hardness of approximating the closest vector problem with pre-processing ⋮ The irreducible vectors of a lattice: some theory and applications ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ FPT-algorithms for some problems related to integer programming ⋮ Centerpoints: A Link between Optimization and Convex Geometry ⋮ (Leveled) Fully Homomorphic Encryption without Bootstrapping ⋮ Finding Shortest Lattice Vectors in the Presence of Gaps ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ Better Key Sizes (and Attacks) for LWE-Based Encryption ⋮ Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ How (Not) to Instantiate Ring-LWE ⋮ A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices ⋮ Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms ⋮ A sieve algorithm based on overlattices

This page was built for publication: A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations