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

IACR Transactions on Symmetric Cryptology

Multi-Key Security in the Quantum World: Revisiting Tweakable Even-Mansour and FX

Rentaro Shiba, Tetsu Iwata

Published Jun 11, 2026• 2 citations
Publisher

Abstract

In this paper, we prove the security of symmetric-key constructions in an adversary model called the Q1MK model, which combines the Q1 model, where the adversary makes classical online queries and quantum offline queries, and the multi-key (multi-user) setting. Specifically, under this model, we prove the security of two symmetric-key constructions: the tweakable Even-Mansour cipher (TEM) and the FX construction (FX), as starting points for understanding the post-quantum security of symmetric-key constructions in this adversary model. Our security proofs are based on the hybrid argument technique introduced by Alagic et al. at EUROCRYPT 2022. First, we prove that in order to break TEM in the Q1MK model, Ω(2Κ/3) classical and quantum queries are needed, regardless of the number of target Κ-bit keys. Then, before turning to the Q1MK security analysis of FX, we revisit the security proof of FX in the standard Q1 model proposed in version 20230317:200508 of ePrint 2022/1097 and tighten it. By the modified proof, we show that in order to break FX with (Κ + n)-bit secret key in the Q1 model, Ω(2(Κ+n)/3) classical and quantum queries are needed. We then apply this proof to the Q1MK setting, and we show that in order to break FX in the Q1MK model, Ω(2(Κ + n - u)/3) classical and quantum queries are needed, when 2u ( 2Κ) independent keys are in use.

DOI
10.46586/tosc.abksudsuurh6

Related papers

Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks

Bai, Chen, Esmaili, Mehdi, Mantri, Atul

