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

International Journal of Quantum Information

The construction of quantum distinguishers for GFS based on Simon’s algorithm

Chengdong Ma, Jie Guan, Tairong Shi, Ziyu Guan

Published Sep 12, 2025• 0 citations
Publisher

Abstract

With the application of quantum algorithms in cryptanalysis keeping increasing. Currently, there are many works based on Simon’s algorithm for generalized Feistel scheme (GFS), mostly using manual derivation to construct periodic functions. We present the functional form of the output component’s algebraic expression. Then we propose the transformation rules of functional form of algebraic expression through round function. Afterwards, we present an algorithm to find GFS’s longest round distinguishers based on Simon’s algorithm. Based on this, we get quantum distinguishers of Type-1 GFS, Type-2 GFS and Type-3 GFS under quantum chosen plaintext attack (qCPA) setting and quantum chosen ciphertext attack (qCCA) setting. For Type-1 GFS, the longest round quantum distinguisher based on Simon’s algorithm is unique under qCPA/qCCA setting, which is [Formula: see text]-round/[Formula: see text]-round. For [Formula: see text]-branch Type-2 GFS, [Formula: see text] kinds of [Formula: see text]-round distinguishers have been found under qCPA/qCCA setting. For Type-3 GFS, the longest round distinguisher based on Simon’s algorithm is unique under qCPA/qCCA setting, which is [Formula: see text]-round/3-round.

DOI
10.1142/s0219749925500297

Related papers

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

Quantum Distinguishing Attacks on Generalized Feistel Schemes

Andrii Fesenko, Anastasiia Zvychaina

It turned out that in addition to problems with classical asymmetric cryptography in the post-quantum period, there are certain doubts about the strength of symmetric cryptographic schemes.This paper demonstrates that on Type III Generalized Feistel Scheme (GFS), by selectively fixing specific parts of the plaintext at the input to the GFS, it is possible to reduce the problem of distinguishing between random text and encrypted output of the same GFS to the Simon problem through different approaches.Our method enables the cracking of the cipher up to 𝑑 rounds in polynomial time, while a more sophisticated approach based on different formulas from other paths of the cipher can crack 𝑑 + 1 rounds with the same time complexity in quantum adversary model.These distinct approaches yield varying results in terms of scheme security, indicating the potential to break more rounds in the GFS using the same methodology.

Theoretical and Applied Cybersecurity•Sep 19, 2023•0 citations

Quantum Attacks on Type-3 Generalized Feistel Scheme and Unbalanced Feistel Scheme with Expanding Functions

Zhongya Zhang, Wenling Wu, Han Sui +1 more

Quantum algorithms are raising concerns in the field of cryptography all over the world. A growing number of symmetric cryptography algorithms have been attacked in the quantum setting. Type-3 generalized Feistel scheme (GFS) and unbalanced Feistel scheme with expanding functions (UFS-E) are common symmetric cryptography schemes, which are often used in cryptographic analysis and design. We propose quantum distinguishing attacks on Type-3 GFS and UFS-E in the quantum chosen plaintext attack setting. The results of key recovery are better than those based on exhaustive search in the quantum setting.

Chinese Journal of Electronics•Mar 1, 2023•19 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

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 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
With the application of quantum algorithms in cryptanalysis keeping increasing. Currently, there are many works based on Simon’s algorithm for generalized Feistel scheme (GFS), mostly using manual derivation to construct periodic functions. We present the functional form of the output component’s algebraic expression. Then we propose the transformation rules of functional form of algebraic expression through round function. Afterwards, we present an algorithm to find GFS’s longest round distinguishers based on Simon’s algorithm. Based on this, we get quantum distinguishers of Type-1 GFS, Type-2 GFS and Type-3 GFS under quantum chosen plaintext attack (qCPA) setting and quantum chosen ciphertext attack (qCCA) setting. For Type-1 GFS, the longest round quantum distinguisher based on Simon’s algorithm is unique under qCPA/qCCA setting, which is [Formula: see text]-round/[Formula: see text]-round. For [Formula: see text]-branch Type-2 GFS, [Formula: see text] kinds of [Formula: see text]-round distinguishers have been found under qCPA/qCCA setting. For Type-3 GFS, the longest round distinguisher based on Simon’s algorithm is unique under qCPA/qCCA setting, which is [Formula: see text]-round/3-round.
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.
It turned out that in addition to problems with classical asymmetric cryptography in the post-quantum period, there are certain doubts about the strength of symmetric cryptographic schemes.This paper demonstrates that on Type III Generalized Feistel Scheme (GFS), by selectively fixing specific parts of the plaintext at the input to the GFS, it is possible to reduce the problem of distinguishing between random text and encrypted output of the same GFS to the Simon problem through different approaches.Our method enables the cracking of the cipher up to 𝑑 rounds in polynomial time, while a more sophisticated approach based on different formulas from other paths of the cipher can crack 𝑑 + 1 rounds with the same time complexity in quantum adversary model.These distinct approaches yield varying results in terms of scheme security, indicating the potential to break more rounds in the GFS using the same methodology.
Quantum algorithms are raising concerns in the field of cryptography all over the world. A growing number of symmetric cryptography algorithms have been attacked in the quantum setting. Type-3 generalized Feistel scheme (GFS) and unbalanced Feistel scheme with expanding functions (UFS-E) are common symmetric cryptography schemes, which are often used in cryptographic analysis and design. We propose quantum distinguishing attacks on Type-3 GFS and UFS-E in the quantum chosen plaintext attack setting. The results of key recovery are better than those based on exhaustive search in the quantum setting.
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.
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.