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.
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.
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.
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.
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.
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.
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.
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.