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

arXiv:1603.07856 · Quantum Information and Computation

Using Simon's algorithm to attack symmetric-key cryptographic primitives

Thomas Santoli, Christian Schaffner

Published Jan 1, 2017• 18 citations
arXivHTMLPDF

Abstract

We present new connections between quantum information and the field of classical cryptography. In particular, we provide examples where Simon’s algorithm can be used to show insecurity of commonly used cryptographic symmetric-key primitives. Specifically, these examples consist of a quantum distinguisher for the 3-round Feistel network and a forgery attack on CBC-MAC which forges a tag for a chosen-prefix message querying only other messages (of the same length). We assume that an adversary has quantum-oracle access to the respective classical primitives. Similar results have been achieved recently in independent work by Kaplan et al. [KLLNP16]. Our findings shed new light on the post-quantum security of cryptographic schemes and underline that classical security proofs of cryptographic constructions need to be revisited in light of quantum attackers.

DOI
10.26421/qic17.1-2-4

Related papers

Using Simon's algorithm to attack symmetric-key cryptographic primitives

SantoliThomas, SchaffnerChristian

We present new connections between quantum information and the field of classical cryptography. In particular, we provide examples where Simon's algorithm can be used to show insecurity of commonly...

Quantum Information and Computation•Feb 1, 2017•0 citations

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

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 distinguisher between the 3-round Feistel cipher and the random permutation

Hidenori Kuwakado, Masakatu Morii

No polynomial classical algorithms can distinguish between the 3-round Feistel cipher with internal permutations and a random permutation. It means that the 3-round Feistel cipher with internal permutations is secure against any chosen plaintext attack on the classical computer. This paper shows that there exists a polynomial quantum algorithm for distinguishing them. Hence, the 3-round Feistel cipher with internal permutations may be insecure against a chosen plaintext attack on a quantum computer. This distinguishing problem is an instance that can be efficiently solved by exploiting the quantum parallelism. The proposed algorithm is the first application of Simon's algorithm to cryptographic analysis.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•220 citations

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 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
We present new connections between quantum information and the field of classical cryptography. In particular, we provide examples where Simon’s algorithm can be used to show insecurity of commonly used cryptographic symmetric-key primitives. Specifically, these examples consist of a quantum distinguisher for the 3-round Feistel network and a forgery attack on CBC-MAC which forges a tag for a chosen-prefix message querying only other messages (of the same length). We assume that an adversary has quantum-oracle access to the respective classical primitives. Similar results have been achieved recently in independent work by Kaplan et al. [KLLNP16]. Our findings shed new light on the post-quantum security of cryptographic schemes and underline that classical security proofs of cryptographic constructions need to be revisited in light of quantum attackers.
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.
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.
No polynomial classical algorithms can distinguish between the 3-round Feistel cipher with internal permutations and a random permutation. It means that the 3-round Feistel cipher with internal permutations is secure against any chosen plaintext attack on the classical computer. This paper shows that there exists a polynomial quantum algorithm for distinguishing them. Hence, the 3-round Feistel cipher with internal permutations may be insecure against a chosen plaintext attack on a quantum computer. This distinguishing problem is an instance that can be efficiently solved by exploiting the quantum parallelism. The proposed algorithm is the first application of Simon's algorithm to cryptographic analysis.
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.
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.