Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

EPJ Quantum Technology

Quantum related-key attacks on Feistel-like ciphers

Hong-Wei Sun, Long Zhang, Dandan Li, Zhenqiang Li, Rong-Xue Xu, Ke-Jia Zhang

Published Feb 17, 2026• 1 citation
Publisher

Abstract

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.

DOI
10.1140/epjqt/s40507-026-00481-3

Related papers

Quantum cryptanalysis on Feistel variants in related-key settings

Xiaoyu Wang, Siwei Chen, Zejun Xiang +2 more

Abstract Simon’s algorithm is a well-known quantum algorithm that can achieve exponential acceleration. This paper studies the applications of Simon’s algorithm in analyzing the security of Feistel variants, several well-known cryptographic structures derived from the Feistel structure. Specifically, we study quantum related-key attacks on Feistel variants in the setting that adversaries can only control part of the key difference in quantum superposition. We delve into observing the quantum related-key attacks on the balanced Feistel structure given by Cid \textit{et al.} and slightly improve the existing method to design periodic functions, ultimately providing a new approach to building periodic functions in single-key settings. Based on these results, we propose a general technique to construct quantum related-key distinguishers exploiting the quantum single-key distinguishers construction technique. As applications of our proposed technique, we demonstrate how to construct new polynomial-time quantum related-key chosen-plaintext distinguishers on several Feistel variants: Feistel-KF, SM4-like, MARS-like, Type-1/2/3 generalized Feistel-KF structures.

Quantum Information Processing•Nov 5, 2025•1 citation

Quantum Attacks without Superposition Queries: the Offline Bernstein-Vazirani Meets Grover Algorithm

Bao-Min Zhou, Zheng Yuan

Block cryptanalysis has a major breakthrough in the model of superposition queries. For instance, Simon’s algorithm can efficiently break various constructions. In practice, Bernstein-Vaziran’s algorithm can also realize the periodic search of the vector function. Moreover, in some cases, it can have more advantages than the Simon’s algorithm.In the context of this study, we present an algorithm that combines Grover’s and Bernstein-Vazirani’s quantum algorithms. This algorithm empowers us to carry out key recovery attacks on Feistel structures. on Feistel structures, FX construction and Even Mansour construction. We exploit cryptosystems’ algebraic structure to launch successful key recovery attacks, considering that quantum attackers can only make classical queries. Through comparison, it can be concluded that this algorithm has stronger practicability in attacking block ciphers.

International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT)•Aug 4, 2023•1 citation

On Quantum Related-Key Attacks on Iterated Even-Mansour Ciphers

Akinori Hosoyamada, Kazumaro Aoki

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Dec 31, 2018•20 citations

Efficient Quantum Generic Key-Recovery Attack on Feistel Ciphers

Kun Zhang, Tao Shang, Yuanjing Zhang

The development of post-quantum cryptography requires cryptographic primitives that remain secure against quantum adversaries. Quantum key-recovery attacks constitute a fundamental class of quantum cryptanalytic techniques, and the resistance of a cryptosystem to such attacks serves as an important indicator of its overall security. Since the Feistel structure is a core component in the design of many block ciphers, efficient quantum key-recovery attacks on Feistel ciphers provide valuable insights into evaluating and strengthening their security. In this paper, we propose an efficient generic quantum key-recovery attack on Feistel ciphers. Our attack integrates universal hash families with Simon's and Grover's algorithms to perform key-recovery. We rigorously analyze the correctness of the proposed attack and derive its time and quantum resource complexities. A comprehensive comparison with existing keyrecovery attacks shows that the proposed approach improves both quantum resource usage and dominant query complexity, and therefore yields a more efficient quantum key-recovery attack. Our work enhances the understanding of Feistel ciphers under quantum threats and informs the design of robust cryptosystems for the post-quantum era.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Apr 6, 2026•0 citations

Conditional Constant Function Problem and Its Quantum Solutions: Attacking Feistel Ciphers

Zhenqiang Li, Shuqin Fan, Fei Gao +5 more

This paper defines the conditional constant function problem (CCFP), and for a special case of CCFP, presents a quantum algorithm for solving it efficiently. Such an algorithm enables us to make new evaluations of the quantum security of Feistel block cipher in the case where quantum attackers can only perform online classical queries. Specifically, the chosen-plaintext key recovery attacks on two Feistel block cipher variants, known as Feistel-KF and Feistel-FK, are significantly improved. For Feistel-KF, a 3-round distinguisher based on the special case of CCFP is constructed, and key recovery attacks forr> 3 rounds are proposed. For Feistel-FK, the CCFP based distinguisher covers 4 rounds and the key recovery attacks are applicable forr> 4 rounds. Based on the CCFP solving algorithm, the key recovery attacks can reduce the classical memory complexity from the previous exponentialO(2cn) toO(1), wherec’s are constants. The query complexity of key recovery attacks on Feistel-KF is also significantly reduced fromO(2cn) toO(1). Besides, the CCFP solving algorithm can be extended to reduce the query complexity exponentially in attacking the 2IEM and pEDM constructions. These results indicate that quantum algorithms solving CCFP could be more promising than those solving the period finding problem.

