Estimating quantum speedups for lattice sieves

DOI10.1007/978-3-030-64834-3_20OpenAlexW3112217460MaRDI QIDQ2692396

John M. Schanck, Eamonn W. Postlethwaite, Vlad Gheorghiu, Martin R. Albrecht

Publication date: 21 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-64834-3_20

Mathematics Subject Classification ID

Cryptography (94A60) Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)

Related Items (7)

Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS ⋮ Lattice Sieving via Quantum Random Walks ⋮ Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract) ⋮ Estimating the hidden overheads in the BDGL lattice sieving algorithm ⋮ 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)}\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shortest vector from lattice sieving: a few dimensions for free
• Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
• Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE
• Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
• The general sieve kernel and new records in lattice reduction
• Applying Grover’s Algorithm to AES: Quantum Resource Estimates
• Efficient (Ideal) Lattice Sieving Using Cross-Polytope LSH
• Tuning GaussSieve for Speed
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Tuple lattice sieving
• Better Key Sizes (and Attacks) for LWE-Based Encryption
• Quantum Random Access Memory
• 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
• Lattice-based Cryptography
• New directions in nearest neighbor searching with applications to lattice sieving
• Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
• Surface code quantum computing by lattice surgery
• On the robustness of bucket brigade quantum RAM
• A sieve algorithm for the shortest lattice vector problem

This page was built for publication: Estimating quantum speedups for lattice sieves