Sieving for closest lattice vectors (with preprocessing)
From MaRDI portal
Publication:1698670
DOI10.1007/978-3-319-69453-5_28zbMath1418.94052arXiv1607.04789OpenAlexW3104264786MaRDI QIDQ1698670
Publication date: 16 February 2018
Full work available at URL: https://arxiv.org/abs/1607.04789
latticesbounded distance decoding (BDD)approximate nearest neighborsShortest Vector problem (SVP)Closest Vector problem (CVP)sieving algorithms
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 n 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)
