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

Quantum-Aware Key Rank for Side-Channel Attacks evaluation

Yevgen Kotukh

quant-phcs.CRSubmitted Oct 14, 2026• Announced Oct 15, 2026• 0 citations
arXivHTMLPDF

Abstract

Side-channel attacks on block ciphers rarely recover the key outright: they leave a residual key space ordered by subkey posteriors, and evaluation laboratories report the key rank of the true key against thresholds near 2^48 and 2^60. No evaluation framework models an adversary who collects traces classically and finishes the search on a quantum computer, although quantum search with advice provides exactly that. We give such an adversary a cost model and a metric. For a device whose key has rank r, any quantum algorithm with classical access to the posteriors needs Omega(sqrt(r)) cipher evaluations, and block search achieves O(sqrt(r)); the per-instance advantage is exactly quadratic, and the super-quadratic exponents reported for search with advice are averages over the prior that apply to no single device. Under the NIST MAXDEPTH budget D and a Grover iteration of g gates and depth d, the quadratic advantage holds only for ranks up to (4D/(pi d))^2 and collapses to a constant factor beyond; with the best published AES-128 oracle and D = 2^40 the window closes near rank 2^58.6. We define the quantum-aware key rank, the classical rank of equal cost, computable from the rank estimators laboratories already run, and derive the classical rank a device must retain to keep a given threshold against each depth budget. Block search and amplitude amplification from the product-form posterior state are within a factor of two to four of each other on Hamming-weight posteriors, so the cost of coherent indexing decides between them. Experiments on simulated leakage and a toy cipher confirm the predicted window: at SNR 0.125 a depth-limited quantum adversary is worth about 22 traces to a classical one, however large its gate budget.

AI Summary

Side-channel evaluations typically leave a ranked residual key space rather than recover a cipher key outright, with classical security thresholds around $2^{48}$–$2^{60}$. This paper asks how those evaluations change when an adversary collects leakage classically and completes key search on a quantum computer. It introduces a cost model and a “quantum-aware key rank”: the classical rank requiring equivalent search cost. For a true key of rank $r$, it states an $\Omega(\sqrt r)$ cipher-evaluation lower bound for quantum algorithms with classical access to the posterior information, matched by block search in $O(\sqrt r)$. It distinguishes this per-instance quadratic scaling from super-quadratic exponents obtained by averaging search-with-advice costs over a prior. With maximum circuit depth $D$ and Grover-iteration depth $d$, the quadratic regime extends only to $r\leq(4D/(\pi d))^2$; beyond it, the advantage becomes a constant factor. Using the best published AES-128 oracle and $D=2^{40}$ gives a boundary near $2^{58.6}$. The proposed metric is computable from existing rank estimators and translates classical security thresholds into depth-dependent requirements. For Hamming-weight posteriors, block search and amplitude amplification from a product-form posterior state have costs within factors of two to four, leaving coherent-indexing costs decisive. Simulated leakage and toy-cipher experiments support the predicted depth window; at SNR $0.125$, the depth-limited quantum advantage corresponds to about 22 classical traces, regardless of gate budget. These experimental checks are limited to simulations and a toy cipher; the AES boundary depends on the chosen oracle and depth budget.

No sign of AI-generated textIncrementalStrong assumptionsOverclaims

Written by gpt-6.1-sol from the abstract only. Automated: it can be wrong.

Related papers

Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice

Carsten Schubert, Niklas Paskarbeit, Maximilian J. Kramer +2 more

In cryptanalysis and beyond, presumably the most basic problem is search within an unstructured space: Given a finite set of elements K, find a marked element using an efficiently evaluable predicate. Grover's algorithm [16] gives an optimal quadratic query advantage for black-box search. Cryptanalytic settings, however, often come with additional probabilistic advice over the candidate space. These distributions frequently have product form, e.g. when probabilities for independent key coordinates are derived from side-channel leakage. Classically, simply querying the predicate function in the given likelihood order is optimal to find the correct result as fast as possible in expectation. In the quantum setting, Montanaro [26] showed how to achieve an optimal expected query complexity, beating plain Grover on every non-uniform distribution of the advice (disregarding a constant overhead factor). What has been missing so far is a finite-size method for evaluating the quantum-classical guessing-moment separation induced by a given advice distribution. We provide such a method for product-distribution advice, thereby sharpening the previous entropy-based estimate of Bashiri et al. [6]. Our approach reduces the relevant classical and quantum guessing moments to functionals of the one-dimensional surprisal distribution. For product advice, this distribution is obtained by convolving the per-coordinate surprisal laws. When the surprisals lie on a common arithmetic grid—the commensurate case—the resulting logarithmic moments, and hence the speedup exponent, can be evaluated as finite sums without discretization error. Exponential tilting makes this computation numerically stable. For general non-commensurate product advice, we discretize the surprisals onto a common grid before running our algorithm and derive an a-posteriori bound on the resulting binning error. We apply the framework to cold-boot leakage on seeds and block-cipher keys, to template-attack posteriors, and to synthetic i.i.d. Bernoulli posteriors whose parameter is chosen to reproduce average residual ranks reported for Keccak side-channel attacks on ML-KEM and ML-DSA. The resulting guessing-moment exponents substantially exceed 2 in several skewed-advice settings, reaching 3.92 for cold-boot advice and 3.12 in the synthetic models, and include cases where the previous entropy-based bound did not establish an exponent above 2.

