New directions in nearest neighbor searching with applications to lattice sieving

DOI10.1137/1.9781611974331.ch2zbMath1410.68093OpenAlexW2952033682WikidataQ57567981 ScholiaQ57567981MaRDI QIDQ4575576

Anja Becker, Thijs Laarhoven, Nicolas Gama, Léo Ducas

Publication date: 16 July 2018

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

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

Mathematics Subject Classification ID

Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Data structures (68P05) Approximation algorithms (68W25)

Related Items (66)

Binary vectors for fast distance and similarity estimation ⋮ SoK: how (not) to design and implement post-quantum cryptography ⋮ Dual lattice attacks for closest vector problems (with preprocessing) ⋮ Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography ⋮ Decryption Failure Is More Likely After Success ⋮ How to meet ternary LWE keys ⋮ Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Towards faster polynomial-time lattice reduction ⋮ Lower bounds on lattice sieving and information set decoding ⋮ Homomorphic Encryption Standard ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ How to find ternary LWE keys using locality sensitive hashing ⋮ Making the BKW algorithm practical for LWE ⋮ On a dual/hybrid approach to small secret LWE. A dual/enumeration technique for learning with errors and application to security estimates of FHE schemes ⋮ Gadget-based iNTRU lattice trapdoors ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ \(\mathsf{Rubato}\): noisy ciphers for approximate homomorphic encryption ⋮ \textsc{Mitaka}: a simpler, parallelizable, maskable variant of \textsc{Falcon} ⋮ On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography ⋮ On the Security of OSIDH ⋮ Predicting the concrete security of LWE against the dual attack using binary search ⋮ Estimation of the hardness of the learning with errors problem with a restricted number of samples ⋮ Lattice Sieving via Quantum Random Walks ⋮ New time-memory trade-offs for subset sum -- improving ISD in theory and practice ⋮ Hull attacks on the lattice isomorphism problem ⋮ EHNP strikes back: analyzing SM2 implementations ⋮ Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract) ⋮ Shorter hash-and-sign lattice-based signatures ⋮ On the asymptotic complexity of solving LWE ⋮ Development and analysis of massive parallelization of a lattice basis reduction algorithm ⋮ Does the dual-sieve attack on learning with errors even work? ⋮ Finding short integer solutions when the modulus is small ⋮ Estimating the hidden overheads in the BDGL lattice sieving algorithm ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Lattice-based cryptography: a survey ⋮ \textsf{Orbweaver}: succinct linear functional commitments from lattices ⋮ LaBRADOR: compact proofs for R1CS from Module-SIS ⋮ Revisiting security estimation for LWE with hints from a geometric perspective ⋮ Fast neighbor search by using revised \(k\)-d tree ⋮ Estimating quantum speedups for lattice sieves ⋮ Distance-based index structures for fast similarity search ⋮ Gauss Sieve Algorithm on GPUs ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$ ⋮ Lattice-based locality sensitive hashing is optimal ⋮ Identifying an unknown code by partial Gaussian elimination ⋮ Quantum algorithm design: techniques and applications ⋮ Unnamed Item ⋮ The lattice-based digital signature scheme qTESLA ⋮ Index structures for fast similarity search for real-valued vectors. I ⋮ Index structures for fast similarity search for binary vectors ⋮ Improved Algorithms for the Approximate k-List Problem in Euclidean Norm ⋮ Computing Generator in Cyclotomic Integer Rings ⋮ On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL ⋮ Unnamed Item ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The randomized slicer for CVPP: sharper, faster, smaller, batchier ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ 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)}\) ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation ⋮ A new post-quantum multivariate polynomial public key encapsulation algorithm ⋮ Revisiting orthogonal lattice attacks on approximate common divisor problems

This page was built for publication: New directions in nearest neighbor searching with applications to lattice sieving