Abstract Symmetric cryptography is expected to be quantum safe when long‐term security is needed. Kuwakado and Morii gave a 3‐round quantum distinguisher of the Feistel cipher based on Simon's algorithm. However, the quantum distinguisher without considering the specific structure of the round function is not accurate enough. A new quantum cryptanalysis method for Feistel structure is studied here. It can make full use of the specific structure of the round function. The properties of Camellia round function and its linear transformation P are taken into account, and a 5‐round quantum distinguisher is proposed. Then, the authors follow a key‐recovery attack framework by Leander and May, that is, Grover‐meet‐Simon algorithm, and give a quantum key‐recovery attack on 7‐round Camellia in Q2 model with the time complexity of 2 24 . It is the very first time that the specific structure of the round function is used to improve quantum attack on Camellia.
Abstract Symmetric cryptography is expected to be quantum safe when long‐term security is needed. Kuwakado and Morii gave a 3‐round quantum distinguisher of the Feistel cipher based on Simon's algorithm. However, the quantum distinguisher without considering the specific structure of the round function is not accurate enough. A new quantum cryptanalysis method for Feistel structure is studied here. It can make full use of the specific structure of the round function. The properties of Camellia round function and its linear transformation P are taken into account, and a 5‐round quantum distinguisher is proposed. Then, the authors follow a key‐recovery attack framework by Leander and May, that is, Grover‐meet‐Simon algorithm, and give a quantum key‐recovery attack on 7‐round Camellia in Q2 model with the time complexity of 2 24 . It is the very first time that the specific structure of the round function is used to improve quantum attack on Camellia.
The Feistel structure represents a fundamental architectural component within the domain of symmetric cryptographic algorithms, with a substantial body of research conducted within the context of classical computing environments. Nevertheless, research into specific symmetric cryptographic algorithms utilizing the Feistel structure is relatively scarce in quantum computing environments. This paper, for the first time, proposes a five-round distinguisher for Camellia under the quantum chosen-ciphertext attack (qCCA) setting, with its effectiveness empirically validated. Additionally, by combining Grover’s algorithm and Simon’s algorithm, we construct a nine-round key-recovery attack model against Camellia. Through an in-depth analysis of Camellia’s key expansion algorithm, we significantly reduce the complexity of the key-recovery attack. The proposed attack achieves a time complexity of 261.5 for recovering the correct key bits and requires 531 quantum bits.
With the rapid advancement of quantum computing, the security of traditional cryptographic systems is facing significant challenges. As a fundamental component of symmetric cryptography, block ciphers have attracted increasing attention regarding their quantum security in recent years.
In this paper, we propose new quantum attacks on two Feistel-type constructions, i.e., New Structure IV and the lightweight block cipher LBlock, under the quantum chosen-plaintext attack (qCPA) model. First, we construct an 8-round quantum distinguisher for New Structure IV and perform an r(r>12)-round quantum key-recovery attack. Compared with Li et al.'s qCPA-based result presented at INSCRYPT 2024, our attack reduces the time complexity by a factor of 2n/2, where n denotes the subkey length. Second, we design a 9-round quantum distinguisher for LBlock and extend it to an r(r>15)-round quantum key-recovery attack. The proposed quantum distinguisher covers one more round than Liu et al.'s automated-search distinguisher at ASIACRYPT 2025, which results in a 216 reduction in the time complexity of our r-round quantum key-recovery attack on LBlock. Furthermore, by analyzing the structure of the round function and the key scheduling of LBlock, we reduce the subkey guess space for the 15-round attack from 76 bits to 52 bits, lowering the time complexity from O(238) to O(226) by a factor of 212.
By studying the attack technology based on Simon, Grover and other quantum algorithms for the security of block cipher structure, this paper proposes new quantum attack on 6 generalized unbalanced Feistel structures. We improve the attack results of n-cell structure, New Structure I/III/IV structure and FBC-like structure, and give a quantum attack on Skipjack structure for the first time. Based on Simon algorithm, this paper constructs a n2-round, a 12/12/6-round and a 4-round quantum distinguisher about n-cell structure, New structure I/III/IV and FBC-like structure, improving n2-n-1 rounds, 6 rounds/3 rounds/1 round and 1 round separately, comparing to the previous results. In addition, this paper also constructs a 9-round quantum distinguisher about Skipjack structure. Moreover, this paper proposes a quantum key recovery attack on the above six structures in combination with Grover algorithm, and the time complexities of attacks are analyzed.
ABSTRACT Since the proposal of the Grover algorithm in 1996, which first combined quantum algorithms with symmetric cryptanalysis, significant progress has been made in the quantization of classical cryptanalysis methods. Differential‐linear cryptanalysis is a hybrid technique combining differential and linear cryptanalysis; however, there has been no prior work on its quantization. This paper presents a quantum differential‐linear key recovery attack framework. We apply this framework to Simon32/64 and Simeck32/64. Considering that the experimental correlation distribution of the differential‐linear distinguisher significantly affects the complexity of quantum attacks, we measure the experimental correlation distributions of Simon32/64 and Simeck32/64. We conduct a quantum differential‐linear key recovery attack on 19‐round Simon32/64. Under the Q1 model, the time complexity of the attack is , the data complexity is , the memory complexity is and the success rate is 60.96%, which achieves the lowest time, memory, and data complexities among all existing 19‐round quantum attacks. In the Q2 model, the time complexity reduces to , with negligible memory complexity. For Simeck32/64, we present a 20‐round quantum key recovery attack under the Q2 model, which is the first quantum key recovery attack on this block cipher.
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.
It has been said that security of symmetric key schemes is not so much affected by quantum computers, compared to public key schemes. However, recent works revealed that, in some specific situations, symmetric key schemes are also broken in polynomial time by adversaries with quantum computers. These works contain a quantum distinguishing attack on 3-round Feistel ciphers and a quantum key recovery attack on the Even-Mansour cipher by Kuwakado and Morii, in addition to the quantum forgery attack on CBC-MAC which is proposed independently by Kaplan et al., and by Santoli and Schaffner. Iterated Even-Mansour cipher is a simple but important block cipher, which can be regarded as an idealization of AES. Whether there exists an efficient quantum algorithm that can break iterated Even-Mansour cipher with independent subkeys is an important problem from the viewpoint of analyzing post-quantum security of block ciphers. Actually there is an efficient quantum attack on iterated Even-Mansour cipher by Kaplan et al., but their attack can only be applied in the case that all subkeys are the same. This paper shows that there is a polynomial time quantum algorithm that recovers partial keys of the iterated Even-Mansour cipher with independent subkeys, in a related-key setting. The related-key condition is somewhat strong, but our algorithm can recover subkeys with two related oracles. In addition, we also show that our algorithm can recover all keys of the i-round iterated Even-Mansour cipher, if we are allowed to access i related quantum oracles. To realize quantum related-key attacks, we extend Simon's quantum algorithm so that we can recover the hidden period of a function that is periodic only up to constant. Our technique is to take differential of the target function to make a double periodic function, and then apply Simon's algorithm.