Lattice-Based Post-Quantum Cryptography and Quantum Algorithms
Time: Mon 2025-06-09 14.00
Location: F3 (Flodis), Lindstedtsvägen 26 & 28, Campus
Video link: https://kth-se.zoom.us/j/62914864473
Language: English
Subject area: Computer Science
Doctoral student: Joel Gärtner , Algebra, kombinatorik och topologi
Opponent: Professor Vinod Vaikuntanathan, Massachusetts Institute of Technology, MA, USA
Supervisor: Professor Johan Håstad, Algebra, kombinatorik och topologi
Abstract
The focus of this thesis is the threat that quantum computers pose to asymmetric cryptography. This threat is considered through analysis and development of both quantum algorithms and post-quantum cryptosystems. Lattices are used in both of these areas of this thesis; lattice-based analysis is used for the quantum algorithms and the cryptosystems are lattice-based.
Arguably the most important building block for lattice-based cryptography is the Learning With Errors (LWE) problem. This problem was introduced by Regev in 2005 together with a quantum reduction from standard lattice problems. In this thesis Regev’s reduction is analyzed in detail, allowing for the first parametrization of a cryptosystem whose concrete security actually is based upon this reduction.
Another important problem used for lattice-based cryptography is the NTRU problem, which was introduced several years before the LWE problem. In this thesis, the NTWE problem is introduced as a natural combination of the NTRU and LWE problems with NTWE-based cryptosystems having certain benefits over comparable NTRU and LWE-based systems.
The quantum algorithms considered in this thesis are variants of Regev’s recently introduced quantum factoring algorithm. When attacking factoring-based cryptography, Regev’s algorithm has certain asymptotic advantages over previous quantum algorithms. As a part of this thesis, variants of Regev’s algorithm for solving other cryptographically relevant problems are introduced. Additionally, by analyzing the lattice-based classical post-processing of the algorithm, it is argued that the algorithm can be made robust to quantum errors.
Although Regev’s new algorithm, and the variations thereof, have an asymptotic advantage over previous quantum algorithms, an advantage for the concrete instances that are used for cryptography would arguably be more interesting. This motivates comparing the concrete efficiency of variants of Regev’s algorithm to that of previous quantum algorithms. Such a comparison is part of this thesis and — based on this comparison — it seems like previously available algorithms still are the best choice for quantum attacks against traditional cryptography.
The final contribution of this thesis is a new lattice-based digital signature scheme. Similar signature schemes have been considered before, such as with the recently standardized ML-DSA. However, compared to similar signature schemes, the new scheme is significantly more compact. This is in large part thanks to developing a new technique for constructing signatures, but also to some extent from being based on the NTWE problem instead of a variant of the LWE problem.