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

EPJ Quantum Technology

Quantum attacks on Sum of Even-Mansour construction utilizing online classical queries

Zhenqiang Li, Shuqin Fan, Fei Gao, Yonglin Hao, Hongwei Sun, Xiaoxin Hu, Dandan Li

Published Jun 5, 2025• 2 citations
Publisher

Abstract

The Sum of Even-Mansour (SoEM) construction, proposed by Chen et al. at Crypto 2019, has become the basis for designing some symmetric schemes, such as the nonce-based MAC scheme $\text{nEHtM}_{p}$ and the nonce-based encryption scheme CENCPP∗. In this paper, we make the first attempt to study the quantum security of SoEM under the Q1 model where the targeted encryption oracle can only respond to classical queries rather than quantum ones. Firstly, we propose a quantum key recovery attack on SoEM21 with a time complexity of $\tilde{O}(2^{n/3})$ along with $O(2^{n/3})$ online classical queries. Compared with the current best classical result which requires $O(2^{2n/3})$ time, our method offers a quadratic time speedup while maintaining the same number of queries. The time complexity of our attack is less than that observed for quantum exhaustive search by a factor of $2^{n/6}$ . We further propose classical and quantum key recovery attacks on the generalized SoEMs1 construction (consisting of $s\geq 2$ independent public permutations), revealing that the application of quantum algorithms can provide a quadratic acceleration over the pure classical methods. Our results also imply that the quantum security of SoEM21 cannot be strengthened merely by increasing the number of permutations.

DOI
10.1140/epjqt/s40507-025-00374-x

Related papers

Poster: An Improved Quantum Attack on the Two-round Even-Mansour Cipher with Independent Permutations and Keys

Rentaro Shiba, Tetsu Iwata

In this study, we propose a quantum attack on the two-round iterated Even-Mansour cipher, which consists of two independent permutations and three independent subkeys. Our attack is in the Q1 model, where an adversary makes classical online queries and quantum offline queries. The complexity of our attack is O(2n/2), where n is the block size, while the best known attack for this variant is O(23n/5). Thus, our method significantly improves the computational complexity compared to existing quantum attacks.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 19, 2025•0 citations

Quantum Attacks on Sum of Even–Mansour Construction with Linear Key Schedules

Ping Zhang

Shinagawa and Iwata are considered quantum security for the sum of Even-Mansour (SoEM) construction and provided quantum key recovery attacks by Simon's algorithm and Grover's algorithm. Furthermore, quantum key recovery attacks are also presented for natural generalizations of SoEM. For some variants of SoEM, they found that their quantum attacks are not obvious and left it as an open problem to discuss the security of such constructions. This paper focuses on this open problem and presents a positive response. We provide quantum key recovery attacks against such constructions by quantum algorithms. For natural generalizations of SoEM with linear key schedules, we also present similar quantum key recovery attacks by quantum algorithms (Simon's algorithm, Grover's algorithm, and Grover-meet-Simon algorithm).

Entropy•Jan 20, 2022•13 citations

Quantum attacks on Sum of Even-Mansour pseudorandom functions

Kazuo Shinagawa, Tetsu Iwata

At CRYPTO 2019, constructions of a pseudorandom function from public random permutations were presented. We consider one of the constructions called Sum of Even-Mansour (SoEM), and present quantum attacks against the construction. Our attacks are based on two quantum algorithms, Simon's algorithm and Grover's algorithm, and derive the secret key. We also present quantum attacks against natural variants of SoEM.

Information Processing Letters•Jul 28, 2021•15 citations

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

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 Key-Recovery Attacks on Permutation-Based Pseudorandom Functions

Hong-Wei Sun, Fei Gao, Rong-Xue Xu +3 more

