Costing Adversaries on Quantum-secure Cryptography

Technological advancement in the 21st century, such as quantum computers, may pose a significant threat to the security of digital information. At the forefront of security stands cryptography, which is, in 2024, an integral com-
ponent of almost every electronic device, ensuring the security of information at rest, in use, or in motion.
While quantum computers hold the potential of being able to solve complex problems for science, they also pose a significant risk to the cryptographic schemes in use right now. This is because quantum computing may offer a
substantial increase in computational power, having the potential to break cryptographic protocols that are (believed to be) secure when attacked with conventional computers.
Consequently, quantum-secure cryptographic protocols may become essential in the near future, necessitating immediate efforts towards standardization to ensure preparedness. The National Institute of Standards and Technology (NIST) initiated a public competition to identify viable quantum-secure cryptographic algorithms. It is important to recognize, that new cryptographic schemes often come with significant flaws. ... mehrAs such a public evaluation of protocols — following Kerckhoffs’s principle, which advocates that the security should solely depend on the secrecy of the key — is essential.
The flaws that can be found in cryptographic protocols range from bugs in the implementation, over side-channel attacks to cases where the underlying computationally hard problem is not as difficult as expected. It is necessary, to conduct a thorough analysis of these schemes to identify and address these flaws, ensuring robust and secure cryptographic protocols for the future. This thesis provides insight into the real-world security of quantum-
secure protocols proposed in the NIST post-quantum competition and beyond. Furthermore, we review what security properties can be achieved if secure post-quantum schemes exist, and what security guarantees may remain even
without any quantum-secure hardness assumption.
Our first contribution is the analysis of three candidates of the NIST competition, their implementations and their underlying hardness assumptions. More specifically, we provide a novel attack that exploits decryption failures
in Mersenne-based cryptography, which is applicable to two candidates from the first round of the NIST competition. We provide an implementation of our attack on one of these cryptosystems and show how an attacker can
retrieve the secret key. Finally, we identify an attackers abilities to forge universal signatures in the hash-based signature scheme SPHINCS+ , which was analyzed as a round three candidate and a finalist to the competition in
2022. We analyze the concrete cost to mount an attack on a fault tolerant quantum computer. Subsequently, we investigate lower bounds on the cost of performing quantum lattice enumeration and report how our findings
impact the security of Kyber, a lattice-based finalist in the NIST competition. We support our results with experiments and implementations that allow to reproduce our results, and to apply our methodology to estimate the cost of
related cryptographic schemes.
Our second contribution quantifies the security of key agreement protocols against quantum-attackers. We review the security of LDACS, a ground-to-air communication protocol under standardization by the International
Civil Aviation Organization. The analysis focuses on the security properties that LDACS can achieve in a post-quantum world with the deployed mutual authenticated key exchange. Particularly, we answer the question which
security properties are achieved, when LDACS is instantiated with any post-quantum secure key encapsulation mechanism, for instance, any of the NIST post-quantum finalists. Finally, we explore what security one may achieve in
the setting of password authenticated key exchange (PAKE) without a post-quantum hardness assumption, in a world were quantum computing is still expensive. In this setting one can perform a quantum-annoying PAKE, which
means, that the adversarial cost can be scaled with the size of a password space. We are the first to show how an asymmetric PAKE can be enhanced to provide quantum-annoying security on top of its conventional computational
security.