aqora

Quantum Algorithms for the Approximate k-List Problem and Their Application to Lattice Sieving

Elena Kirshanova, Erik Mårtensson, Eamonn W. Postlethwaite +1 more

Lecture notes in computer scienceJan 1, 201918 citations

Improved Quantum Hypercone Locality Sensitive Filtering in Lattice Sieving.

Max Heiser

Jan 1, 20210 citations

Lattice Sieving via Quantum Random Walks

André Chailloux, Johanna Loyer

arXiv:2105.05608Lecture notes in computer scienceJan 1, 202139 citations

On the Practicality of Quantum Sieving Algorithms for the Shortest Vector Problem

João Fernando Doriguello, George Giapitzakis, Alessandro Luongo +1 more

arXiv:2410.13759Lecture notes in computer scienceJan 1, 20261 citation

Estimating Quantum Speedups for Lattice Sieves

Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite +1 more

Lecture notes in computer scienceJan 1, 202039 citations

Classical and quantum cryptanalysis of lattices and codes

Lynn Engelberts

This thesis studies the security of lattice-based and code-based cryptography, two leading approaches to post-quantum cryptography. Although several lattice-based and code-based schemes have been selected for standardization and deployment, these schemes and their underlying computational problems have received less scrutiny than those they aim to replace. Continued cryptanalysis is therefore essential to build confidence in the security of post-quantum cryptography. The first part of this thesis concerns the classical cryptanalysis of lattice-based cryptography. We provide an algorithm that solves the Short Integer Solution problem in subexponential time for nontrivial parameter regimes. Moreover, we develop a predictive model for analyzing the practical performance of module-BKZ, a module-lattice analog of the BKZ algorithm. The second part considers the quantum cryptanalysis of lattice-based and code-based cryptography, focusing on quantum speedups for sieving algorithms. We present a new quantum algorithm for 3-tuple lattice sieving that yields an improved time-memory trade-off for solving the Shortest Vector Problem. We also introduce quantum algorithms for code sieving and investigate their potential for attacking code-based cryptography. Together, these results provide new insights into the security of lattice-based and code-based cryptography and highlight several directions for future research.This thesis studies the security of lattice-based and code-based cryptography, two leading approaches to post-quantum cryptography. Although several lattice-based and code-based schemes have been selected for standardization and deployment, these schemes and their underlying computational problems have received less scrutiny than those they aim to replace. Continued cryptanalysis is therefore essential to build confidence in the security of post-quantum cryptography. The first part of this thesis concerns the classical cryptanalysis of lattice-based cryptography. We provide an algorithm that solves the Short Integer Solution problem in subexponential time for nontrivial parameter regimes. Moreover, we develop a predictive model for analyzing the practical performance of module-BKZ, a module-lattice analog of the BKZ algorithm. The second part considers the quantum cryptanalysis of lattice-based and code-based cryptography, focusing on quantum speedups for sieving algorithms. We present a new quantum algorithm for 3-tuple lattice sieving that yields an improved time-memory trade-off for solving the Shortest Vector Problem. We also introduce quantum algorithms for code sieving and investigate their potential for attacking code-based cryptography. Together, these results provide new insights into the security of lattice-based and code-based cryptography and highlight several directions for future research.

Jan 1, 20260 citations

An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

Related papers

An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

Related papers