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

Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys

Glaser, Timo, Alexander May, Nowakowski, Julian

Published Sep 8, 2025• 0 citations
arXivHTMLPDF

Abstract

We study the fundamental problem of guessing cryptographic keys, drawn from some non-uniform probability distribution $D$, as e.g. in LPN, LWE or for passwords. The optimal classical algorithm enumerates keys in decreasing order of likelihood. The optimal quantum algorithm, due to Montanaro (2011), is a sophisticated Grover search. We give the first tight analysis for Montanaro's algorithm, showing that its runtime is $2^{H_{2/3}(D)/2}$, where $H_α(\cdot)$ denotes Renyi entropy with parameter $α$. Interestingly, this is a direct consequence of an information theoretic result called Arikan's Inequality (1996) -- which has so far been missed in the cryptographic community -- that tightly bounds the runtime of classical key guessing by $2^{H_{1/2}(D)}$. Since $H_{2/3}(D) < H_{1/2}(D)$ for every non-uniform distribution $D$, we thus obtain a super-quadratic quantum speed-up $s>2$ over classical key guessing. As another main result, we provide the first thorough analysis of guessing in a multi-key setting. Specifically, we consider the task of attacking many keys sampled independently from some distribution $D$, and aim to guess a fraction of them. For product distributions $D = χ^n$, we show that any constant fraction of keys can be guessed within $2^{H(D)}$ classically and $2 ^{H(D)/2}$ quantumly per key, where $H(χ)$ denotes Shannon entropy. In contrast, Arikan's Inequality implies that guessing a single key costs $2^{H_{1/2}(D)}$ classically and $2^{H_{2/3}(D)/2}$ quantumly. Since $H(D) < H_{2/3}(D) < H_{1/2}(D)$, this shows that in a multi-key setting the guessing cost per key is substantially smaller than in a single-key setting, both classically and quantumly.

DOI
10.48550/arxiv.2509.06549

Related papers

Pinpointing Super-Quadratic Quantum Enumeration Speedups

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•0 citations

Quantum Query Complexity of Entropy Estimation

Tongyang Li, Xiaodi Wu

Estimation of Shannon and Rényi entropies of unknown discrete distributions is a fundamental problem in statistical property testing. In this paper, we give the first quantum algorithms for estimating α-Rényi entropies (Shannon entropy being 1-Rényi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for α-Rényi entropy estimation for all α ≥ 0 values, including tight bounds for the Shannon entropy, the Hartley entropy (α = 0), and the collision entropy (α = 2). We also provide quantum upper bounds for estimating min-entropy (α = +∞) as well as the Kullback-Leibler divergence. We complement our results with quantum lower bounds on α-Rényi entropy estimation for all α ≥ 0 values. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH); however, with many new technical ingredients: 1) we improve the error dependence of the BHH framework by a fine-tuned error analysis together with Montanaro's approach to estimating the expected output of quantum subroutines for α = 0, 1; 2) we develop a procedure, similar to cooling schedules in simulated annealing, for general α ≥ 0, and 3) in the cases of integer α ≥ 2 and α = +∞, we reduce the entropy estimation problem to the α-distinctness and [log n]-distinctness problems, respectively.

IEEE Transactions on Information Theory•Nov 26, 2018•43 citations

Quantum Search With Generalized Wildcards

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro +2 more

