Fast Lattice Point Enumeration with Minimal Overhead

DOI10.1137/1.9781611973730.21zbMath1372.68140OpenAlexW2951649498MaRDI QIDQ5363033

Daniele Micciancio, Michael Walter

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Cryptography (94A60)

Related Items (17)

Dual lattice attacks for closest vector problems (with preprocessing) ⋮ Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ Scalable revocable identity-based signature over lattices in the standard model ⋮ 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 ⋮ Individual discrete logarithm with sublattice reduction ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors ⋮ Approximate Voronoi cells for lattices, revisited ⋮ A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\)

This page was built for publication: Fast Lattice Point Enumeration with Minimal Overhead