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

IEEE Transactions on Information Forensics and Security

Dedicated Quantum Attacks on XOR-Type Function With Applications to Beyond-Birthday- Bound MACs

Tairong Shi, Wenling Wu, Bin Hu, Jie Guan, Han Sui, Senpeng Wang, Mengyuan Zhang

Published Jan 1, 2024• 3 citations
Publisher

Abstract

A lot of work in the field of quantum cryptanalysis is currently devoted to finding applications of Grover-meets-Simon algorithm and its complexity is given in the form of$\mathcal {O}$, but research on how to implement the attack efficiently is still insufficient. After all, it is crucial to study quantum attacks in resource-limited situations, according to NIST’s guidance on circuit depth. This work first evaluates the parallelization of Grover-meets-Simon by drawing on the Grover’s parallel approach and shows that as the width increases by$2^{t}(t\gt 0)$, the depth decreases by a factor of$\sqrt {2^{t}}$. Further, the first dedicated quantum attack on a class of functions that appear in cryptographic scheme applications (so-called XOR-type function) is proposed. The depth, width, and the number of gates required for the attack are greatly reduced compared to the general parallelization. Then we apply the attack to various Beyond-Birthday-Bound (BBB) MACs, where the XOR function can be constructed, includingSUM-ECBCand its variants (2K-SUM-ECBC,2K-ECBC_Plus), andGCM-SIV2. In the typical case whereSUM-ECBCis based on AES-128, our attack saves at least 62.3% in depth, 19.5% in width and 22.2% in gate count simultaneously. The impact on some lightweight ciphers is further explored, and it is interesting to note that the lighter the quantum circuit implementation of the cipher is, the greater the possible impact of an attack will be. This observation may provide new insights into quantum cryptanalysis.

DOI
10.1109/tifs.2024.3402970

Related papers

Quantum grover attack on MIBS

Hasan Özgür Çıldıroğlu, Harun Basmaci, Oğuz Yayla

Abstract The advent of quantum computing necessitates a rigorous reassessment of classical cryptographic primitives, particularly lightweight block ciphers (LBCs) deployed in resource-constrained environments. This work presents a comprehensive quantum implementation and security analysis of the Feistel-based LBC MIBS against quantum cryptanalysis. Using the inherent reversibility of its structure, we develop a novel ancilla-free quantum circuit that optimizes qubit count and depth. For MIBS-64 and MIBS-80, our implementation achieves quantum costs of 23,371 and 24,363, requiring 128 and 144 qubits, respectively, with a depth of 4,768. We subsequently quantify the cipher’s vulnerability to Grover’s key-search algorithm under the NIST PQC security constraint M A X D E P T H $\mathtt{M}\mathtt{A}\mathtt{X}\mathtt{D}\mathtt{E}\mathtt{P}\mathtt{T}\mathtt{H}$ . By constructing Grover oracles using inner parallelization with multiple plaintext-ciphertext pairs to suppress false positives, we demonstrate total quantum attack costs of approximately 2 94 for MIBS-64 and 2 111 for MIBS-80. These values fall below NIST’s Level-1 security threshold (2 170 ), confirming the susceptibility of both MIBS variants to quantum key-recovery attacks despite their classical lightweight efficiency.

Open Physics•Jan 1, 2026•0 citations

Quantum Analysis of AES

Kyungbae Jang, Anubhab Baksi, Hyunji Kim +3 more