arXiv:2609.28226•ACM Conference on Post-Quantum and Quantum-based Security•Oct 26, 2026•1 citation

Quantum Key Search Algorithms under Side-channel Attack

Yunteng Yang, Jianhong Shi, Hailong Zhang +5 more

Abstract It is assumed that the attacker obtains an error-containing noisy key through side-channel attacks, and the probability distribution of the key space follows a \((n)\)-fold Bernoulli distribution. We investigate the key search problem of cryptographic algorithms in the scenario of side-channel attacks. The main contributions of this study are summarized as follows: First, the computational complexity of the classical key search algorithm in the scenario of side-channel attacks is derived. Second, a quantum key search algorithm is designed based on Grover’s algorithm and Montanaro's algorithm. By leveraging the \((n)\)-fold Bernoulli distribution, the key space partition strategy is determined, different from Montanaro's algorithm, thus developing an improved quantum key search algorithm; the computational complexity of this improved algorithm is further analyzed. Simulation results show that the proposed quantum key search algorithm can achieve a super-quadratic speedup over the classical counterpart under side-channel attack conditions. Taking a 256-bit cryptographic key as an example (1% BER), the query complexity decreases from \((2^{256})\) for the conventional classical algorithm to \((2^{62.29})\) with side-channel attacks, and is further reduced from Glaser's \((2^{21.59})\) to \((2^{19.77})\) by our quantum algorithm. Correspondingly, the speedup factor of the proposed quantum algorithm relative to the classical algorithm under side-channel attack conditions reaches 3.15, while the speedup factor reported by Glaser is only 2.73 under the same conditions. Third, to address the difficulty of input state preparation in the our quantum algorithm, we transform the problem of input state preparation into the preparation of the Dicke state. The Dicke state can be implemented by \((O(nd))\) CNOT gates with \((O\left(d \log \frac{n}{d}\right))\) circuit depth for ion trap topology (or \((O\left(\sqrt{nd}\right))\) circuit depth for superconducting topology) in short-depth quantum circuits, and the input state of our algorithm only need to add \((O(d))\) \((X)\)-gates based on the Dicke state.

•Aug 12, 2026•0 citations

Q-LEAK: Quantum-Based LEAKage Verification for Side-Channel Countermeasures

Walid El Maouaki, Alberto Marchisio, Muhammad Shafique

Formal verification of power side-channel leakage and its countermeasures in cryptographic algorithms is challenging, as SAT-based methods fail to scale on XOR-heavy, time-unrolled cryptographic circuits with realistic leakage models. We construct compact Conjunctive Normal Form (CNF) cases modeling one-bit leakage under two-trace conditions, linking key dependence and state evolution. Classical solvers quickly reach complexity limits, so we propose Q-LEAK, a quantum-based verification approach using Grover's algorithm, compiling each CNF into an oracle and applying amplitude amplification to search in O(sqrt(N)) oracle calls, with oracles that encode the two-trace leakage predicate and the CNF constraints. Benchmarking against classical SAT shows both potential gains and practical resource limits. In noiseless tests on 5-7 variable benchmarks, Q-LEAK consistently recovered a satisfying assignment within 1-4 tries, with marked bitstrings amplified clearly above the background distribution, exceeding 20 percent probability. The evaluation of Q-LEAK on real quantum hardware revealed at least one classically verified SAT assignment, despite the presence of noise. These results point to a potential path toward quantum-assisted verification of side-channel protections.

quant-pharXiv:2605.25728•May 26, 2026•0 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•17 citations

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•1 citation

Quantum exhaustive key search with simplified-DES as a case study

Mishal Almazrooie, Azman Samsudin, Rosni Abdullah +1 more

To evaluate the security of a symmetric cryptosystem against any quantum attack, the symmetric algorithm must be first implemented on a quantum platform. In this study, a quantum implementation of a classical block cipher is presented. A quantum circuit for a classical block cipher of a polynomial size of quantum gates is proposed. The entire work has been tested on a quantum mechanics simulator called libquantum. First, the functionality of the proposed quantum cipher is verified and the experimental results are compared with those of the original classical version. Then, quantum attacks are conducted by using Grover's algorithm to recover the secret key. The proposed quantum cipher is used as a black box for the quantum search. The quantum oracle is then queried over the produced ciphertext to mark the quantum state, which consists of plaintext and key qubits. The experimental results show that for a key of n-bit size and key space of N such that [Formula: see text], the key can be recovered in [Formula: see text] computational steps.

SpringerPlus•Sep 6, 2016•11 citations
Side-channel attacks on block ciphers rarely recover the key outright: they leave a residual key space ordered by subkey posteriors, and evaluation laboratories report the key rank of the true key against thresholds near 2^48 and 2^60. No evaluation framework models an adversary who collects traces classically and finishes the search on a quantum computer, although quantum search with advice provides exactly that. We give such an adversary a cost model and a metric. For a device whose key has rank r, any quantum algorithm with classical access to the posteriors needs Omega(sqrt(r)) cipher evaluations, and block search achieves O(sqrt(r)); the per-instance advantage is exactly quadratic, and the super-quadratic exponents reported for search with advice are averages over the prior that apply to no single device. Under the NIST MAXDEPTH budget D and a Grover iteration of g gates and depth d, the quadratic advantage holds only for ranks up to (4D/(pi d))^2 and collapses to a constant factor beyond; with the best published AES-128 oracle and D = 2^40 the window closes near rank 2^58.6. We define the quantum-aware key rank, the classical rank of equal cost, computable from the rank estimators laboratories already run, and derive the classical rank a device must retain to keep a given threshold against each depth budget. Block search and amplitude amplification from the product-form posterior state are within a factor of two to four of each other on Hamming-weight posteriors, so the cost of coherent indexing decides between them. Experiments on simulated leakage and a toy cipher confirm the predicted window: at SNR 0.125 a depth-limited quantum adversary is worth about 22 traces to a classical one, however large its gate budget.
Side-channel evaluations typically leave a ranked residual key space rather than recover a cipher key outright, with classical security thresholds around 2482^{48}248–2602^{60}260. This paper asks how those evaluations change when an adversary collects leakage classically and completes key search on a quantum computer.
It introduces a cost model and a “quantum-aware key rank”: the classical rank requiring equivalent search cost. For a true key of rank rrr, it states an Ω(r)\Omega(\sqrt r)Ω(r​) cipher-evaluation lower bound for quantum algorithms with classical access to the posterior information, matched by block search in O(r)O(\sqrt r)O(r​). It distinguishes this per-instance quadratic scaling from super-quadratic exponents obtained by averaging search-with-advice costs over a prior.
With maximum circuit depth DDD and Grover-iteration depth ddd, the quadratic regime extends only to r≤(4D/(πd))2r\leq(4D/(\pi d))^2r≤(4D/(πd))2; beyond it, the advantage becomes a constant factor. Using the best published AES-128 oracle and D=240D=2^{40}D=240 gives a boundary near 258.62^{58.6}258.6. The proposed metric is computable from existing rank estimators and translates classical security thresholds into depth-dependent requirements.
For Hamming-weight posteriors, block search and amplitude amplification from a product-form posterior state have costs within factors of two to four, leaving coherent-indexing costs decisive. Simulated leakage and toy-cipher experiments support the predicted depth window; at SNR 0.1250.1250.125, the depth-limited quantum advantage corresponds to about 22 classical traces, regardless of gate budget. These experimental checks are limited to simulations and a toy cipher; the AES boundary depends on the chosen oracle and depth budget.
In cryptanalysis and beyond, presumably the most basic problem is search within an unstructured space: Given a finite set of elements K, find a marked element using an efficiently evaluable predicate. Grover's algorithm [16] gives an optimal quadratic query advantage for black-box search. Cryptanalytic settings, however, often come with additional probabilistic advice over the candidate space. These distributions frequently have product form, e.g. when probabilities for independent key coordinates are derived from side-channel leakage. Classically, simply querying the predicate function in the given likelihood order is optimal to find the correct result as fast as possible in expectation. In the quantum setting, Montanaro [26] showed how to achieve an optimal expected query complexity, beating plain Grover on every non-uniform distribution of the advice (disregarding a constant overhead factor). What has been missing so far is a finite-size method for evaluating the quantum-classical guessing-moment separation induced by a given advice distribution. We provide such a method for product-distribution advice, thereby sharpening the previous entropy-based estimate of Bashiri et al. [6]. Our approach reduces the relevant classical and quantum guessing moments to functionals of the one-dimensional surprisal distribution. For product advice, this distribution is obtained by convolving the per-coordinate surprisal laws. When the surprisals lie on a common arithmetic grid—the commensurate case—the resulting logarithmic moments, and hence the speedup exponent, can be evaluated as finite sums without discretization error. Exponential tilting makes this computation numerically stable. For general non-commensurate product advice, we discretize the surprisals onto a common grid before running our algorithm and derive an a-posteriori bound on the resulting binning error. We apply the framework to cold-boot leakage on seeds and block-cipher keys, to template-attack posteriors, and to synthetic i.i.d. Bernoulli posteriors whose parameter is chosen to reproduce average residual ranks reported for Keccak side-channel attacks on ML-KEM and ML-DSA. The resulting guessing-moment exponents substantially exceed 2 in several skewed-advice settings, reaching 3.92 for cold-boot advice and 3.12 in the synthetic models, and include cases where the previous entropy-based bound did not establish an exponent above 2.
Abstract It is assumed that the attacker obtains an error-containing noisy key through side-channel attacks, and the probability distribution of the key space follows a (n)(n)(n)-fold Bernoulli distribution. We investigate the key search problem of cryptographic algorithms in the scenario of side-channel attacks. The main contributions of this study are summarized as follows: First, the computational complexity of the classical key search algorithm in the scenario of side-channel attacks is derived. Second, a quantum key search algorithm is designed based on Grover’s algorithm and Montanaro's algorithm. By leveraging the (n)(n)(n)-fold Bernoulli distribution, the key space partition strategy is determined, different from Montanaro's algorithm, thus developing an improved quantum key search algorithm; the computational complexity of this improved algorithm is further analyzed. Simulation results show that the proposed quantum key search algorithm can achieve a super-quadratic speedup over the classical counterpart under side-channel attack conditions. Taking a 256-bit cryptographic key as an example (1% BER), the query complexity decreases from (2256)(2^{256})(2256) for the conventional classical algorithm to (262.29)(2^{62.29})(262.29) with side-channel attacks, and is further reduced from Glaser's (221.59)(2^{21.59})(221.59) to (219.77)(2^{19.77})(219.77) by our quantum algorithm. Correspondingly, the speedup factor of the proposed quantum algorithm relative to the classical algorithm under side-channel attack conditions reaches 3.15, while the speedup factor reported by Glaser is only 2.73 under the same conditions. Third, to address the difficulty of input state preparation in the our quantum algorithm, we transform the problem of input state preparation into the preparation of the Dicke state. The Dicke state can be implemented by (O(nd))(O(nd))(O(nd)) CNOT gates with (O(dlog⁡nd))(O\left(d \log \frac{n}{d}\right))(O(dlogdn​)) circuit depth for ion trap topology (or (O(nd))(O\left(\sqrt{nd}\right))(O(nd​)) circuit depth for superconducting topology) in short-depth quantum circuits, and the input state of our algorithm only need to add (O(d))(O(d))(O(d)) (X)(X)(X)-gates based on the Dicke state.
Formal verification of power side-channel leakage and its countermeasures in cryptographic algorithms is challenging, as SAT-based methods fail to scale on XOR-heavy, time-unrolled cryptographic circuits with realistic leakage models. We construct compact Conjunctive Normal Form (CNF) cases modeling one-bit leakage under two-trace conditions, linking key dependence and state evolution. Classical solvers quickly reach complexity limits, so we propose Q-LEAK, a quantum-based verification approach using Grover's algorithm, compiling each CNF into an oracle and applying amplitude amplification to search in O(sqrt(N)) oracle calls, with oracles that encode the two-trace leakage predicate and the CNF constraints. Benchmarking against classical SAT shows both potential gains and practical resource limits. In noiseless tests on 5-7 variable benchmarks, Q-LEAK consistently recovered a satisfying assignment within 1-4 tries, with marked bitstrings amplified clearly above the background distribution, exceeding 20 percent probability. The evaluation of Q-LEAK on real quantum hardware revealed at least one classically verified SAT assignment, despite the presence of noise. These results point to a potential path toward quantum-assisted verification of side-channel protections.
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.
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.
To evaluate the security of a symmetric cryptosystem against any quantum attack, the symmetric algorithm must be first implemented on a quantum platform. In this study, a quantum implementation of a classical block cipher is presented. A quantum circuit for a classical block cipher of a polynomial size of quantum gates is proposed. The entire work has been tested on a quantum mechanics simulator called libquantum. First, the functionality of the proposed quantum cipher is verified and the experimental results are compared with those of the original classical version. Then, quantum attacks are conducted by using Grover's algorithm to recover the secret key. The proposed quantum cipher is used as a black box for the quantum search. The quantum oracle is then queried over the produced ciphertext to mark the quantum state, which consists of plaintext and key qubits. The experimental results show that for a key of n-bit size and key space of N such that [Formula: see text], the key can be recovered in [Formula: see text] computational steps.