Sieving for closest lattice vectors (with preprocessing)

DOI10.1007/978-3-319-69453-5_28zbMath1418.94052arXiv1607.04789OpenAlexW3104264786MaRDI QIDQ1698670

Thijs Laarhoven

Publication date: 16 February 2018

Full work available at URL: https://arxiv.org/abs/1607.04789

zbMATH Keywords

latticesbounded distance decoding (BDD)approximate nearest neighborsShortest Vector problem (SVP)Closest Vector problem (CVP)sieving algorithms

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Related Items (9)

Dual lattice attacks for closest vector problems (with preprocessing) ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP ⋮ Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices ⋮ The irreducible vectors of a lattice: some theory and applications ⋮ A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$ ⋮ Approximate Voronoi cells for lattices, revisited ⋮ The randomized slicer for CVPP: sharper, faster, smaller, batchier ⋮ A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic

Cites Work

• Unnamed Item
• Unnamed Item
• Hardness of approximating the closest vector problem with pre-processing
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• A hierarchy of polynomial time lattice basis reduction algorithms
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Sieving for shortest vectors in ideal lattices: a practical perspective
• The inapproximability of lattice and coding problems with preprocessing
• Efficient (Ideal) Lattice Sieving Using Cross-Polytope LSH
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• A sieve algorithm based on overlattices
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing
• Tuning GaussSieve for Speed
• A Three-Level Sieve Algorithm for the Shortest Vector Problem
• Tuple lattice sieving
• Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices
• A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices
• BKZ 2.0: Better Lattice Security Estimates
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• Sieve algorithms for the shortest vector problem are practical
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• Lattice Enumeration Using Extreme Pruning
• The hardness of the closest vector problem with preprocessing
• New directions in nearest neighbor searching with applications to lattice sieving
• Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
• Closest point search in lattices
• Sieving for Shortest Vectors in Ideal Lattices
• A sieve algorithm for the shortest lattice vector problem
• Fast Lattice Point Enumeration with Minimal Overhead
• Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice

This page was built for publication: Sieving for closest lattice vectors (with preprocessing)