Our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256). In total, we develop a pool of 26 implementations per AES variant (totaling 78), by taking the state-of-the-art advancements in the relevant fields into account. We present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.'s Asiacrypt'20 paper by more than 97 percent for each variant of AES. We show that the qubit count - Toffoli depth product is reduced from theirs by more than 87 percent. Furthermore, we analyze the Jaques et al.'s Eurocrypt'20 implementations in detail, fix the bugs (arising from some problem of the quantum computing tool used), and report corrected benchmarks (which seem to improve from the authors' own bug-fixing, thanks to our architecture consideration). To the best of our finding, our work improves from all the previous works (including the Asiacrypt'22 paper by Huang and Sun, the Asiacrypt'23 paper by Liu et al. and the Asiacrypt'24 paper by Shi and Feng) in terms of various quantum circuit complexity metrics. To be more precise, we estimate the currently best-known quantum attack complexities for AES-128 ( 2 156.2630 ), AES-192 ( 2 221.5801 ) and AES-256 ( 2 286.0731 ). Additionally, we achieve the least Toffoli depth - qubit count product for AES-128 ( 121920 , improving from 130720 by Shi and Feng in Asiacrypt'24), AES-192 ( 161664 , improving from 188880 by Liu et al. in Asiacrypt'23) and AES-256 ( 206528 , improving from 248024 by Liu et al. in Asiacrypt'23) so far. We further investigate the prospect of the Grover's search. We propose four new implementations of the S-box, one new implementation of the MixColumn; as well as five new architecture (one is motivated by the architecture by Jaques et al. in Eurocrypt'20, and the rest four are entirely our innovation). Under the MAXDEPTH constraint (specified by NIST), the circuit depth metrics (Toffoli depth, T -depth and full depth) become crucial factors and parallelization for often becomes necessary. We provide the least depth implementation in this respect that offers the best performance in terms of metrics like depth-squared - qubit count product, depth - gate count product.

IACR Communications in Cryptology•Apr 8, 2025•32 citations

Implementing Grover’s on AES-based AEAD schemes

Surajit Mandal, Ravi Anand, Mostafizar Rahman +2 more

Extensive research is currently underway to determine the security of existing ciphers in light of the advancements in quantum computing. Against symmetric key cryptography, Grover’s search algorithm is a prominent attack, capable of reducing search costs to the square root. For using Grover’s algorithm, it is imperative to embed the target cipher into a quantum circuit. Even so, this area of research is relatively new; it has garnered significant attention from the research community. In this study, we provide the first estimation of the cost of Grover’s key search attack against the AES-based AEAD schemes Rocca-S, AEGIS-128, and Tiaoxin-346. Our analysis considers circuit depth restrictions specified in NIST’s PQC standardization process. Considering NIST’s maximum depth constraints, We present the overall cost of these attacks using gate count and depth-times-width metrics. We observed that for $$\textsf{MAXDEPTH} = 2^{40}$$ , Rocca-S, AEGIS-128, and Tiaoxin-346 can be retrieved using Grover’s search algorithm with gate count of 1.09 × 2253, 1.14 × 2124, and 1.22 × 2124 respectively. Concerning the current updated values by NIST, these ciphers are secure in terms of the cost of implementing Grover’s attack for key recovery. The quantum circuits of these ciphers are implemented using QISKIT, an open-source software development kit (SDK) designed for working with quantum computers running on the IBM Quantum Experience platform.

Scientific Reports•Sep 10, 2024•9 citations

Faster Quantum Algorithms for MQ2 and Applications

Quentin Edme, Pierre-Alain Fouque, André Schrottenloher

We study quantum algorithms for multivariate quadratic Boolean equation systems by focusing on their precise gate count. While better asymptotic algorithms are known, currently gate counts were only computed for exhaustive search (Schwabe and Westerbaan, SPACE 2016) and a variant of Grover's search using preprocessing (Pring, WAIFI 2018). This limits the applicability of Boolean equation solving to cryptanalysis, which considers relatively small numbers of variables (from 40 to 200) and is concerned with the exact complexity of the solver. In this paper, we introduce two new quantum algorithms. The first algorithm is an optimized quantum exhaustive search which amortizes the cost of polynomial evaluation at each quantum search iterate. The second algorithm adapts a method of Bouillaguet et al. (SOSA 2022) which proceeds by linearization of the system. In both cases, we implement the quantum circuits, study their complexity, and obtain significant improvements over previous results. Next, we apply these new algorithms to the cryptanalysis of the block ciphers LowMC and RAIN in the single-data setting. By adapting attacks from Liu et al. (ToSC 2022) and Liu et al. (ToSC 2023) we obtain the first quantum cryptanalysis results on these ciphers.

IACR Communications in Cryptology•Apr 8, 2025•0 citations

Quantum Implementation of AIM: Aiming for Low-Depth

Kyungbae Jang, Yujin Oh, Hyunji Kim +1 more

Security vulnerabilities in the symmetric-key primitives of a cipher can undermine the overall security claims of the cipher. With the rapid advancement of quantum computing in recent years, there is an increasing effort to evaluate the security of symmetric-key cryptography against potential quantum attacks. This paper focuses on analyzing the quantum attack resistance of AIM, a symmetric-key primitive used in the AIMer digital signature scheme. We present the first quantum circuit implementation of AIM and estimate its complexity (such as qubit count, gate count, and circuit depth) with respect to Grover’s search algorithm. For Grover’s key search, the most important optimization metric is depth, especially when considering parallel search. Our implementation gathers multiple methods for a low-depth quantum circuit of AIM in order to reduce the Toffoli depth and full depth (such as the Karatsuba multiplication and optimization of inner modules; Mer, LinearLayer).

Applied Sciences•Mar 27, 2024•4 citations

Constructing resource-efficient quantum circuits for AES

Liang Jiang, Bin‐Bin Cai, Fei Gao +3 more

An efficient quantum implementation of the advanced encryption standard (AES) is crucial for reducing the complexity of implementing an exhaustive key search through Grover’s algorithm. In this paper, we study how to construct resource-efficient quantum circuits for AES. We consider the product of T-gates depth and width (TDW) and the product of full depth and width (FDW) as optimization targets. We propose a generic method, called the controlled control qubit cascade (CCQC) technique, to construct quantum circuits for nonlinear components with reduced TDW and FDW. Using this, we construct a quantum circuit for the AES S-box. Compared with recent work presented at ASIACRYPT 2023, our S-box quantum circuit achieves reductions of 2.3% in TDW and 45.2% in FDW. Additionally, we propose a new key schedule strategy to reduce the full depth of the AES quantum circuit. Finally, the trade-offs between T-gates depth and width and the parallel numbers of S-box and TDW are analyzed.

Frontiers in Physics•Apr 22, 2025•2 citations
A lot of work in the field of quantum cryptanalysis is currently devoted to finding applications of Grover-meets-Simon algorithm and its complexity is given in the form ofO\mathcal {O}O, but research on how to implement the attack efficiently is still insufficient. After all, it is crucial to study quantum attacks in resource-limited situations, according to NIST’s guidance on circuit depth. This work first evaluates the parallelization of Grover-meets-Simon by drawing on the Grover’s parallel approach and shows that as the width increases by2t(t>0)2^{t}(t\gt 0)2t(t>0), the depth decreases by a factor of2t\sqrt {2^{t}}2t​. Further, the first dedicated quantum attack on a class of functions that appear in cryptographic scheme applications (so-called XOR-type function) is proposed. The depth, width, and the number of gates required for the attack are greatly reduced compared to the general parallelization. Then we apply the attack to various Beyond-Birthday-Bound (BBB) MACs, where the XOR function can be constructed, includingSUM-ECBCand its variants (2K-SUM-ECBC,2K-ECBC_Plus), andGCM-SIV2. In the typical case whereSUM-ECBCis based on AES-128, our attack saves at least 62.3% in depth, 19.5% in width and 22.2% in gate count simultaneously. The impact on some lightweight ciphers is further explored, and it is interesting to note that the lighter the quantum circuit implementation of the cipher is, the greater the possible impact of an attack will be. This observation may provide new insights into quantum cryptanalysis.
Abstract The advent of quantum computing necessitates a rigorous reassessment of classical cryptographic primitives, particularly lightweight block ciphers (LBCs) deployed in resource-constrained environments. This work presents a comprehensive quantum implementation and security analysis of the Feistel-based LBC MIBS against quantum cryptanalysis. Using the inherent reversibility of its structure, we develop a novel ancilla-free quantum circuit that optimizes qubit count and depth. For MIBS-64 and MIBS-80, our implementation achieves quantum costs of 23,371 and 24,363, requiring 128 and 144 qubits, respectively, with a depth of 4,768. We subsequently quantify the cipher’s vulnerability to Grover’s key-search algorithm under the NIST PQC security constraint M A X D E P T H MAXDEPTH\mathtt{M}\mathtt{A}\mathtt{X}\mathtt{D}\mathtt{E}\mathtt{P}\mathtt{T}\mathtt{H}MAXDEPTH . By constructing Grover oracles using inner parallelization with multiple plaintext-ciphertext pairs to suppress false positives, we demonstrate total quantum attack costs of approximately 2 94 for MIBS-64 and 2 111 for MIBS-80. These values fall below NIST’s Level-1 security threshold (2 170 ), confirming the susceptibility of both MIBS variants to quantum key-recovery attacks despite their classical lightweight efficiency.
Our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256). In total, we develop a pool of 26 implementations per AES variant (totaling 78), by taking the state-of-the-art advancements in the relevant fields into account. We present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.'s Asiacrypt'20 paper by more than 97 percent for each variant of AES. We show that the qubit count - Toffoli depth product is reduced from theirs by more than 87 percent. Furthermore, we analyze the Jaques et al.'s Eurocrypt'20 implementations in detail, fix the bugs (arising from some problem of the quantum computing tool used), and report corrected benchmarks (which seem to improve from the authors' own bug-fixing, thanks to our architecture consideration). To the best of our finding, our work improves from all the previous works (including the Asiacrypt'22 paper by Huang and Sun, the Asiacrypt'23 paper by Liu et al. and the Asiacrypt'24 paper by Shi and Feng) in terms of various quantum circuit complexity metrics. To be more precise, we estimate the currently best-known quantum attack complexities for AES-128 ( 2 156.2630 ), AES-192 ( 2 221.5801 ) and AES-256 ( 2 286.0731 ). Additionally, we achieve the least Toffoli depth - qubit count product for AES-128 ( 121920 , improving from 130720 by Shi and Feng in Asiacrypt'24), AES-192 ( 161664 , improving from 188880 by Liu et al. in Asiacrypt'23) and AES-256 ( 206528 , improving from 248024 by Liu et al. in Asiacrypt'23) so far. We further investigate the prospect of the Grover's search. We propose four new implementations of the S-box, one new implementation of the MixColumn; as well as five new architecture (one is motivated by the architecture by Jaques et al. in Eurocrypt'20, and the rest four are entirely our innovation). Under the MAXDEPTH constraint (specified by NIST), the circuit depth metrics (Toffoli depth, T -depth and full depth) become crucial factors and parallelization for often becomes necessary. We provide the least depth implementation in this respect that offers the best performance in terms of metrics like depth-squared - qubit count product, depth - gate count product.
Extensive research is currently underway to determine the security of existing ciphers in light of the advancements in quantum computing. Against symmetric key cryptography, Grover’s search algorithm is a prominent attack, capable of reducing search costs to the square root. For using Grover’s algorithm, it is imperative to embed the target cipher into a quantum circuit. Even so, this area of research is relatively new; it has garnered significant attention from the research community. In this study, we provide the first estimation of the cost of Grover’s key search attack against the AES-based AEAD schemes Rocca-S, AEGIS-128, and Tiaoxin-346. Our analysis considers circuit depth restrictions specified in NIST’s PQC standardization process. Considering NIST’s maximum depth constraints, We present the overall cost of these attacks using gate count and depth-times-width metrics. We observed that for MAXDEPTH=240\textsf{MAXDEPTH} = 2^{40}MAXDEPTH=240 , Rocca-S, AEGIS-128, and Tiaoxin-346 can be retrieved using Grover’s search algorithm with gate count of 1.09 × 2253, 1.14 × 2124, and 1.22 × 2124 respectively. Concerning the current updated values by NIST, these ciphers are secure in terms of the cost of implementing Grover’s attack for key recovery. The quantum circuits of these ciphers are implemented using QISKIT, an open-source software development kit (SDK) designed for working with quantum computers running on the IBM Quantum Experience platform.
We study quantum algorithms for multivariate quadratic Boolean equation systems by focusing on their precise gate count. While better asymptotic algorithms are known, currently gate counts were only computed for exhaustive search (Schwabe and Westerbaan, SPACE 2016) and a variant of Grover's search using preprocessing (Pring, WAIFI 2018). This limits the applicability of Boolean equation solving to cryptanalysis, which considers relatively small numbers of variables (from 40 to 200) and is concerned with the exact complexity of the solver. In this paper, we introduce two new quantum algorithms. The first algorithm is an optimized quantum exhaustive search which amortizes the cost of polynomial evaluation at each quantum search iterate. The second algorithm adapts a method of Bouillaguet et al. (SOSA 2022) which proceeds by linearization of the system. In both cases, we implement the quantum circuits, study their complexity, and obtain significant improvements over previous results. Next, we apply these new algorithms to the cryptanalysis of the block ciphers LowMC and RAIN in the single-data setting. By adapting attacks from Liu et al. (ToSC 2022) and Liu et al. (ToSC 2023) we obtain the first quantum cryptanalysis results on these ciphers.
Security vulnerabilities in the symmetric-key primitives of a cipher can undermine the overall security claims of the cipher. With the rapid advancement of quantum computing in recent years, there is an increasing effort to evaluate the security of symmetric-key cryptography against potential quantum attacks. This paper focuses on analyzing the quantum attack resistance of AIM, a symmetric-key primitive used in the AIMer digital signature scheme. We present the first quantum circuit implementation of AIM and estimate its complexity (such as qubit count, gate count, and circuit depth) with respect to Grover’s search algorithm. For Grover’s key search, the most important optimization metric is depth, especially when considering parallel search. Our implementation gathers multiple methods for a low-depth quantum circuit of AIM in order to reduce the Toffoli depth and full depth (such as the Karatsuba multiplication and optimization of inner modules; Mer, LinearLayer).
An efficient quantum implementation of the advanced encryption standard (AES) is crucial for reducing the complexity of implementing an exhaustive key search through Grover’s algorithm. In this paper, we study how to construct resource-efficient quantum circuits for AES. We consider the product of T-gates depth and width (TDW) and the product of full depth and width (FDW) as optimization targets. We propose a generic method, called the controlled control qubit cascade (CCQC) technique, to construct quantum circuits for nonlinear components with reduced TDW and FDW. Using this, we construct a quantum circuit for the AES S-box. Compared with recent work presented at ASIACRYPT 2023, our S-box quantum circuit achieves reductions of 2.3% in TDW and 45.2% in FDW. Additionally, we propose a new key schedule strategy to reduce the full depth of the AES quantum circuit. Finally, the trade-offs between T-gates depth and width and the parallel numbers of S-box and TDW are analyzed.