Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing

DOI10.1007/978-3-319-22174-8_6zbMath1370.94521OpenAlexW1192290872MaRDI QIDQ2946443

Benne de Weger, Thijs Laarhoven

Publication date: 17 September 2015

Published in: Progress in Cryptology -- LATINCRYPT 2015 (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/faster-sieving-for-shortest-lattice-vectors-using-spherical-localitysensitive-hashing(b133b3d2-526c-44f0-afd2-9b47e68665a6).html

zbMATH Keywords

lattice cryptographysieving algorithmsnearest neighbor problemshortest vector problem (SVP)locality-sensitive hashing (LSH)

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60)

Related Items (7)

Lower bounds on lattice sieving and information set decoding ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Lattice Sieving via Quantum Random Walks ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ Estimating the hidden overheads in the BDGL lattice sieving algorithm ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding shortest lattice vectors faster using quantum search
• 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
• Efficient (Ideal) Lattice Sieving Using Cross-Polytope LSH
• Estimating Key Sizes for High Dimensional Lattice-Based Systems
• 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
• Optimal Data-Dependent Hashing for Approximate Near Neighbors
• Tuning GaussSieve for Speed
• A Three-Level Sieve Algorithm for the Shortest Vector Problem
• 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
• 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
• Post-Quantum Cryptography
• Sieve algorithms for the shortest vector problem are practical
• Lattice Enumeration Using Extreme Pruning
• Similarity estimation techniques from rounding algorithms
• On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
• Sieving for Shortest Vectors in Ideal Lattices
• Fully homomorphic encryption using ideal lattices
• A sieve algorithm for the shortest lattice vector problem
• Locality-sensitive hashing scheme based on p-stable distributions
• Fast Lattice Point Enumeration with Minimal Overhead
• Beyond Locality-Sensitive Hashing
• Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing