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

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

Yinsong Xu, Zheng Yuan

Published Jul 27, 2021• 0 citations
OpenAlex

Abstract

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.

Related papers

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 Attacks on Key-Length Extension Constructions

Min Liang, Ruihao Gao, Jiali Wu

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.

cs.CRCross-listedarXiv:2511.09351•Quantum Information Processing•Nov 13, 2025•0 citations

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

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

Quantum Cryptanalysis on Two Feistel-Type Constructions

Yan-Ying Zhu, Bin-Bin Cai, Fei Gao +1 more

With the rapid advancement of quantum computing, the security of traditional cryptographic systems is facing significant challenges. As a fundamental component of symmetric cryptography, block ciphers have attracted increasing attention regarding their quantum security in recent years. In this paper, we propose new quantum attacks on two Feistel-type constructions, i.e., New Structure IV and the lightweight block cipher LBlock, under the quantum chosen-plaintext attack (qCPA) model. First, we construct an 8-round quantum distinguisher for New Structure IV and perform an $r(r>12)$-round quantum key-recovery attack. Compared with Li et al.'s qCPA-based result presented at INSCRYPT 2024, our attack reduces the time complexity by a factor of $2^{n/2}$, where $n$ denotes the subkey length. Second, we design a 9-round quantum distinguisher for LBlock and extend it to an $r(r>15)$-round quantum key-recovery attack. The proposed quantum distinguisher covers one more round than Liu et al.'s automated-search distinguisher at ASIACRYPT 2025, which results in a $2^{16}$ reduction in the time complexity of our $r$-round quantum key-recovery attack on LBlock. Furthermore, by analyzing the structure of the round function and the key scheduling of LBlock, we reduce the subkey guess space for the 15-round attack from 76 bits to 52 bits, lowering the time complexity from \(O(2^{38})\) to \(O(2^{26})\) by a factor of \(2^{12}\).

quant-pharXiv:2610.27506•Oct 21, 2026•0 citations

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 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.
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.
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.
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.
With the rapid advancement of quantum computing, the security of traditional cryptographic systems is facing significant challenges. As a fundamental component of symmetric cryptography, block ciphers have attracted increasing attention regarding their quantum security in recent years. In this paper, we propose new quantum attacks on two Feistel-type constructions, i.e., New Structure IV and the lightweight block cipher LBlock, under the quantum chosen-plaintext attack (qCPA) model. First, we construct an 8-round quantum distinguisher for New Structure IV and perform an r(r>12)r(r>12)r(r>12)-round quantum key-recovery attack. Compared with Li et al.'s qCPA-based result presented at INSCRYPT 2024, our attack reduces the time complexity by a factor of 2n/22^{n/2}2n/2, where nnn denotes the subkey length. Second, we design a 9-round quantum distinguisher for LBlock and extend it to an r(r>15)r(r>15)r(r>15)-round quantum key-recovery attack. The proposed quantum distinguisher covers one more round than Liu et al.'s automated-search distinguisher at ASIACRYPT 2025, which results in a 2162^{16}216 reduction in the time complexity of our rrr-round quantum key-recovery attack on LBlock. Furthermore, by analyzing the structure of the round function and the key scheduling of LBlock, we reduce the subkey guess space for the 15-round attack from 76 bits to 52 bits, lowering the time complexity from O(238)O(2^{38})O(238) to O(226)O(2^{26})O(226) by a factor of 2122^{12}212.
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.