A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
From MaRDI portal
Publication:2875162
DOI10.1145/1806689.1806739zbMATH Open1293.68172DBLPconf/stoc/MicciancioV10OpenAlexW2000956176WikidataQ57567984 ScholiaQ57567984MaRDI QIDQ2875162FDOQ2875162
Authors: 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
Recommendations
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- Complexity and algorithms for computing Voronoi cells of lattices
- Approximate Voronoi cells for lattices, revisited
- scientific article; zbMATH DE number 4062598
- A nearly optimal deterministic parallel Voronoi diagram algorithm
- Approximation on the Voronoi cells of the \(A_d\) lattice
- Computing the Voronoi cell of a lattice: the diamond-cutting algorithm
- Higher-dimensional Voronoi diagrams in linear expected time
- A LINEAR-TIME RANDOMIZED ALGORITHM FOR THE BOUNDED VORONOI DIAGRAM OF A SIMPLE POLYGON
- scientific article; zbMATH DE number 7651184
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cited In (58)
- Concrete analysis of quantum lattice enumeration
- Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
- Post-quantum cryptosystems: open problems and solutions. Lattice-based cryptosystems
- Robust additive randomized encodings from IO and pseudo-non-linear codes
- Improvements in closest point search based on dual HKZ-bases
- Dual lattice attacks for closest vector problems (with preprocessing)
- Finding shortest lattice vectors faster using quantum search
- Correcting noisy exponentiation black-boxes modulo a prime
- New algorithms for minimizing the weighted number of tardy jobs on a single machine
- On the modular inversion hidden number problem
- A fast phase-based enumeration algorithm for SVP challenge through \(y\)-sparse representations of short lattice vectors
- A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices
- On the asymptotic complexity of solving LWE
- Sieving for closest lattice vectors (with preprocessing)
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- How (not) to instantiate ring-LWE
- Approximate Voronoi cells for lattices, revisited
- FPT-algorithms for some problems related to integer programming
- Hardness of approximating the closest vector problem with pre-processing
- Approximate CVP_p in Time 2^{0.802 n}
- New lattice attacks on DSA schemes
- Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method
- Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
- Algorithms for the shortest and closest lattice vector problems
- Finding closest lattice vectors using approximate Voronoi cells
- Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
- Voronoi cells of lattices with respect to arbitrary norms
- Finding shortest lattice vectors in the presence of gaps
- Individual discrete logarithm with sublattice reduction
- Better key sizes (and attacks) for LWE-based encryption
- Lattice sparsification and the approximate closest vector problem
- From approximate to exact integer programming
- Covering convex bodies and the closest vector problem
- Lattice-based algorithms for number partitioning in the hard phase
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- Short paths on the Voronoi graph and closest vector problem with preprocessing
- Approximate CVP\(_p\) in time \(2^{0.802n}\)
- A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
- On approximating the covering radius and finding dense lattice subspaces
- Complexity and algorithms for computing Voronoi cells of lattices
- (Leveled) fully homomorphic encryption without bootstrapping
- The closest vector problem in tensored root lattices of type A and in their duals
- Complexity of optimizing over the integers
- Sampling methods for shortest vectors, closest vectors and successive minima
- A sieve algorithm based on overlattices
- Analysis of Gauss-sieve for solving the shortest vector problem in lattices
- Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes
- Sieve, Enumerate, Slice, and Lift:
- Finding a closest point in a lattice of Voronoi's first kind
- Lower bounds on lattice sieving and information set decoding
- The irreducible vectors of a lattice: some theory and applications
- Approximating the closest vector problem using an approximate shortest vector oracle
- Lattice Point Enumeration on Block Reduced Bases
- On lattice-based algebraic feedback shift registers synthesis for multisequences
- Centerpoints: a link between optimization and convex geometry
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- Improvements in the analysis of Kannan's CVP algorithm
- On the complexity of quasiconvex integer minimization problem
This page was built for publication: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875162)
