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:2511.09351 · Quantum Information Processing

Quantum Meet-in-the-Middle Attacks on Key-Length Extension Constructions

Min Liang, Ruihao Gao, Jiali Wu

cs.CRquant-phSubmitted Nov 12, 2025• Announced Nov 13, 2025• 0 citations
arXivHTMLPDF

Abstract

Key-length extension (KLE) techniques provide a general approach to enhancing the security of block ciphers by using longer keys. There are mainly two classes of KLE techniques, cascade encryption and XOR-cascade encryption. This paper presents several quantum meet-in-the-middle (MITM) attacks against two specific KLE constructions. For the two-key triple encryption (2kTE), we propose two quantum MITM attacks under the Q2 model. The first attack, leveraging the quantum claw-finding (QCF) algorithm, achieves a time complexity of $O(2^{2κ/3})$ with $O(2^{2κ/3})$ quantum random access memory (QRAM). The second attack, based on Grover's algorithm, achieves a time complexity of $O(2^{κ/2})$ with $O(2^κ)$ QRAM. The latter complexity is nearly identical to Grover-based brute-force attack on the underlying block cipher, indicating that 2kTE does not enhance security under the Q2 model when sufficient QRAM resources are available. For the 3XOR-cascade encryption (3XCE), we propose a quantum MITM attack applicable to the Q1 model. This attack requires no QRAM and has a time complexity of $O(2^{(κ+n)/2})$ ($κ$ and $n$ are the key length and block length of the underlying block cipher, respectively.), achieving a quadratic speedup over classical MITM attack. Furthermore, we extend the quantum MITM attack to quantum sieve-in-the-middle (SITM) attack, which is applicable for more constructions. We present a general quantum SITM framework for the construction $ELE=E^2\circ L\circ E^1$ and provide specific attack schemes for three different forms of the middle layer $L$. The quantum SITM attack technique can be further applied to a broader range of quantum cryptanalysis scenarios.

Comments
23 pages, 4 figures

Related papers

Quantum Differential Meet‐In‐The‐Middle Attack and Some Applications to Lightweight Ciphers

Yinsong Xu, Bin‐Bin Cai, Zheng Yuan +3 more

Abstract At CRYPTO 2023, Boura et al. proposed a new cryptanalysis technique, differential meet‐in‐the‐middle (MITM) attack. They used MITM technique to make the key recovery step of a differential attack more efficient. In this study, a quantum differential meet‐in‐the‐middle attack is proposed by using nested quantum search algorithm, which can achieve up to a quadratic speed‐up compared to the classical version. Besides, the time complexity of the attack can be reduced by at least a factor of ( is the guessed key length and is the block size) compared to the first quantum differential attack proposed by Kaplan et al. at ToSC 2016. Finally, to demonstrate the efficiency of our attack, it is applied to two reduced‐round lightweight block ciphers, PIPO and SIMON , to evaluate their post‐quantum security. When attacking the same number of rounds, the time complexity of our attack is significantly lower than that of classical attacks. For the 8‐round PIPO‐128 , the attack significantly improves efficiency, reducing the time complexity from to , cutting down the required qRAM size by a factor of and obtaining the data complexity instead of compared to the best quantum attack proposed by Schrottenloher at CRYPTO 2023. For the 19‐round SIMON‐32‐64 , the time complexity here will be instead of compared to the other quantum attack, and the attack can target more rounds than using Grover‐meets‐Simon technique.

Advanced Quantum Technologies•Aug 7, 2024•6 citations

Quantum Meet-in-the-Middle Attack on 7-round Feistel Construction.

Yinsong Xu, Zhen Yuan

Quantum attacks on Feistel constructions have attracted much more attention from worldwide cryptologists. To reduce the time complexity of quantum attacks on 7-round Feistel construction, we propose a quantum meet-in-the-middle attack based on quantum claw finding algorithm and 5-round distinguisher in Q1 model firstly. Compared with quantum attacks in Q2 model, our attack reduce the time complexity from $O({2^n})$ to $O({2^{7n/8}})$. Moreover, our attack belongs to Q1 model, which is more practical than Q2 model. When compared with best classical attacks, our attack not only reduces the time complexity, but also reduces the data and memory complexity by ${2^{n/2}}$ and ${2^{n/4}}$ respectively.

•Jul 27, 2021•0 citations

Quantum Meet-in-the-Middle Attack on Feistel Constructions

Yinsong Xu, Zheng Yuan

