Lattice Sieving via Quantum Random Walks

DOI10.1007/978-3-030-92068-5_3zbMath1514.94058arXiv2105.05608OpenAlexW4205104754MaRDI QIDQ6045073

Unnamed Author, André Chailloux

Publication date: 26 May 2023

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

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

zbMATH Keywords

lattice-based cryptographypost-quantum cryptography

Mathematics Subject Classification ID

Cryptography (94A60) Quantum cryptography (quantum-theoretic aspects) (81P94)

Related Items (3)

Finding many collisions via reusable quantum walks. Application to lattice sieving ⋮ Shorter hash-and-sign lattice-based signatures ⋮ Concrete security from worst-case to average-case lattice reductions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding shortest lattice vectors faster using quantum search
• Factoring polynomials with rational coefficients
• Quantum information set decoding algorithms
• Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
• Estimating quantum speedups for lattice sieves
• Improved classical and quantum algorithms for subset-sum
• Efficient (Ideal) Lattice Sieving Using Cross-Polytope LSH
• Optimal Data-Dependent Hashing for Approximate Near Neighbors
• Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing
• A Three-Level Sieve Algorithm for the Shortest Vector Problem
• Search via Quantum Walk
• Quantum Random Access Memory
• 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
• Similarity estimation techniques from rounding algorithms
• Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
• On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
• New directions in nearest neighbor searching with applications to lattice sieving
• Quantum Algorithms for the Subset-Sum Problem
• On the robustness of bucket brigade quantum RAM
• Fully homomorphic encryption using ideal lattices
• Beyond Locality-Sensitive Hashing
• Quantum Walk Algorithm for Element Distinctness

This page was built for publication: Lattice Sieving via Quantum Random Walks