Due to their simple security assessments, permutation-based pseudo-random functions (PRFs) have become widely used in cryptography. It has been shown that PRFs using a single n-bit permutation achieve n/2 bits of security, while those using two permutation calls provide 2n/3 bits of security in the classical setting. This paper studies the security of permutation-based PRFs within the Q1 model, where attackers are restricted to classical queries and offline quantum computations. We present improved quantum-time/classical-data tradeoffs compared with the previous attacks. Specifically, under the same assumptions/hardware as Grover’s exhaustive search attack, i.e. the offline Simon algorithm, we can recover keys in quantum time Õ(2n/3), with O(2n/3) classical queries and O(n2) qubits. Furthermore, we enhance previous superposition attacks by reducing the data complexity from exponential to polynomial, while maintaining the same time complexity. This implies that permutation-based PRFs become vulnerable when adversaries have access to quantum computing resources. It is pointed out that the above quantum attack can be applied to several cryptographic schemes, including PDMMAC and pEDM, as well as general instantiations like XopEM, EDMEM, EDMDEM, and others.

IEEE Internet of Things Journal•Jun 12, 2025•7 citations
The Sum of Even-Mansour (SoEM) construction, proposed by Chen et al. at Crypto 2019, has become the basis for designing some symmetric schemes, such as the nonce-based MAC scheme nEHtMp\text{nEHtM}_{p}nEHtMp​ and the nonce-based encryption scheme CENCPP∗. In this paper, we make the first attempt to study the quantum security of SoEM under the Q1 model where the targeted encryption oracle can only respond to classical queries rather than quantum ones. Firstly, we propose a quantum key recovery attack on SoEM21 with a time complexity of O~(2n/3)\tilde{O}(2^{n/3})O~(2n/3) along with O(2n/3)O(2^{n/3})O(2n/3) online classical queries. Compared with the current best classical result which requires O(22n/3)O(2^{2n/3})O(22n/3) time, our method offers a quadratic time speedup while maintaining the same number of queries. The time complexity of our attack is less than that observed for quantum exhaustive search by a factor of 2n/62^{n/6}2n/6 . We further propose classical and quantum key recovery attacks on the generalized SoEMs1 construction (consisting of s≥2s\geq 2s≥2 independent public permutations), revealing that the application of quantum algorithms can provide a quadratic acceleration over the pure classical methods. Our results also imply that the quantum security of SoEM21 cannot be strengthened merely by increasing the number of permutations.
In this study, we propose a quantum attack on the two-round iterated Even-Mansour cipher, which consists of two independent permutations and three independent subkeys. Our attack is in the Q1 model, where an adversary makes classical online queries and quantum offline queries. The complexity of our attack is O(2n/2), where n is the block size, while the best known attack for this variant is O(23n/5). Thus, our method significantly improves the computational complexity compared to existing quantum attacks.
Shinagawa and Iwata are considered quantum security for the sum of Even-Mansour (SoEM) construction and provided quantum key recovery attacks by Simon's algorithm and Grover's algorithm. Furthermore, quantum key recovery attacks are also presented for natural generalizations of SoEM. For some variants of SoEM, they found that their quantum attacks are not obvious and left it as an open problem to discuss the security of such constructions. This paper focuses on this open problem and presents a positive response. We provide quantum key recovery attacks against such constructions by quantum algorithms. For natural generalizations of SoEM with linear key schedules, we also present similar quantum key recovery attacks by quantum algorithms (Simon's algorithm, Grover's algorithm, and Grover-meet-Simon algorithm).
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.
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.
Due to their simple security assessments, permutation-based pseudo-random functions (PRFs) have become widely used in cryptography. It has been shown that PRFs using a single n-bit permutation achieve n/2 bits of security, while those using two permutation calls provide 2n/3 bits of security in the classical setting. This paper studies the security of permutation-based PRFs within the Q1 model, where attackers are restricted to classical queries and offline quantum computations. We present improved quantum-time/classical-data tradeoffs compared with the previous attacks. Specifically, under the same assumptions/hardware as Grover’s exhaustive search attack, i.e. the offline Simon algorithm, we can recover keys in quantum time Õ(2n/3), with O(2n/3) classical queries and O(n2) qubits. Furthermore, we enhance previous superposition attacks by reducing the data complexity from exponential to polynomial, while maintaining the same time complexity. This implies that permutation-based PRFs become vulnerable when adversaries have access to quantum computing resources. It is pointed out that the above quantum attack can be applied to several cryptographic schemes, including PDMMAC and pEDM, as well as general instantiations like XopEM, EDMEM, EDMDEM, and others.