Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing

DOI10.1007/978-3-662-47989-6_1zbMath1336.94060OpenAlexW1447686308MaRDI QIDQ3457102

Thijs Laarhoven

Publication date: 10 December 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47989-6_1

zbMATH Keywords

latticessieving algorithmsshortest vector problem (SVP)locality-sensitive hashing (LSH)approximate nearest neighbor problem

Mathematics Subject Classification ID

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

Related Items

How to meet ternary LWE keys ⋮ Lower bounds on lattice sieving and information set decoding ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Gadget-based iNTRU lattice trapdoors ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems ⋮ \textsc{Mitaka}: a simpler, parallelizable, maskable variant of \textsc{Falcon} ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Predicting the concrete security of LWE against the dual attack using binary search ⋮ Lattice Sieving via Quantum Random Walks ⋮ EHNP strikes back: analyzing SM2 implementations ⋮ On the asymptotic complexity of solving LWE ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ Estimating the hidden overheads in the BDGL lattice sieving algorithm ⋮ Post-quantum key exchange for the Internet and the open quantum safe project ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Estimating quantum speedups for lattice sieves ⋮ Gauss Sieve Algorithm on GPUs ⋮ A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$ ⋮ Lattice-based locality sensitive hashing is optimal ⋮ Quantum algorithm design: techniques and applications ⋮ Improved Algorithms for the Approximate k-List Problem in Euclidean Norm ⋮ On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ Advanced lattice sieving on GPUs, with tensor cores ⋮ Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\) ⋮ Revisiting orthogonal lattice attacks on approximate common divisor problems

Uses Software

• NTRU

Cites Work

• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Estimating Key Sizes for High Dimensional Lattice-Based Systems
• A Three-Level Sieve Algorithm for the Shortest Vector Problem
• Better Key Sizes (and Attacks) for LWE-Based Encryption
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Post-Quantum Cryptography
• Sieve algorithms for the shortest vector problem are practical
• On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
• Sieving for Shortest Vectors in Ideal Lattices
• Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice