With the continuous development of quantum technology, the quantum security of symmetric ciphers has attracted widespread attention. This study focuses on the security of 1K-AES, employing both quantum and classical slide attacks to analyze its security. On the one hand, for the 1K-AES with MixColumns in the last round, using the CNS algorithm achieves a success rate of 74%, an improvement from 63%, under a query complexity of O (22n/5) and classical memory complexity of O (2n/5) without the need for quantum random access memory, where n denotes the block size. When using a quantum random access memory, the universal quantum claw-finding algorithm improves the success rate to 100% with a query complexity of O (2n/3) and quantum random memory complexity of O (2n/3). Additionally, under the chosen plaintext attack, the success rate of the classical slide attack is also increased to 100%. On the other hand, for the 1K-AES with no MixColumns in the last round, the universal quantum claw-finding algorithm is used to perform a quantum slide attack, with both time and memory complexity of O (2n/3). Compared with the classical slide attack, this method achieves sub-exponential acceleration; compared with Grover’s search, the query complexity reduces from O (2n/2) to O (2n/3).
With the continuous development of quantum technology, the quantum security of symmetric ciphers has attracted widespread attention. This study focuses on the security of 1K-AES, employing both quantum and classical slide attacks to analyze its security. On the one hand, for the 1K-AES with MixColumns in the last round, using the CNS algorithm achieves a success rate of 74%, an improvement from 63%, under a query complexity of O (22n/5) and classical memory complexity of O (2n/5) without the need for quantum random access memory, where n denotes the block size. When using a quantum random access memory, the universal quantum claw-finding algorithm improves the success rate to 100% with a query complexity of O (2n/3) and quantum random memory complexity of O (2n/3). Additionally, under the chosen plaintext attack, the success rate of the classical slide attack is also increased to 100%. On the other hand, for the 1K-AES with no MixColumns in the last round, the universal quantum claw-finding algorithm is used to perform a quantum slide attack, with both time and memory complexity of O (2n/3). Compared with the classical slide attack, this method achieves sub-exponential acceleration; compared with Grover’s search, the query complexity reduces from O (2n/2) to O (2n/3).
Abstract By introducing the BHT algorithm into the slide attack on 1K-AES and the related-key attack on PRINCE, we present the corresponding quantum attacks in this paper. In the proposed quantum attacks, we generalize the BHT algorithm to the situation where the number of marked items is unknown ahead of time. Moreover, we give an implementation scheme of classifier oracle based on Quantum Phase Estimation algorithm in presented quantum attacks. The complexity analysis shows that the query complexity, time complexity and memory complexity of the presented quantum attacks are all O(2n/3) when the success probability is about 63%, where n is the block size. Compared with the corresponding classical attacks, the proposed quantum attacks can achieve subquadratic speed-up under the same success probability no matter on query complexity, time complexity or memory complexity. Furthermore, the query complexity of the proposed quantum slide attack on 1K-AES is less than Grover search on 1K-AES by a factor of 2n/6. When compared with the Grover search on PRINCE, the query complexity of the presented quantum attack on PRINCE is reduced from O(2n) to O(2n/2). When compared with the combination of Grover and Simon’s algorithms on PRINCE, the query complexity of our quantum attack on PRINCE is reduced from O(n⋅2n/2) to O(2n/2). Besides, the proposed quantum slide attack on 1K-AES indicates that the quantum slide attack could also be applied on Substitution-Permutation Network construction, apart from the iterated Even-Mansour cipher and Feistel constructions.
In this paper we analyze for the first time the post-quantum security of AES. AES is the most popular and widely used block cipher, established as the encryption standard by the NIST in 2001. We consider the secret key setting and, in particular, AES-256, the recommended primitive and one of the few existing ones that aims at providing a post-quantum security of 128 bits. In order to determine the new security margin, i.e., the lowest number of non-attacked rounds in time less than 2128 encryptions, we first provide generalized and quantized versions of the best known cryptanalysis on reduced-round AES, as well as a discussion on attacks that don’t seem to benefit from a significant quantum speed-up. We propose a new framework for structured search that encompasses both the classical and quantum attacks we present, and allows to efficiently compute their complexity. We believe this framework will be useful for future analysis.Our best attack is a quantum Demirci-Selçuk meet-in-the-middle attack. Unexpectedly, using the ideas underlying its design principle also enables us to obtain new, counter-intuitive classical TMD trade-offs. In particular, we can reduce the memory in some attacks against AES-256 and AES-128.One of the building blocks of our attacks is solving efficiently the AES S-Box differential equation, with respect to the quantum cost of a reversible S-Box. We believe that this generic quantum tool will be useful for future quantum differential attacks. Judging by the results obtained so far, AES seems a resistant primitive in the post-quantum world as well as in the classical one, with a bigger security margin with respect to quantum generic attacks.
This paper focuses on quantum key-recovery attacks on block ciphers. Previous works on quantum differential and truncated differential attacks like [Kaplan et al., ToSC 2016] have shown that classical algorithms for key-recovery, typically based on generating differential pairs and sieving them, can be accelerated by up to a quadratic speedup using variants of quantum search, quantum amplitude amplification, and quantum collision-finding.>br/> In this paper, we introduce a new quantum truncated differential key-recovery attack, which leverages the quantum convolution algorithm introduced in [Schrottenloher, CRYPTO 2022] and previously used in linear cryptanalysis. We adapt this algorithm to the case of differential cryptanalysis, by rewriting the probability of a differential of an n-bit cipher as a convolution of functions with 2n-bit input. We then construct a quantum state whose amplitudes encode the probability of the differential for different key guesses, and use this as the starting point of a quantum search. In some cases (although not on practical ciphers so far), the speedup is better than quadratic compared to classical attacks. We also extend the framework to related-key differential attacks.We give applications to a 9-round attack on QARMAv2-64 adapted from [Ahmadian et al., DCC 2024] and a 12-round related-key attack on AES-256 from [Boura et al., CRYPTO 2023], which show improvement over classical attacks and over Kaplan et al.’s strategy when taking into account the amount of memory and the type of quantum memory used (as our attack requires only quantum-accessible classical memory).
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.
Key recovery attack on SPN ciphers such as AES is NP hard in complexity. Previous studies have estimated the quantum resources required for implementing Grover’s key search for AES, but these are largely theoretical in nature. The key challenges to implement Grover’s algorithm on current quantum hardware include the number of available qubits, noise, and decoherence. However, the rapid advancement of hardware has brought us closer to practical realization for the cryptanalysis of light-weight SPN ciphers. This study presents an efficient quantum circuit implementation of Mini-AES, a 16-bit variant of AES, employing standard CNOT and Toffoli gates. To the best of our knowledge, our work provides the first complete quantum implementations of all core Mini-AES components for the quantum oracle. The effects of noise are emulated for each module of the quantum oracle and quantified. Furthermore, Grover’s algorithm is applied to Mini-AES to perform successful key recovery through a known-plaintext attack, demonstrating significant amplitude amplification while using near-optimal Grover’s iterations, thereby reducing the total quantum volume. The optimal Grover’s iterations have been obtained empirically as well as validated with finite-shot analysis. Notably, the application of Grover’s algorithm reveals key clustering behavior in Mini-AES, which has been corroborated through classical simulation.
Abstract Quantum attacks employing superposition queries (Q2 model) have been demonstrated to compromise numerous classically secure block-cipher constructions. These attacks embed the target encryption structure into a period-finding problem, which dedicated quantum algorithms, including the Simon and BV algorithms, can solve. After restoring the secret state, attackers can launch an attack by recovering the key (the secret state contains key information) or distinguishing it from random permutations. In this paper, we investigate the quantum security of Feistel-like ciphers in a related-key setting. For several constructions, we demonstrate how to define a periodic function that can be evaluated using the Simon algorithm with only O(n) O ( n ) quantum queries to the encryption oracle, where n represents the block size. This enables secret-state recovery attacks on Type-1/2 generalized Feistel schemes, as well as key-recovery attacks on the Feistel-FK and Misty L-KF constructions. All these attacks achieve an exponential reduction in query complexity compared to the best known classical or quantum methods.