IEEE Internet of Things Journal•Oct 30, 2025•2 citations

Quantum Cryptanalysis on Two Feistel-Type Constructions

Yan-Ying Zhu, Bin-Bin Cai, Fei Gao +1 more

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 $2^{n/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 $2^{16}$ 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(2^{38})\) to \(O(2^{26})\) by a factor of \(2^{12}\).

quant-pharXiv:2610.27506•Oct 21, 2026•0 citations
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)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.
Abstract Simon’s algorithm is a well-known quantum algorithm that can achieve exponential acceleration. This paper studies the applications of Simon’s algorithm in analyzing the security of Feistel variants, several well-known cryptographic structures derived from the Feistel structure. Specifically, we study quantum related-key attacks on Feistel variants in the setting that adversaries can only control part of the key difference in quantum superposition. We delve into observing the quantum related-key attacks on the balanced Feistel structure given by Cid \textit{et al.} and slightly improve the existing method to design periodic functions, ultimately providing a new approach to building periodic functions in single-key settings. Based on these results, we propose a general technique to construct quantum related-key distinguishers exploiting the quantum single-key distinguishers construction technique. As applications of our proposed technique, we demonstrate how to construct new polynomial-time quantum related-key chosen-plaintext distinguishers on several Feistel variants: Feistel-KF, SM4-like, MARS-like, Type-1/2/3 generalized Feistel-KF structures.
Block cryptanalysis has a major breakthrough in the model of superposition queries. For instance, Simon’s algorithm can efficiently break various constructions. In practice, Bernstein-Vaziran’s algorithm can also realize the periodic search of the vector function. Moreover, in some cases, it can have more advantages than the Simon’s algorithm.In the context of this study, we present an algorithm that combines Grover’s and Bernstein-Vazirani’s quantum algorithms. This algorithm empowers us to carry out key recovery attacks on Feistel structures. on Feistel structures, FX construction and Even Mansour construction. We exploit cryptosystems’ algebraic structure to launch successful key recovery attacks, considering that quantum attackers can only make classical queries. Through comparison, it can be concluded that this algorithm has stronger practicability in attacking block ciphers.
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.
The development of post-quantum cryptography requires cryptographic primitives that remain secure against quantum adversaries. Quantum key-recovery attacks constitute a fundamental class of quantum cryptanalytic techniques, and the resistance of a cryptosystem to such attacks serves as an important indicator of its overall security. Since the Feistel structure is a core component in the design of many block ciphers, efficient quantum key-recovery attacks on Feistel ciphers provide valuable insights into evaluating and strengthening their security. In this paper, we propose an efficient generic quantum key-recovery attack on Feistel ciphers. Our attack integrates universal hash families with Simon's and Grover's algorithms to perform key-recovery. We rigorously analyze the correctness of the proposed attack and derive its time and quantum resource complexities. A comprehensive comparison with existing keyrecovery attacks shows that the proposed approach improves both quantum resource usage and dominant query complexity, and therefore yields a more efficient quantum key-recovery attack. Our work enhances the understanding of Feistel ciphers under quantum threats and informs the design of robust cryptosystems for the post-quantum era.
This paper defines the conditional constant function problem (CCFP), and for a special case of CCFP, presents a quantum algorithm for solving it efficiently. Such an algorithm enables us to make new evaluations of the quantum security of Feistel block cipher in the case where quantum attackers can only perform online classical queries. Specifically, the chosen-plaintext key recovery attacks on two Feistel block cipher variants, known as Feistel-KF and Feistel-FK, are significantly improved. For Feistel-KF, a 3-round distinguisher based on the special case of CCFP is constructed, and key recovery attacks forr> 3 rounds are proposed. For Feistel-FK, the CCFP based distinguisher covers 4 rounds and the key recovery attacks are applicable forr> 4 rounds. Based on the CCFP solving algorithm, the key recovery attacks can reduce the classical memory complexity from the previous exponentialO(2cn) toO(1), wherec’s are constants. The query complexity of key recovery attacks on Feistel-KF is also significantly reduced fromO(2cn) toO(1). Besides, the CCFP solving algorithm can be extended to reduce the query complexity exponentially in attacking the 2IEM and pEDM constructions. These results indicate that quantum algorithms solving CCFP could be more promising than those solving the period finding problem.
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)r(r>12)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/22^{n/2}2n/2, where nnn denotes the subkey length. Second, we design a 9-round quantum distinguisher for LBlock and extend it to an r(r>15)r(r>15)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 2162^{16}216 reduction in the time complexity of our rrr-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)O(2^{38})O(238) to O(226)O(2^{26})O(226) by a factor of 2122^{12}212.