A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
From MaRDI portal
Publication:2875162
DOI10.1145/1806689.1806739zbMath1293.68172WikidataQ57567984 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
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Centerpoints: A Link between Optimization and Convex Geometry, Improvements in the analysis of Kannan's CVP algorithm, Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms, (Leveled) Fully Homomorphic Encryption without Bootstrapping, New lattice attacks on DSA schemes, Improvements in closest point search based on dual HKZ-bases, Correcting noisy exponentiation black-boxes modulo a prime, On the modular inversion hidden number problem, Hardness of approximating the closest vector problem with pre-processing, Finding shortest lattice vectors faster using quantum search, On the asymptotic complexity of solving LWE, The closest vector problem in tensored root lattices of type A and in their duals, Sieving for closest lattice vectors (with preprocessing), On lattice-based algebraic feedback shift registers synthesis for multisequences, FPT-algorithms for some problems related to integer programming, Lattice-based algorithms for number partitioning in the hard phase, Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes, On the complexity of quasiconvex integer minimization problem, Finding Shortest Lattice Vectors in the Presence of Gaps, How (Not) to Instantiate Ring-LWE, A sieve algorithm based on overlattices, A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors, Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing, Lattice Point Enumeration on Block Reduced Bases, Algorithms for the Shortest and Closest Lattice Vector Problems, Better Key Sizes (and Attacks) for LWE-Based Encryption, Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices, Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle, A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices
