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
Sieve, Enumerate, Slice, and Lift:, 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, Approximate CVP_p in Time 2^{0.802 n}, Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method, Individual discrete logarithm with sublattice reduction, From approximate to exact integer programming, Complexity of optimizing over the integers, (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, Dual lattice attacks for closest vector problems (with preprocessing), New algorithms for minimizing the weighted number of tardy jobs on a single machine, 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, Approximate Voronoi cells for lattices, revisited, Approximate CVP\(_p\) in time \(2^{0.802n}\), Lower bounds on lattice sieving and information set decoding, Covering convex bodies and the closest vector problem, Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes, On the complexity of quasiconvex integer minimization problem, The irreducible vectors of a lattice: some theory and applications, 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
