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

International Conference on Communication and Network Security (ICCNS)

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

Jichen Wei, Jian Xiao Zou, Rongwei Lin

Published Dec 19, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1145/3789456.3789469

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 Truncated Differential Attacks Using Convolutions

Aurel Pichollet-Mugnier, André Schrottenloher

This paper focuses on quantum key-recovery attacks on block ciphers. Previous works on quantum differential and truncated differential attacks like [Kaplan et al., ToSC 2016] have shown that classical algorithms for key-recovery, typically based on generating differential pairs and sieving them, can be accelerated by up to a quadratic speedup using variants of quantum search, quantum amplitude amplification, and quantum collision-finding.>br/> In this paper, we introduce a new quantum truncated differential key-recovery attack, which leverages the quantum convolution algorithm introduced in [Schrottenloher, CRYPTO 2022] and previously used in linear cryptanalysis. We adapt this algorithm to the case of differential cryptanalysis, by rewriting the probability of a differential of an n-bit cipher as a convolution of functions with 2n-bit input. We then construct a quantum state whose amplitudes encode the probability of the differential for different key guesses, and use this as the starting point of a quantum search. In some cases (although not on practical ciphers so far), the speedup is better than quadratic compared to classical attacks. We also extend the framework to related-key differential attacks.We give applications to a 9-round attack on QARMAv2-64 adapted from [Ahmadian et al., DCC 2024] and a 12-round related-key attack on AES-256 from [Boura et al., CRYPTO 2023], which show improvement over classical attacks and over Kaplan et al.’s strategy when taking into account the amount of memory and the type of quantum memory used (as our attack requires only quantum-accessible classical memory).

IACR Transactions on Symmetric Cryptology•Mar 16, 2026•1 citation

Quantum Automated Tools for Finding Impossible Differentials

Huiqin Xie, Qiqing Xia, Ke Wang +2 more

Due to the superiority of quantum computing, traditional cryptography is facing a severe threat. This makes the security evaluation of cryptographic systems in quantum attack models both significant and urgent. For symmetric ciphers, the security analysis heavily relies on cryptanalysis tools. Thus, exploring the use of quantum algorithms in traditional cryptanalysis tools has garnered considerable attention. In this study, we utilize quantum algorithms to improve impossible differential attacks and design two quantum automated tools to search for impossible differentials. The proposed quantum algorithms exploit the idea of miss-in-the-middle and the properties of truncated differentials. We rigorously prove their validity and calculate the quantum resources required for their implementation. Compared to the existing classical automated cryptanalysis, the proposed quantum tools have the advantage of accurately characterizing S-boxes while only requiring polynomial complexity, and can take into consideration the impact of the key schedules in a single-key model.

arXiv:2407.10056•Mathematics•Aug 22, 2024•2 citations

Quantum Security Analysis of AES

Xavier Bonnetain, María Naya‐Plasencia, André Schrottenloher

In this paper we analyze for the first time the post-quantum security of AES. AES is the most popular and widely used block cipher, established as the encryption standard by the NIST in 2001. We consider the secret key setting and, in particular, AES-256, the recommended primitive and one of the few existing ones that aims at providing a post-quantum security of 128 bits. In order to determine the new security margin, i.e., the lowest number of non-attacked rounds in time less than 2128 encryptions, we first provide generalized and quantized versions of the best known cryptanalysis on reduced-round AES, as well as a discussion on attacks that don’t seem to benefit from a significant quantum speed-up. We propose a new framework for structured search that encompasses both the classical and quantum attacks we present, and allows to efficiently compute their complexity. We believe this framework will be useful for future analysis.Our best attack is a quantum Demirci-Selçuk meet-in-the-middle attack. Unexpectedly, using the ideas underlying its design principle also enables us to obtain new, counter-intuitive classical TMD trade-offs. In particular, we can reduce the memory in some attacks against AES-256 and AES-128.One of the building blocks of our attacks is solving efficiently the AES S-Box differential equation, with respect to the quantum cost of a reversible S-Box. We believe that this generic quantum tool will be useful for future quantum differential attacks. Judging by the results obtained so far, AES seems a resistant primitive in the post-quantum world as well as in the classical one, with a bigger security margin with respect to quantum generic attacks.

IACR Transactions on Symmetric Cryptology•Jun 11, 2019•192 citations

An efficient quantum meet-in-the-middle attack against NTRU-2005

Hong Wang, Zhi Ma, Chuan-gui Ma