In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string $x \in \{-1,1\}^n$. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost $O(\sqrt{n} \log n)$ and a near-matching lower bound of $Ω(\sqrt{n})$. Belovs [Comput.~Comp.'15] subsequently showed a tight $O(\sqrt{n})$ upper bound. We consider a natural generalization of this problem, parametrized by a subset $\cal{Q} \subseteq 2^{[n]}$, where an algorithm may test whether $x_S = b$ for an arbitrary $S \in \cal{Q}$ and $b \in \{-1,1\}^S$ of its choice, at unit cost. We show near-tight bounds when $\cal{Q}$ is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning $x$ is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions $f : \{-1,1\}^n \to \mathbb{R}$ the ratio of the maximum value of $f$ to the maximum (over $T \in \cal{Q}$) standard deviation of $f$ on a subcube whose free variables are exactly $T$.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.

quant-pharXiv:2511.04669•Leibniz international proceedings in informatics•Nov 7, 2025•0 citations

Informed guessing of an eavesdropper's Renyi entropy

John M. Myers, Tai Tsun Wu

Users of a quantum cryptographic system face a problem of deciding on the ignorance of a maximally adroit eavesdropper concerning their key material. It is known that there can be no sure, positive, lower bound on any plausible measure of ignorance, and for this reason we characterize the problem as the making of an informed guess, meaning a guess that employs a rule that can be shown to work except in unlikely cases. As the measure of an eavesdropper's ignorance concerning n bits of sifted key material less some number k of bits found in error and discarded, we analyze Renyi entropy of arbitrary order R, for 1 ≤ R ≤ 2. We offer a rule for deciding on Renyi entropy based on a tighter bound on the relevant probability distributions than has been available. To this end, we employ a recently derived approximation to the cumulative binomial distribution which is uniformly accurate over a larger domain than previously available approximations. This results in a longer distilled key than that obtained from looser bounds, as well as generalizing the order R. Some numerical examples are presented.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 5, 2003•0 citations

Min-entropy and quantum key distribution: Nonzero key rates for “small” numbers of signals

Sylvia Bratzik, Markus Mertz, Hermann Kampermann +1 more

We calculate an achievable secret key rate for quantum key distribution with a finite number of signals by evaluating the quantum conditional min-entropy explicitly. The min-entropy for a classical random variable is the negative logarithm of the maximal value in its probability distribution. The quantum conditional min-entropy can be expressed in terms of the guessing probability, which we calculate for $d$-dimensional systems. We compare these key rates to previous approaches using the von Neumann entropy and find nonzero key rates for a smaller number of signals. Furthermore, we improve the secret key rates by modifying the parameter estimation step. Both improvements taken together lead to nonzero key rates for only ${10}^{4}$--${10}^{5}$ signals. An interesting conclusion can also be drawn from the additivity of the min-entropy and its relation to the guessing probability: for a set of symmetric tensor product states, the optimal minimum-error discrimination (MED) measurement is the optimal MED measurement on each subsystem.

arXiv:1011.1190•Physical Review A•Feb 28, 2011•26 citations

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
We study the fundamental problem of guessing cryptographic keys, drawn from some non-uniform probability distribution DDD, as e.g. in LPN, LWE or for passwords. The optimal classical algorithm enumerates keys in decreasing order of likelihood. The optimal quantum algorithm, due to Montanaro (2011), is a sophisticated Grover search. We give the first tight analysis for Montanaro's algorithm, showing that its runtime is 2H2/3(D)/22^{H_{2/3}(D)/2}2H2/3​(D)/2, where Hα(⋅)H_α(\cdot)Hα​(⋅) denotes Renyi entropy with parameter ααα. Interestingly, this is a direct consequence of an information theoretic result called Arikan's Inequality (1996) -- which has so far been missed in the cryptographic community -- that tightly bounds the runtime of classical key guessing by 2H1/2(D)2^{H_{1/2}(D)}2H1/2​(D). Since H2/3(D)<H1/2(D)H_{2/3}(D) < H_{1/2}(D)H2/3​(D)<H1/2​(D) for every non-uniform distribution DDD, we thus obtain a super-quadratic quantum speed-up s>2s>2s>2 over classical key guessing. As another main result, we provide the first thorough analysis of guessing in a multi-key setting. Specifically, we consider the task of attacking many keys sampled independently from some distribution DDD, and aim to guess a fraction of them. For product distributions D=χnD = χ^nD=χn, we show that any constant fraction of keys can be guessed within 2H(D)2^{H(D)}2H(D) classically and 2H(D)/22 ^{H(D)/2}2H(D)/2 quantumly per key, where H(χ)H(χ)H(χ) denotes Shannon entropy. In contrast, Arikan's Inequality implies that guessing a single key costs 2H1/2(D)2^{H_{1/2}(D)}2H1/2​(D) classically and 2H2/3(D)/22^{H_{2/3}(D)/2}2H2/3​(D)/2 quantumly. Since H(D)<H2/3(D)<H1/2(D)H(D) < H_{2/3}(D) < H_{1/2}(D)H(D)<H2/3​(D)<H1/2​(D), this shows that in a multi-key setting the guessing cost per key is substantially smaller than in a single-key setting, both classically and quantumly.
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.
Estimation of Shannon and Rényi entropies of unknown discrete distributions is a fundamental problem in statistical property testing. In this paper, we give the first quantum algorithms for estimating α-Rényi entropies (Shannon entropy being 1-Rényi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for α-Rényi entropy estimation for all α ≥ 0 values, including tight bounds for the Shannon entropy, the Hartley entropy (α = 0), and the collision entropy (α = 2). We also provide quantum upper bounds for estimating min-entropy (α = +∞) as well as the Kullback-Leibler divergence. We complement our results with quantum lower bounds on α-Rényi entropy estimation for all α ≥ 0 values. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH); however, with many new technical ingredients: 1) we improve the error dependence of the BHH framework by a fine-tuned error analysis together with Montanaro's approach to estimating the expected output of quantum subroutines for α = 0, 1; 2) we develop a procedure, similar to cooling schedules in simulated annealing, for general α ≥ 0, and 3) in the cases of integer α ≥ 2 and α = +∞, we reduce the entropy estimation problem to the α-distinctness and [log n]-distinctness problems, respectively.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}nx \in \{-1,1\}^nx∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlog⁡n)O(\sqrt{n} \log n)O(n​logn) and a near-matching lower bound of Ω(n)Ω(\sqrt{n})Ω(n​). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n)O(\sqrt{n})O(n​) upper bound. We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n]\cal{Q} \subseteq 2^{[n]}Q⊆2[n], where an algorithm may test whether xS=bx_S = bxS​=b for an arbitrary S∈QS \in \cal{Q}S∈Q and b∈{−1,1}Sb \in \{-1,1\}^Sb∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q\cal{Q}Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning xxx is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→Rf : \{-1,1\}^n \to \mathbb{R}f:{−1,1}n→R the ratio of the maximum value of fff to the maximum (over T∈QT \in \cal{Q}T∈Q) standard deviation of fff on a subcube whose free variables are exactly TTT.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
Users of a quantum cryptographic system face a problem of deciding on the ignorance of a maximally adroit eavesdropper concerning their key material. It is known that there can be no sure, positive, lower bound on any plausible measure of ignorance, and for this reason we characterize the problem as the making of an informed guess, meaning a guess that employs a rule that can be shown to work except in unlikely cases. As the measure of an eavesdropper's ignorance concerning n bits of sifted key material less some number k of bits found in error and discarded, we analyze Renyi entropy of arbitrary order R, for 1 ≤ R ≤ 2. We offer a rule for deciding on Renyi entropy based on a tighter bound on the relevant probability distributions than has been available. To this end, we employ a recently derived approximation to the cumulative binomial distribution which is uniformly accurate over a larger domain than previously available approximations. This results in a longer distilled key than that obtained from looser bounds, as well as generalizing the order R. Some numerical examples are presented.
We calculate an achievable secret key rate for quantum key distribution with a finite number of signals by evaluating the quantum conditional min-entropy explicitly. The min-entropy for a classical random variable is the negative logarithm of the maximal value in its probability distribution. The quantum conditional min-entropy can be expressed in terms of the guessing probability, which we calculate for ddd-dimensional systems. We compare these key rates to previous approaches using the von Neumann entropy and find nonzero key rates for a smaller number of signals. Furthermore, we improve the secret key rates by modifying the parameter estimation step. Both improvements taken together lead to nonzero key rates for only 104{10}^{4}104--105{10}^{5}105 signals. An interesting conclusion can also be drawn from the additivity of the min-entropy and its relation to the guessing probability: for a set of symmetric tensor product states, the optimal minimum-error discrimination (MED) measurement is the optimal MED measurement on each subsystem.
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.