Quantum computers offer a novel approach to data processing, which poses both opportunities and threats for modern cryptography. While Shor’s algorithm for prime factorisation demonstrated the possible impact of quantum cryptanalysis, the complete quantum significance in the cryptanalytical context still needs further research. This thesis compiles a series of recent publications, each of which examines a distinct application of quantum advantage in cryptography. Collectively, these contributions constitute a non-exhaustive compendium of recent advancements in quantum cryptanalysis. We first examine applications of the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear equation systems. We propose two approaches in which the quantum advantage of the HHL algorithm could be leveraged to investigate structural properties relevant to symmetric cryptanalysis. In the subsequent chapter, an analysis is conducted on the significance of adiabatic quantum computing and its role in the cryptanalytical setting. Together, these results offer novel insights into the capabilities and limitations of quantum-enhanced cryptanalysis of symmetric ciphers. Turning to asymmetric settings, two quantum attacks are proposed that result in the complete break of the underlying ciphers. The first one exploits the recipient’s encryption process to extract the secret key used in the Quantum Encryption Method. The second targets an Identity-Based Encryption scheme whose security relies on isogenies. We demonstrate that the distinct use of isogenies introduces new attack vectors for both classical and quantum adversaries. Collectively, these contributions deepen the understanding of quantum-enhanced cryptanalysis, thereby clarifying both its potential and current boundaries.
Quantum computers offer a novel approach to data processing, which poses both opportunities and threats for modern cryptography. While Shor’s algorithm for prime factorisation demonstrated the possible impact of quantum cryptanalysis, the complete quantum significance in the cryptanalytical context still needs further research. This thesis compiles a series of recent publications, each of which examines a distinct application of quantum advantage in cryptography. Collectively, these contributions constitute a non-exhaustive compendium of recent advancements in quantum cryptanalysis. We first examine applications of the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear equation systems. We propose two approaches in which the quantum advantage of the HHL algorithm could be leveraged to investigate structural properties relevant to symmetric cryptanalysis. In the subsequent chapter, an analysis is conducted on the significance of adiabatic quantum computing and its role in the cryptanalytical setting. Together, these results offer novel insights into the capabilities and limitations of quantum-enhanced cryptanalysis of symmetric ciphers. Turning to asymmetric settings, two quantum attacks are proposed that result in the complete break of the underlying ciphers. The first one exploits the recipient’s encryption process to extract the secret key used in the Quantum Encryption Method. The second targets an Identity-Based Encryption scheme whose security relies on isogenies. We demonstrate that the distinct use of isogenies introduces new attack vectors for both classical and quantum adversaries. Collectively, these contributions deepen the understanding of quantum-enhanced cryptanalysis, thereby clarifying both its potential and current boundaries.
In this thesis, we study the security of cryptographic systems against an adversary who has access to a quantum computer. In quantum computing, we studied the hidden period and hidden shift problems, which are among the few known problems that have some applications in cryptogaphy and for which the best known quantum algorithm is more than polynomially faster than the best known classical algorithm. We proposed some improvements, new tradeoffs between classical and quantum time and memory, and extended their scope of applications to cases where only a classical oracle is available. In cryptanalysis, in symmetric cryptography, we proposed some attacks against symmetric constructions based on hidden shifts, and generalized many attacks using hidden periods to cases where the construction is only accessible classically. We proposed a quantum cryptanalysis of the different versions of the authenticated cipher AEZ and some quantum versions of multiple slide attacks, which are a classical family of cryptanalyses. This rewriting of attacks in the formalism of hidden periods has allowed us to propose a new classical attack against multiple variants of the cipher MiMC. In asymmetric cryptography, we proposed a concrete and asymptotic quantum security analysis of some isogeny-based key exchanges. Finally, we studied quantum security in some cases where these hidden structure problems do not apply, with in particular the first quantum security analysis of AES, the most used symmetric cipher to date.
The advent of quantum computing poses an existential threat to classical cryptographic systems. Shor’s algorithm (1994) can factor large integers and compute discrete logarithms in polynomial time, breaking widely used schemes like RSA, ECC, and Diffie-Hellman. This paper surveys the state-of-the-art in quantum cryptanalysis, examining its impact on symmetric and asymmetric cryptography, recent progress in quantum attacks, and defenses via post-quantum cryptography (PQC). We analyze key quantum algorithms (Shor’s, Grover’s), their real-world feasibility given current hardware (NISQ-era limitations), and emerging PQC standards (NIST’s CRYSTALS-Kyber, Dilithium). We also discuss novel attack vectors (e.g., hybrid quantum-classical cryptanalysis) and future research directions.
Quantum computers, that may become available one day, would impact many scientific fields, most notably cryptography since many asymmetric primitives are insecure against an adversary with quantum capabilities. Cryptographers are already anticipating this threat by proposing and studying a number of potentially quantum-safe alternatives for those primitives. On the other hand, symmetric primitives seem less vulnerable against quantum computing: the main known applicable result is Grover’s algorithm that gives a quadratic speed-up for exhaustive search. In this work, we examine more closely the security of symmetric ciphers against quantum attacks. Since our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques, we investigate quantum cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced: we don’t get a quadratic speed-up for all variants of the attacks. This allows us to demonstrate the following non-intuitive result: the best attack in the classical world does not necessarily lead to the best quantum one. We give some examples of application on ciphers LAC and KLEIN. We also discuss the important difference between an adversary that can only perform quantum computations, and an adversary that can also make quantum queries to a keyed primitive.
Quantum computers, that may become available one day, would impact many scientific fields, most notably cryptography since many asymmetric primitives are insecure against an adversary with quantum capabilities. Cryptographers are already anticipating this threat by proposing and studying a number of potentially quantum-safe alternatives for those primitives. On the other hand, symmetric primitives seem less vulnerable against quantum computing: the main known applicable result is Grover's algorithm that gives a quadratic speed-up for exhaustive search. In this work, we examine more closely the security of symmetric ciphers against quantum attacks. Since our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques, we investigate quantum cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced: we don't get a quadratic speed-up for all variants of the attacks. This allows us to demonstrate the following non-intuitive result: the best attack in the classical world does not necessarily lead to the best quantum one. We give some examples of application on ciphers LAC and KLEIN. We also discuss the important difference between an adversary that can only perform quantum computations, and an adversary that can also make quantum queries to a keyed primitive.
Motivated by Shor’s algorithm and its attractive features, the milestone results in quantum cryptanalysis were the discovery of quantum differential and linear cryptanalysis. In quantum cryptanalysis, quantum distinguishers imitate the classical setting. Details differ; however, as the distinguisher in the quantum setting can take maximum coset superposition of all possible subsets of plaintext pairs. Using quantum measurements, the winning gap of the game is exploited so that a distinguisher can still guess the secret key perfectly with a constant probability. Symmetric primitives also suffer reduced ideal security in the quantum world, but this security reduction is less drastic than for most asymmetric primitives. Stream ciphers, block ciphers, and cryptographic hash functions are primitives that are believed to resist quantum attacks. Analogs to Shor’s algorithm may say how hard it is to build a quantum computer, but devising quantum algorithms to outperform the best classical attacks for widely-used cryptographic primitives is probably outside the reach of current even if exponentially growing noisy intermediate-scale quantum (NISQ) computers.
Quantum computing poses a fundamental threat to modern cryptographic protocols by exploiting quantum algorithms that surpass classical computational limits. Shor’s algorithm can efficiently factor large integers, breaking RSA and other public-key cryptosystems, while Grover’s algorithm accelerates brute-force attacks against symmetric encryption. As quantum hardware advances, traditional cryptographic schemes risk obsolescence, necessitating the development of quantum-resistant cryptographic techniques. This paper explores the theoretical foundations of quantum cryptanalysis, examining key algorithms, their implications for cybersecurity, and the current state of post-quantum cryptographic solutions. By analyzing resource estimates for quantum attacks and potential mitigation strategies, this study provides a comprehensive overview of the evolving cryptographic landscape in the quantum era.