Classical and Quantum Cryptanalysis of Lattices and Codes
Lynn Engelberts

Abstract:
In online environments, most people expect their data and communications to remain private and to be readable only by the intended recipients. While this expectation is often taken for granted, it is not easy to design practical mechanisms for securing our online data and communications. The field that develops such mechanisms is called cryptography, and these mechanisms are often referred to as cryptographic schemes and protocols. For example, an encryption scheme enables two parties to send a private message over a public channel such as the internet: before the message is sent, it is hidden (encrypted) using some mathematical operation that can be reversed (decrypted) using an associated secret key. The intended recipient can then recover the original message if they know this secret key. Of course, the purpose of encryption is defeated if the message can be recovered by someone without prior knowledge of the secret key, such as by guessing the key or by exploiting some patterns in the encryption method that reveal part of the message. We therefore want some guarantees that such attacks are impossible or at least computationally too expensive to be performed in practice. 
For most cryptographic schemes used in practice, we do not know how to mathematically prove such strong security guarantees. Fortunately, the ability to attack a scheme can often be related to solving a well-studied computational problem. If it is widely believed that no efficient algorithms exist for this computational problem, then this belief may contribute to confidence in the scheme's security. More generally, confidence is built through extensive but unsuccessful attempts to find weaknesses in the scheme and its related computational problems. These efforts fall under the field of cryptanalysis, which analyzes cryptographic constructions by adopting the mindset of an attacker. 

An attacker may have capabilities beyond ordinary computation, since our physical universe is understood to be fundamentally quantum. The concept of a quantum computer stems from the 1980s, and employs a model of computation based on the laws of quantum mechanics. These laws enable forms of computation that are not feasible on a classical (i.e., non-quantum) computer, and in some cases lead to so-called quantum speedups for certain computational problems. The first sign that quantum speedups could have practical implications came in 1994, when Peter Shor designed a quantum algorithm that solves the integer factorization and discrete logarithm problems exponentially faster than all known classical algorithms. The security of various cryptographic schemes that have been widely deployed, including RSA and elliptic-curve cryptography, relies on the assumed difficulty of these problems. Shor's result therefore renders a large portion of currently-used cryptography insecure against attackers with sufficiently powerful quantum computers. 
Recent progress in quantum hardware has made this threat to cryptography more urgent and has necessitated the development of post-quantum cryptography: cryptography based on computational problems for which no efficient classical or quantum algorithms are believed to exist. Many candidates for post-quantum cryptography have been proposed and analyzed, stimulated by a standardization effort that was initiated by the US National Institute of Standards and Technology (NIST) in 2016. While a few post-quantum schemes have now been standardized, the migration to post-quantum cryptography is considered a difficult and time-consuming task. It also remains vitally important to continue cryptanalysis of these standards in order to increase our confidence in their security, not least because the newer post-quantum schemes and their underlying computational problems have received far less scrutiny than the schemes that they replace. Indeed, as illustrated by Shor's discovery, new (quantum) attacks may continue to emerge in the future. 

In this thesis, we focus on the cryptanalysis of lattice-based and code-based cryptography, two of the most promising candidates for post-quantum cryptography, from which multiple schemes have been selected for standardization by NIST. We investigate their security by designing and analyzing algorithms for their underlying computational problems, often building on variants of existing attack strategies. 
In Part I, we present our contributions to classical lattice-based cryptanalysis. We study the Short Integer Solution problem (SIS), a foundational problem in lattice-based cryptography that underlies the security of the NIST standard ML-DSA. Using a more abstract view of a prior algorithm and discrete-Gaussian techniques, we obtain a subexponential-time algorithm for nontrivial instances of SIS. Fortunately for cryptography, this asymptotic result does not seem to threaten the concrete security of ML-DSA. Our second contribution is motivated by the fact that most practical lattice-based schemes (including all current standards) consider lattices equipped with additional algebraic structure. We analyze whether this structure can be exploited in lattice attacks, focusing on a structured analog of the BKZ algorithm called module-BKZ. Using a heuristic analysis supported by experiments, we develop a model that enables a performance comparison between module-BKZ and BKZ, allowing us to identify algebraic properties that appear to make structured instances more vulnerable to attack. 
In Part II, we switch to the perspective of an attacker with access to a quantum computer, and consider the quantum cryptanalysis of lattice-based and code-based cryptography. We explore how quantum algorithms can speed up lattice sieving methods, which are currently the fastest known algorithms for solving the Shortest Vector Problem (SVP), another central problem in lattice-based cryptography closely related to SIS. Roughly speaking, we present a quantum algorithm that achieves a better time-memory trade-off for SVP, using a carefully nested quantum algorithm combined with classical preprocessing. In addition, we investigate whether similar techniques can lead to faster quantum attacks on code-based cryptography. Building on recent work that extended the classical framework of lattice sieving to the setting of codes, we show how to also translate their quantum analogs to code sieving. While we achieve quantum speedups for code sieving itself, we show that this does not result in an improved quantum attack on code-based cryptography. 

Conceptually, this thesis illustrates the importance of finding the right level of abstraction and an appropriate set of tools for cryptanalysis. Our asymptotic results on SIS, quantum lattice sieving, and quantum code sieving benefited from viewing the targeted problem and prior algorithms from a high-level perspective. On the other hand, our analysis of the practical performance of module-BKZ was guided by taking a closer look at the internal algebraic structure of lattices used in cryptographic constructions, and by running concrete numerical experiments. Another key takeaway is that asymptotic speedups do not necessarily lead to faster attacks in practice, since the concrete cost of competing algorithms may be much lower than asymptotic upper bounds suggest. This highlights the significance of complementing theory with experiments and heuristic models where available. 

Taken together, the results in this thesis address some natural questions in lattice-based and code-based cryptanalysis, and identify several next steps towards a better understanding of lattice-based and code-based cryptography.