NTRU is one of the most widely used public-key cryptosystems and its security has been an active research topic. This paper proposes a new way to find NTRU-2005 private key. The algorithm is based on meet-in-the-middle attack and a quantum algorithm for searching the fixed weight target. Compared with the current classical and quantum meet-in-the-middle attacks, our algorithm has lower time and space complexity. Moreover, this attack can also be applied against different versions of NTRU. The result can help to understand the security of NTRU better.

Chinese Science Bulletin•Oct 1, 2013•11 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
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.
This paper focuses on quantum key-recovery attacks on block ciphers. Previous works on quantum differential and truncated differential attacks like [Kaplan et al., ToSC 2016] have shown that classical algorithms for key-recovery, typically based on generating differential pairs and sieving them, can be accelerated by up to a quadratic speedup using variants of quantum search, quantum amplitude amplification, and quantum collision-finding.>br/> In this paper, we introduce a new quantum truncated differential key-recovery attack, which leverages the quantum convolution algorithm introduced in [Schrottenloher, CRYPTO 2022] and previously used in linear cryptanalysis. We adapt this algorithm to the case of differential cryptanalysis, by rewriting the probability of a differential of an n-bit cipher as a convolution of functions with 2n-bit input. We then construct a quantum state whose amplitudes encode the probability of the differential for different key guesses, and use this as the starting point of a quantum search. In some cases (although not on practical ciphers so far), the speedup is better than quadratic compared to classical attacks. We also extend the framework to related-key differential attacks.We give applications to a 9-round attack on QARMAv2-64 adapted from [Ahmadian et al., DCC 2024] and a 12-round related-key attack on AES-256 from [Boura et al., CRYPTO 2023], which show improvement over classical attacks and over Kaplan et al.’s strategy when taking into account the amount of memory and the type of quantum memory used (as our attack requires only quantum-accessible classical memory).
Due to the superiority of quantum computing, traditional cryptography is facing a severe threat. This makes the security evaluation of cryptographic systems in quantum attack models both significant and urgent. For symmetric ciphers, the security analysis heavily relies on cryptanalysis tools. Thus, exploring the use of quantum algorithms in traditional cryptanalysis tools has garnered considerable attention. In this study, we utilize quantum algorithms to improve impossible differential attacks and design two quantum automated tools to search for impossible differentials. The proposed quantum algorithms exploit the idea of miss-in-the-middle and the properties of truncated differentials. We rigorously prove their validity and calculate the quantum resources required for their implementation. Compared to the existing classical automated cryptanalysis, the proposed quantum tools have the advantage of accurately characterizing S-boxes while only requiring polynomial complexity, and can take into consideration the impact of the key schedules in a single-key model.
In this paper we analyze for the first time the post-quantum security of AES. AES is the most popular and widely used block cipher, established as the encryption standard by the NIST in 2001. We consider the secret key setting and, in particular, AES-256, the recommended primitive and one of the few existing ones that aims at providing a post-quantum security of 128 bits. In order to determine the new security margin, i.e., the lowest number of non-attacked rounds in time less than 2128 encryptions, we first provide generalized and quantized versions of the best known cryptanalysis on reduced-round AES, as well as a discussion on attacks that don’t seem to benefit from a significant quantum speed-up. We propose a new framework for structured search that encompasses both the classical and quantum attacks we present, and allows to efficiently compute their complexity. We believe this framework will be useful for future analysis.Our best attack is a quantum Demirci-Selçuk meet-in-the-middle attack. Unexpectedly, using the ideas underlying its design principle also enables us to obtain new, counter-intuitive classical TMD trade-offs. In particular, we can reduce the memory in some attacks against AES-256 and AES-128.One of the building blocks of our attacks is solving efficiently the AES S-Box differential equation, with respect to the quantum cost of a reversible S-Box. We believe that this generic quantum tool will be useful for future quantum differential attacks. Judging by the results obtained so far, AES seems a resistant primitive in the post-quantum world as well as in the classical one, with a bigger security margin with respect to quantum generic attacks.
NTRU is one of the most widely used public-key cryptosystems and its security has been an active research topic. This paper proposes a new way to find NTRU-2005 private key. The algorithm is based on meet-in-the-middle attack and a quantum algorithm for searching the fixed weight target. Compared with the current classical and quantum meet-in-the-middle attacks, our algorithm has lower time and space complexity. Moreover, this attack can also be applied against different versions of NTRU. The result can help to understand the security of NTRU better.
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.