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

Symmetry

Quantum Related-Key Attack Based on Simon’s Algorithm and Its Applications

Ping Zhang

Published Apr 24, 2023• 6 citations
Publisher

Abstract

With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.

DOI
10.3390/sym15050972

Related papers

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

Simon's Algorithm for the Even-Mansour Cipher on Quantum Hardware

Anina Köhler, Jakob Murauer, Tim Heine +2 more

Simon's algorithm is a polynomial period-finding algorithm that has been used to exploit the algebraic structure of specific symmetric ciphers, showing that exponential speedups in their cryptanalysis are theoretically possible. While the theoretical framework for an attack using Simon's algorithm on the Even-Mansour cipher is well-established, practical implementations on noisy intermediate-scale quantum (NISQ) hardware remain limited. This paper presents a proof of concept quantum cryptanalysis of the Even-Mansour cipher using Simon's period-finding algorithm on NISQ hardware. For N = 3 and N = 4, we successfully demonstrate secret key recovery for N-bit constructions on the ibm_miami processor. Our experiments also identify a scaling limitation in the classical pre-processing stage: The DORCIS circuit optimization tool encountered a memory bottleneck at N = 5, preventing the generation of optimized circuits for larger key lengths. Our results suggest firstly that Simon's algorithm is effective for the Even-Mansour cipher for short bit lengths on current quantum hardware. Secondly, while DORCIS is effective for the small-scale S-boxes for which it was designed, there remains a need for the investigation of more scalable and efficient synthesis tools capable of handling larger and more general permutations in the context of Even-Mansour ciphers.

quant-pharXiv:2604.25509•Apr 29, 2026•0 citations

A quantum related-key attack based on Bernstein-Vazirani algorithm

Huiqin Xie, Li Yang

Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results in recent years. In this paper, we study related-key attack in the quantum setting, and proposed a specific related-key attack which can recover the key of block ciphers efficiently, as long as the attacked block ciphers satisfy certain conditions. The attack algorithm employs Bernstein-Vazirani algorithm as a subroutine and requires the attacker to query the encryption oracle with quantum superpositions. Afterwards, we rigorously demonstrate the validity of the attack and analyze its complexity. Our work shows that related-key attack is quite powerful when combined with quantum algorithms, and provides some guidance for the design of block ciphers that are secure against quantum adversaries.

arXiv:1808.03266•Aug 9, 2018•2 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 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

Quantum Cryptanalysis on IBM Quantum Hardware: Extending Even--Mansour Period Recovery from $N=4$ to $N=10$

Taebong Kim, Youngsik Hong, Minsik Kim +4 more

We report genuine-un-compiled, textbook-faithful-quantum cryptanalysis of symmetric-cipher structures executed on real IBM quantum hardware (ibm\_kingston, Heron generation). Using Simon's algorithm we recover the hidden period of the Even-Mansour cipher up to security parameter N = 10 on real hardware, beyond the largest previously reported real-hardware key recovery of N = 4, and we cleanly recover the periods of a 3-round Feistel (DES-family) construction at block sizes 6 and 8; a 21-qubit block-10 instance is verified in simulation and submitted to hardware. We further provide a breadth-first benchmark of five genuine quantum attacks spanning four symmetric-cipher design paradigms -- Bernstein-Vazirani (linear structure, single query), Grover (SPN key search, quadratic), and Simon (Even-Mansour, CBC-MAC forgery, and Feistel; exponential-to-polynomial in query complexity) -- validated to the classical-simulation ceiling of 25 qubits. We are deliberately explicit about scope: these attacks target reduced or structured constructions in the Q2 (quantum-query) model, asymptotically follow the birthday bound and therefore do not constitute quantum advantage over classical collision-finding, do not break full AES/RSA or 16-round DES, and rely on error mitigation rather than fault-tolerant error correction. Our contribution is the real-hardware demonstration at record structure sizes, the breadth of genuine algorithmic coverage across four paradigms, and an honest, reproducible benchmark with public artifacts.

arXiv:2607.18340•Jul 20, 2026•0 citations
With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.
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.
Simon's algorithm is a polynomial period-finding algorithm that has been used to exploit the algebraic structure of specific symmetric ciphers, showing that exponential speedups in their cryptanalysis are theoretically possible. While the theoretical framework for an attack using Simon's algorithm on the Even-Mansour cipher is well-established, practical implementations on noisy intermediate-scale quantum (NISQ) hardware remain limited. This paper presents a proof of concept quantum cryptanalysis of the Even-Mansour cipher using Simon's period-finding algorithm on NISQ hardware. For N = 3 and N = 4, we successfully demonstrate secret key recovery for N-bit constructions on the ibm_miami processor. Our experiments also identify a scaling limitation in the classical pre-processing stage: The DORCIS circuit optimization tool encountered a memory bottleneck at N = 5, preventing the generation of optimized circuits for larger key lengths. Our results suggest firstly that Simon's algorithm is effective for the Even-Mansour cipher for short bit lengths on current quantum hardware. Secondly, while DORCIS is effective for the small-scale S-boxes for which it was designed, there remains a need for the investigation of more scalable and efficient synthesis tools capable of handling larger and more general permutations in the context of Even-Mansour ciphers.
Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results in recent years. In this paper, we study related-key attack in the quantum setting, and proposed a specific related-key attack which can recover the key of block ciphers efficiently, as long as the attacked block ciphers satisfy certain conditions. The attack algorithm employs Bernstein-Vazirani algorithm as a subroutine and requires the attacker to query the encryption oracle with quantum superpositions. Afterwards, we rigorously demonstrate the validity of the attack and analyze its complexity. Our work shows that related-key attack is quite powerful when combined with quantum algorithms, and provides some guidance for the design of block ciphers that are secure against quantum adversaries.
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.
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.
Quantum Cryptanalysis on IBM Quantum Hardware: Extending Even--Mansour Period Recovery from N=4N=4N=4 to N=10N=10N=10
We report genuine-un-compiled, textbook-faithful-quantum cryptanalysis of symmetric-cipher structures executed on real IBM quantum hardware (ibm\_kingston, Heron generation). Using Simon's algorithm we recover the hidden period of the Even-Mansour cipher up to security parameter N = 10 on real hardware, beyond the largest previously reported real-hardware key recovery of N = 4, and we cleanly recover the periods of a 3-round Feistel (DES-family) construction at block sizes 6 and 8; a 21-qubit block-10 instance is verified in simulation and submitted to hardware. We further provide a breadth-first benchmark of five genuine quantum attacks spanning four symmetric-cipher design paradigms -- Bernstein-Vazirani (linear structure, single query), Grover (SPN key search, quadratic), and Simon (Even-Mansour, CBC-MAC forgery, and Feistel; exponential-to-polynomial in query complexity) -- validated to the classical-simulation ceiling of 25 qubits. We are deliberately explicit about scope: these attacks target reduced or structured constructions in the Q2 (quantum-query) model, asymptotically follow the birthday bound and therefore do not constitute quantum advantage over classical collision-finding, do not break full AES/RSA or 16-round DES, and rely on error mitigation rather than fault-tolerant error correction. Our contribution is the real-hardware demonstration at record structure sizes, the breadth of genuine algorithmic coverage across four paradigms, and an honest, reproducible benchmark with public artifacts.