With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.
Abstract To guarantee the security of symmetric key schemes against quantum adversary, developing quantum cryptanalytic techniques becomes a major worldwide challenge in the post-quantum world. In this paper, we present a general framework of classical guess and determine attack on stream ciphers, and then convert it into quantum guess and determine attack. It shows that, for a given stream cipher with a key size of
k bits and an internal state size of
n bits, if a basic guess and determine attack with a time complexity below
O(23k/2/n) is available, there is a quantum guess and determine attack with multiple data that can recover all
n internal state bits of the cipher with complexity below
O(2k/2). As applications, we present quantum guess and determine attacks on the SNOW-like stream ciphers. The results show that all of SNOW 1.0 with 128-bit key, SNOW 2.0 with 128-bit key and SOSEMANUK are insecure against quantum guess and determine attack. The resource requirements for implementing a quantum guess and determine attack on SNOW 3G are evaluated as a case study. To the best of our knowledge, this is the first time that the general quantum guess and determine attack is formally proposed and applied to the SNOW-like stream ciphers.
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.