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 7-round Feistel Construction.

Yinsong Xu, Zhen Yuan

Published Jul 27, 2021• 0 citations
OpenAlex

Abstract

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.

Related papers

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 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 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

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 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 Round Key Recovery Attack on Extended Generalized Feistel Network

Bohdan Dyhas, Andrii Fesenko

In this paper, we analyse the extended generalized Feistel-like scheme and construct new quantum distinguishing attacks as well as multiple new quantum round key recovery attacks on this scheme with polynomial complexity. The obtained result implies that the investigated scheme is not resistant to the quantum computing model, at least to the distinguishing attacks.

IEEE International Conference on Advanced Trends in Information Theory (ATIT)•Nov 21, 2024•0 citations
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.
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.
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.
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.
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.