Quantum attacks on Feistel constructions have attracted much attention from worldwide crytologists. To reduce the time complexity of quantum attacks on $r$-round ($r \ge 7$) Feistel construction, we propose a novel quantum meet-in-the-middle (QMITM) attack. For 7-round Feistel construction, we introduce quantum computing in the offline computation of the classic meet-in-the-middle (MITM) attack [Guo2016], i.e., propose a quantum claw finding algorithm based on quantum walk, which speeds up the process of finding a match in the offline computation phase. The keys in 7-round Feistel construction could be recovered by the match at last. Furthermore, to attack $r$-round ($r > 7$), we use amplitude amplification algorithm to search the last $r-7$ rounds of keys. Compared with other quantum attacks in Q2 model, our attack reduces the time complexity from $O({2^{0.25nr - n}})$ to $O({2^{2n/3 + (r - 7)n/4}})$, and is significantly better than classic attacks. Moreover, our attack only needs to make classical online queries, without quantum superposition queries in other quantum attacks, which is more practical.

•Jul 27, 2021•0 citations

Quantum attacks against iterated block ciphers

Marc Kaplan

We study the amplification of security against quantum attacks provided by iteration of block ciphers. In the classical case, the Meet-in-the-middle attack is a generic attack against those constructions. This attack reduces the time required to break double iterations to only twice the time it takes to attack a single block cipher, given that the attacker has access to a large amount of memory. More abstractly, it shows that security by composition does not achieve exact multiplicative amplification. We present a quantized version of this attack based on an optimal quantum algorithm for the Element Distinctness problem. We then use the generalized adversary method to prove the optimality of the attack. An interesting corollary is that the time-space tradeoff for quantum attacks is very different from what classical attacks allow. This first result seems to indicate that composition resists better to quantum attacks than to classical ones because it prevents the quadratic speedup achieved by quantizing an exhaustive search. We investigate security amplification by composition further by examining the case of four iterations. We quantize a recent technique called the dissection attack using the framework of quantum walks. Surprisingly, this leads to better gains over classical attacks than for double iterations, which seems to indicate that when the number of iterations grows, the resistance against quantum attacks decreases.

arXiv:1410.1434•Oct 6, 2014•26 citations

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

Improved quantum differential Meet-In-The-Middle attack and some applications

Jichen Wei, Jian Xiao Zou, Rongwei Lin

To enhance the efficiency of the quantum differential Meet-In-The-Middle attack, an improved scheme based on quantum collision search is proposed. The traditional quantum search steps were replaced with Ambainis’ quantum collision search algorithm. This replacement optimized the matching process between candidate keys and plaintexts in the Meet-in-the-Middle phase and significantly reduced time complexity. The improved attack scheme is applied to PIPO-128, SKINNY-128-384, and AES-256, achieving key recovery attacks for 8, 23, and 12 rounds, respectively. Analysis results under both Q1 and Q2 models demonstrate that the proposed scheme outperforms existing classical and quantum attacks in both time and memory complexity, validating its effectiveness and superiority in cryptanalysis.

