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

IEEE Internet of Things Journal

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

Zhenqiang Li, Shuqin Fan, Fei Gao, Yonglin Hao, Xi-Chao Hu, Lin‐Chun Wan, Hong-Wei Sun, Qi Su

Published Oct 30, 2025• 2 citations
Publisher

Abstract

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.

DOI
10.1109/jiot.2025.3627427

Related papers

Quantum related-key attacks on Feistel-like ciphers

Hong-Wei Sun, Long Zhang, Dandan Li +3 more

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.

EPJ Quantum Technology•Feb 17, 2026•1 citation

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

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 on Type‐1 Generalized Feistel Schemes

Hongwei Sun, Bin‐Bin Cai, Su‐Juan Qin +2 more

Abstract Generalized Feistel schemes (GFSs) are extremely important and extensively researched cryptographic schemes. In this paper, the security of Type‐1 GFS in quantum circumstances is investigated. On the one hand, in the qCCA setting, a new quantum polynomial‐time distinguisher on ‐round Type‐1 GFS with branches is given, which extends the previous results by rounds. This leads to a more efficient analysis of type‐1 GFS, that is, the complexity of some previous key‐recovery attacks is reduced by a factor of , where k is the key length of the internal round function. On the other hand, for CAST‐256, which is a certain block cipher based on Type‐1 GFS, a 17‐round quantum distinguisher in the qCPA setting is given. Based on this, an ‐round quantum key‐recovery attack with complexity is constructed.

Advanced Quantum Technologies•Jul 24, 2023•18 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

Quantum cryptanalysis of ciphers based on generalized Feistel and Lai-Massey schemes

Andrii Fesenko

This paper investigates generalizations of the Lai-Massey scheme, including unified constructionscombining it with the Feistel scheme (MD GLM, UFLM, L-Feistel, and quasi-Feistel). New reductionsto the quasi-Feistel scheme are provided. Known efficient quantum attacks are analyzed, includingchosen-plaintext attacks on 3 rounds and chosen-ciphertext attacks on 4 rounds for a special case of thequasi-Feistel cipher using Simon’s algorithm. It is demonstrated that restrictions in that work led to thedegeneration of the quasi-Feistel scheme into the standard Feistel scheme, replicating known quantumattacks on the Feistel scheme. New two-round distinguishing attacks are presented for the L-Feistel andMD-1 GLM schemes, enabling round key recovery.

Theoretical and Applied Cybersecurity•Dec 28, 2025•0 citations
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.
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.
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.
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.
Abstract Generalized Feistel schemes (GFSs) are extremely important and extensively researched cryptographic schemes. In this paper, the security of Type‐1 GFS in quantum circumstances is investigated. On the one hand, in the qCCA setting, a new quantum polynomial‐time distinguisher on ‐round Type‐1 GFS with branches is given, which extends the previous results by rounds. This leads to a more efficient analysis of type‐1 GFS, that is, the complexity of some previous key‐recovery attacks is reduced by a factor of , where k is the key length of the internal round function. On the other hand, for CAST‐256, which is a certain block cipher based on Type‐1 GFS, a 17‐round quantum distinguisher in the qCPA setting is given. Based on this, an ‐round quantum key‐recovery attack with complexity is constructed.
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 investigates generalizations of the Lai-Massey scheme, including unified constructionscombining it with the Feistel scheme (MD GLM, UFLM, L-Feistel, and quasi-Feistel). New reductionsto the quasi-Feistel scheme are provided. Known efficient quantum attacks are analyzed, includingchosen-plaintext attacks on 3 rounds and chosen-ciphertext attacks on 4 rounds for a special case of thequasi-Feistel cipher using Simon’s algorithm. It is demonstrated that restrictions in that work led to thedegeneration of the quasi-Feistel scheme into the standard Feistel scheme, replicating known quantumattacks on the Feistel scheme. New two-round distinguishing attacks are presented for the L-Feistel andMD-1 GLM schemes, enabling round key recovery.