We study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even--Mansour construction. KAC abstracts the round structure of practical block ciphers as public permutations interleaved with key XORs. The $1$-round KAC or EM setting already highlights the power of quantum superposition access: EM is secure against classical and Q1 adversaries (quantum access to the public permutation), but insecure in the Q2 model. The security of multi-round KACs remain largely unexplored; in particular, whether the quantum-classical separation extends beyond a single round had remained open. 1) Quantum Lower Bounds. We prove security of the $t$-round KAC against a non-adaptive adversary in both the Q1 and Q2 models. In the Q1 model, any distinguiser requires $Ω(2^{\frac{tn}{2t+1}})$ oracle queries to distinguish the cipher from a random permutation, whereas classically any distinguisher needs $Ω(2^{\frac{tn}{t+1}})$ queries. As a corollary, we obtain a Q2 lower bound of $Ω(2^{\frac{(t-1)n}{2t}})$ quantum queries. Thus, for $t \geq 2$, the exponential Q1-Q2 gap collapses in the non-adaptive setting, partially resolving an open problem posed by Kuwakado and Morii (2012). Our proofs develop a controlled-reprogramming framework within a quantum hybrid argument, sidestepping the lack of quantum recording techniques for permutation-based ciphers; we expect this framework to be useful for analyzing other post-quantum symmetric primitives. 2) Quantum Key-Recovery Attack. We give the first non-trivial quantum key-recovery algorithm for $t$-round KAC in the Q1 model. It makes $O(2^{αn})$ queries with $α= \frac{t(t+1)}{(t+1)^2 + 1}$, improving on the best known classical bound of $O(2^{α' n})$ with $α' = \frac{t}{t+1}$. The algorithm adapts quantum walk techniques to the KAC structure.

arXiv:2412.05026•Dec 6, 2024•0 citations

Post-Quantum Security of Block Cipher Constructions

Gorjan Alagic, Chen Bai, Christian Majenz +1 more

Block ciphers are versatile cryptographic ingredients that are used in a wide range of applications ranging from secure Internet communications to disk encryption. While post-quantum security of public-key cryptography has received significant attention, the case of symmetric-key cryptography (and block ciphers in particular) remains a largely unexplored topic. In this work, we set the foundations for a theory of post-quantum security for block ciphers and associated constructions. Leveraging our new techniques, we provide the first post-quantum security proofs for the key-length extension scheme FX, the tweakable block ciphers LRW and XEX, and most block cipher encryption and authentication modes. Our techniques can be used for security proofs in both the plain model and the quantum ideal cipher model. Our work takes significant initial steps in establishing a rigorous understanding of the post-quantum security of practical symmetric-key cryptography.

arXiv:2510.08725•Oct 9, 2025•0 citations

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

Zhenqiang Li, Shuqin Fan, Fei Gao +4 more

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.

EPJ Quantum Technology•Jun 5, 2025•2 citations

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

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

Provable Post-Quantum Security of the 3-Round Substitution-Permutation Network

Rentaro Shiba, Tetsu Iwata

Substitution-Permutation Networks (SPNs) constitute a major design paradigm for block ciphers. While the provable security of generic SPNs has been studied in the classical setting, their security against quantum adversaries remains largely unexplored. In this work, we provide the first provable security result for a generic SPN construction against quantum adversaries. Specifically, we prove that the generic 3-round linear SPN whose classical security was established by Dodis et al., instantiated with independent and uniformly distributed round and whitening keys, achieves post-quantum SPRP security in the Q1 model. In this model, construction queries are classical, while the adversary is given quantum forward and inverse access to the underlying public random permutation. The construction operates on a w n -bit state and applies this n -bit permutation, which corresponds to the S-box, in parallel to w state blocks in each round, with linear transformations and key additions between the S-box layers. For a constant w , our bound implies security up to approximately 2 n / 3 quantum and classical queries. Our proof builds on the hybrid argument introduced by Alagic et al. at EUROCRYPT 2022. The main technical challenge is to bound bad events caused by collisions among hidden internal values arising from the parallel and repeated use of the same public permutation. To overcome this difficulty, we develop new technical tools for bounding such internal-collision events in the presence of quantum forward and inverse access to the public random permutation. Our result also shows that the 3-round linear SPN can be viewed as a post-quantum-secure domain-extension method for constructing a keyed pseudorandom permutation on w n bits from a random permutation on n bits.

IACR Communications in Cryptology•Oct 26, 2026•0 citations
In this paper, we prove the security of symmetric-key constructions in an adversary model called the Q1MK model, which combines the Q1 model, where the adversary makes classical online queries and quantum offline queries, and the multi-key (multi-user) setting. Specifically, under this model, we prove the security of two symmetric-key constructions: the tweakable Even-Mansour cipher (TEM) and the FX construction (FX), as starting points for understanding the post-quantum security of symmetric-key constructions in this adversary model. Our security proofs are based on the hybrid argument technique introduced by Alagic et al. at EUROCRYPT 2022. First, we prove that in order to break TEM in the Q1MK model, Ω(2Κ/3) classical and quantum queries are needed, regardless of the number of target Κ-bit keys. Then, before turning to the Q1MK security analysis of FX, we revisit the security proof of FX in the standard Q1 model proposed in version 20230317:200508 of ePrint 2022/1097 and tighten it. By the modified proof, we show that in order to break FX with (Κ + n)-bit secret key in the Q1 model, Ω(2(Κ+n)/3) classical and quantum queries are needed. We then apply this proof to the Q1MK setting, and we show that in order to break FX in the Q1MK model, Ω(2(Κ + n - u)/3) classical and quantum queries are needed, when 2u ( 2Κ) independent keys are in use.
We study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even--Mansour construction. KAC abstracts the round structure of practical block ciphers as public permutations interleaved with key XORs. The 111-round KAC or EM setting already highlights the power of quantum superposition access: EM is secure against classical and Q1 adversaries (quantum access to the public permutation), but insecure in the Q2 model. The security of multi-round KACs remain largely unexplored; in particular, whether the quantum-classical separation extends beyond a single round had remained open. 1) Quantum Lower Bounds. We prove security of the ttt-round KAC against a non-adaptive adversary in both the Q1 and Q2 models. In the Q1 model, any distinguiser requires Ω(2tn2t+1)Ω(2^{\frac{tn}{2t+1}})Ω(22t+1tn​) oracle queries to distinguish the cipher from a random permutation, whereas classically any distinguisher needs Ω(2tnt+1)Ω(2^{\frac{tn}{t+1}})Ω(2t+1tn​) queries. As a corollary, we obtain a Q2 lower bound of Ω(2(t−1)n2t)Ω(2^{\frac{(t-1)n}{2t}})Ω(22t(t−1)n​) quantum queries. Thus, for t≥2t \geq 2t≥2, the exponential Q1-Q2 gap collapses in the non-adaptive setting, partially resolving an open problem posed by Kuwakado and Morii (2012). Our proofs develop a controlled-reprogramming framework within a quantum hybrid argument, sidestepping the lack of quantum recording techniques for permutation-based ciphers; we expect this framework to be useful for analyzing other post-quantum symmetric primitives. 2) Quantum Key-Recovery Attack. We give the first non-trivial quantum key-recovery algorithm for ttt-round KAC in the Q1 model. It makes O(2αn)O(2^{αn})O(2αn) queries with α=t(t+1)(t+1)2+1α= \frac{t(t+1)}{(t+1)^2 + 1}α=(t+1)2+1t(t+1)​, improving on the best known classical bound of O(2α′n)O(2^{α' n})O(2α′n) with α′=tt+1α' = \frac{t}{t+1}α′=t+1t​. The algorithm adapts quantum walk techniques to the KAC structure.
Block ciphers are versatile cryptographic ingredients that are used in a wide range of applications ranging from secure Internet communications to disk encryption. While post-quantum security of public-key cryptography has received significant attention, the case of symmetric-key cryptography (and block ciphers in particular) remains a largely unexplored topic. In this work, we set the foundations for a theory of post-quantum security for block ciphers and associated constructions. Leveraging our new techniques, we provide the first post-quantum security proofs for the key-length extension scheme FX, the tweakable block ciphers LRW and XEX, and most block cipher encryption and authentication modes. Our techniques can be used for security proofs in both the plain model and the quantum ideal cipher model. Our work takes significant initial steps in establishing a rigorous understanding of the post-quantum security of practical symmetric-key cryptography.
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.
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.
Substitution-Permutation Networks (SPNs) constitute a major design paradigm for block ciphers. While the provable security of generic SPNs has been studied in the classical setting, their security against quantum adversaries remains largely unexplored. In this work, we provide the first provable security result for a generic SPN construction against quantum adversaries. Specifically, we prove that the generic 3-round linear SPN whose classical security was established by Dodis et al., instantiated with independent and uniformly distributed round and whitening keys, achieves post-quantum SPRP security in the Q1 model. In this model, construction queries are classical, while the adversary is given quantum forward and inverse access to the underlying public random permutation. The construction operates on a w n -bit state and applies this n -bit permutation, which corresponds to the S-box, in parallel to w state blocks in each round, with linear transformations and key additions between the S-box layers. For a constant w , our bound implies security up to approximately 2 n / 3 quantum and classical queries. Our proof builds on the hybrid argument introduced by Alagic et al. at EUROCRYPT 2022. The main technical challenge is to bound bad events caused by collisions among hidden internal values arising from the parallel and repeated use of the same public permutation. To overcome this difficulty, we develop new technical tools for bounding such internal-collision events in the presence of quantum forward and inverse access to the public random permutation. Our result also shows that the 3-round linear SPN can be viewed as a post-quantum-secure domain-extension method for constructing a keyed pseudorandom permutation on w n bits from a random permutation on n bits.