International Conference on Communication and Network Security (ICCNS)•Dec 19, 2025•0 citations
Key-length extension (KLE) techniques provide a general approach to enhancing the security of block ciphers by using longer keys. There are mainly two classes of KLE techniques, cascade encryption and XOR-cascade encryption. This paper presents several quantum meet-in-the-middle (MITM) attacks against two specific KLE constructions.
For the two-key triple encryption (2kTE), we propose two quantum MITM attacks under the Q2 model. The first attack, leveraging the quantum claw-finding (QCF) algorithm, achieves a time complexity of O(22κ/3)O(2^{2κ/3})O(22κ/3) with O(22κ/3)O(2^{2κ/3})O(22κ/3) quantum random access memory (QRAM). The second attack, based on Grover's algorithm, achieves a time complexity of O(2κ/2)O(2^{κ/2})O(2κ/2) with O(2κ)O(2^κ)O(2κ) QRAM. The latter complexity is nearly identical to Grover-based brute-force attack on the underlying block cipher, indicating that 2kTE does not enhance security under the Q2 model when sufficient QRAM resources are available.
For the 3XOR-cascade encryption (3XCE), we propose a quantum MITM attack applicable to the Q1 model. This attack requires no QRAM and has a time complexity of O(2(κ+n)/2)O(2^{(κ+n)/2})O(2(κ+n)/2) (κκκ and nnn are the key length and block length of the underlying block cipher, respectively.), achieving a quadratic speedup over classical MITM attack.
Furthermore, we extend the quantum MITM attack to quantum sieve-in-the-middle (SITM) attack, which is applicable for more constructions. We present a general quantum SITM framework for the construction ELE=E2∘L∘E1ELE=E^2\circ L\circ E^1ELE=E2∘L∘E1 and provide specific attack schemes for three different forms of the middle layer LLL. The quantum SITM attack technique can be further applied to a broader range of quantum cryptanalysis scenarios.
Abstract At CRYPTO 2023, Boura et al. proposed a new cryptanalysis technique, differential meet‐in‐the‐middle (MITM) attack. They used MITM technique to make the key recovery step of a differential attack more efficient. In this study, a quantum differential meet‐in‐the‐middle attack is proposed by using nested quantum search algorithm, which can achieve up to a quadratic speed‐up compared to the classical version. Besides, the time complexity of the attack can be reduced by at least a factor of ( is the guessed key length and is the block size) compared to the first quantum differential attack proposed by Kaplan et al. at ToSC 2016. Finally, to demonstrate the efficiency of our attack, it is applied to two reduced‐round lightweight block ciphers, PIPO and SIMON , to evaluate their post‐quantum security. When attacking the same number of rounds, the time complexity of our attack is significantly lower than that of classical attacks. For the 8‐round PIPO‐128 , the attack significantly improves efficiency, reducing the time complexity from to , cutting down the required qRAM size by a factor of and obtaining the data complexity instead of compared to the best quantum attack proposed by Schrottenloher at CRYPTO 2023. For the 19‐round SIMON‐32‐64 , the time complexity here will be instead of compared to the other quantum attack, and the attack can target more rounds than using Grover‐meets‐Simon technique.
Quantum attacks on Feistel constructions have attracted much more attention from worldwide cryptologists. To reduce the time complexity of quantum attacks on 7-round Feistel construction, we propose a quantum meet-in-the-middle attack based on quantum claw finding algorithm and 5-round distinguisher in Q1 model firstly. Compared with quantum attacks in Q2 model, our attack reduce the time complexity from O(2n)O({2^n})O(2n) to O(27n/8)O({2^{7n/8}})O(27n/8). Moreover, our attack belongs to Q1 model, which is more practical than Q2 model. When compared with best classical attacks, our attack not only reduces the time complexity, but also reduces the data and memory complexity by 2n/2{2^{n/2}}2n/2 and 2n/4{2^{n/4}}2n/4 respectively.
Quantum attacks on Feistel constructions have attracted much attention from worldwide crytologists. To reduce the time complexity of quantum attacks on rrr-round (r≥7r \ge 7r≥7) Feistel construction, we propose a novel quantum meet-in-the-middle (QMITM) attack. For 7-round Feistel construction, we introduce quantum computing in the offline computation of the classic meet-in-the-middle (MITM) attack [Guo2016], i.e., propose a quantum claw finding algorithm based on quantum walk, which speeds up the process of finding a match in the offline computation phase. The keys in 7-round Feistel construction could be recovered by the match at last. Furthermore, to attack rrr-round (r>7r > 7r>7), we use amplitude amplification algorithm to search the last r−7r-7r−7 rounds of keys. Compared with other quantum attacks in Q2 model, our attack reduces the time complexity from O(20.25nr−n)O({2^{0.25nr - n}})O(20.25nr−n) to O(22n/3+(r−7)n/4)O({2^{2n/3 + (r - 7)n/4}})O(22n/3+(r−7)n/4), and is significantly better than classic attacks. Moreover, our attack only needs to make classical online queries, without quantum superposition queries in other quantum attacks, which is more practical.
We study the amplification of security against quantum attacks provided by iteration of block ciphers. In the classical case, the Meet-in-the-middle attack is a generic attack against those constructions. This attack reduces the time required to break double iterations to only twice the time it takes to attack a single block cipher, given that the attacker has access to a large amount of memory. More abstractly, it shows that security by composition does not achieve exact multiplicative amplification. We present a quantized version of this attack based on an optimal quantum algorithm for the Element Distinctness problem. We then use the generalized adversary method to prove the optimality of the attack. An interesting corollary is that the time-space tradeoff for quantum attacks is very different from what classical attacks allow. This first result seems to indicate that composition resists better to quantum attacks than to classical ones because it prevents the quadratic speedup achieved by quantizing an exhaustive search. We investigate security amplification by composition further by examining the case of four iterations. We quantize a recent technique called the dissection attack using the framework of quantum walks. Surprisingly, this leads to better gains over classical attacks than for double iterations, which seems to indicate that when the number of iterations grows, the resistance against quantum attacks decreases.
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.
To enhance the efficiency of the quantum differential Meet-In-The-Middle attack, an improved scheme based on quantum collision search is proposed. The traditional quantum search steps were replaced with Ambainis’ quantum collision search algorithm. This replacement optimized the matching process between candidate keys and plaintexts in the Meet-in-the-Middle phase and significantly reduced time complexity. The improved attack scheme is applied to PIPO-128, SKINNY-128-384, and AES-256, achieving key recovery attacks for 8, 23, and 12 rounds, respectively. Analysis results under both Q1 and Q2 models demonstrate that the proposed scheme outperforms existing classical and quantum attacks in both time and memory complexity, validating its effectiveness and superiority in cryptanalysis.