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

Timo Glaser, Alexander May, Julian Nowakowski · 2025

Read Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys by Timo Glaser, Alexander May, Julian Nowakowski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06549.txt.

Introduction

Guessing secret keys gets a sharper quantum analysis from Timo Glaser and two co-authors in a 2025 cryptography paper. Keys are often unevenly likely, as with passwords or noisy learning problems. Classically, the best attack tries keys from most to least likely, while a quantum method by Montanaro uses Grover-style search.

The authors give the first tight runtime for Montanaro's method, expressed through a Rényi entropy of the key distribution. The key step is an old information-theory inequality that, they note, the cryptography community had missed; it also pins down the classical cost. Because the relevant entropies differ, the quantum gain exceeds the usual quadratic speedup for every uneven distribution. Attacking many keys at once is also analyzed, and there the cost per key drops further, both classically and quantumly.

Catalog record

CREATORTimo Glaser, Alexander May, Julian Nowakowski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-06549

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys Timo Glaser, Alexander May, Julian Nowakowski Abstract We study the fundamental problem of guessing cryptographic keys, drawn from some non-uniform probability distribution 𝒟 \mathcal{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 ⁡ ( 𝒟 ) / 2 2^{\operatorname{H}_{2/3}(\mathcal{D})/2} , where H α ⁡ ( ⋅ ) \operatorname{H}_{\alpha}(\cdot) denotes Renyi entropy with parameter α \alpha . 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 ⁡ ( 𝒟 ) 2^{\operatorname{H}_{1/2}(\mathcal{D})} . Since H 2 / 3 ⁡ ( 𝒟 ) < H 1 / 2 ⁡ ( 𝒟 ) \operatorname{H}_{2/3}(\mathcal{D})<\operatorname{H}_{1/2}(\mathcal{D}) for every non-uniform distribution 𝒟 \mathcal{D} , we thus obtain a super-quadratic quantum speed-up s > 2 s>2 over classical key guessing. To give some numerical examples, for the binomial distribution used in Kyber, and for a typical password distribution, we obtain quantum speed-up s > 2.04 s>2.04 . For the n n -fold Bernoulli distribution with parameter p = 0.1 p=0.1 as in LPN, we obtain s > 2.27 s>2.27 . For small error LPN with p = Θ ( n − 1 / 2 ) p=\Theta(n^{-1/2}) as in Alekhnovich encryption, we even achieve unbounded quantum speedup s = Ω ⁡ ( n 1 / 12 ) s=\Omega(n^{1/12}) . 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 𝒟 \mathcal{D} , and aim to guess a fraction of them. For product distributions 𝒟 = χ n \mathcal{D}=\chi^{n} , we show that any constant fraction of keys can be guessed within 2 H ⁡ ( 𝒟 ) 2^{\operatorname{H}(\mathcal{D})} classically and 2 H ⁡ ( 𝒟 ) / 2 2^{\operatorname{H}(\mathcal{D})/2} quantumly per key, where H ⁡ ( χ ) \operatorname{H}(\chi) denotes Shannon entropy. In contrast, Arikan’s Inequality implies that guessing a single key costs 2 H 1 / 2 ⁡ ( 𝒟 ) 2^{\operatorname{H}_{1/2}(\mathcal{D})} classically and 2 H 2 / 3 ⁡ ( 𝒟 ) / 2 2^{\operatorname{H}_{2/3}(\mathcal{D})/2} quantumly. Since H ⁡ ( 𝒟 ) < H 2 / 3 ⁡ ( 𝒟 ) < H 1 / 2 ⁡ ( 𝒟 ) \operatorname{H}(\mathcal{D})<\operatorname{H}_{2/3}(\mathcal{D})<\operatorname{H}_{1/2}(\mathcal{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. 1 Introduction Key guessing. The most fundamental problem in cryptanalysis is the key guessing problem . Formally, let k\in\mathcal{K} be a cryptographic key sampled from some key space \mathcal{K} , and let \mathbbm{1}_{k}:\mathcal{K}\to\{0,1\} be an oracle with \mathbbm{1}_{k}(x):=\begin{cases}1&\text{if }x=k,\\ 0&\text{else.}\end{cases} The key guessing problem asks to find k , given oracle access to \mathbbm{1}_{k}(\cdot) . The optimal classical algorithm for key guessing is brute force search, i.e., iterating over the key space \mathcal{K} in uniformly random order until one finds k . On expectation, brute force finds k after \Theta(|\mathcal{K}|) steps. The optimal quantum algorithm is Grover search [ Gro96 ] , which achieves a square root speed-up over the classical algorithm, thus solving the key guessing problem in time \Theta(\sqrt{|\mathcal{K}|}) . Key guessing from a distribution. The situation changes if the attacker knows the probability distribution \mathcal{D} of the key k . In that case, the optimal classical algorithm for key guessing is to query \mathbbm{1}_{k}(\cdot) on keys x\in\mathcal{K} in decreasing order of probability. This approach has expected runtime T_{C}(\mathcal{D}):=\sum_{i=1}^{|\mathcal{K}|}i\cdot p_{i}, where p_{i} is the probability of the i -th likeliest key. An information theoretic inequality by Arikan [ Ari96 ] shows \frac{2^{\operatorname{H}_{1/2}(\mathcal{D})}}{1+\log_{2}|\mathcal{K}|}\leq T_{C}(\mathcal{D})\leq 2^{\operatorname{H}_{1/2}(\mathcal{D})} (1) where \operatorname{H}_{1/2}(\mathcal{D}) is the Rényi entropy of the distribution \mathcal{D} with parameter \frac{1}{2} . Notice, if \mathcal{D} is the uniform distribution over \mathcal{K} , then 2^{\operatorname{H}_{1/2}(\mathcal{D})}=|\mathcal{K}| . However, for non-uniform \mathcal{D} , we have 2^{\operatorname{H}_{1/2}(\mathcal{D})}<|\mathcal{K}| . Hence, for \mathcal{D} different from the uniform distribution, enumerating keys in decreasing order of likelihood yields a non-trivial speed-up. 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 p \alpha=\frac{1}{2} \alpha=\frac{2}{3} \alpha=1 (Shannon entropy) \alpha=\text{min} (Min entropy) Figure 1: Rènyi entropy \operatorname{H}_{\alpha}(\text{Ber}(p)) of the Bernoulli distribution \text{Ber}(p) for various \alpha . For instance, suppose that \mathcal{D} is the n -fold Bernoulli distribution \text{Ber}(p)^{n} with parameter p\in(0,1) . That is, \mathcal{D} samples binary strings from \{0,1\}^{n} and sets each bit independently to 1 with probability p . Then |\mathcal{K}|=2^{n},\quad\text{and}\quad 2^{\operatorname{H}_{1/2}(\mathcal{D})}=2^{\operatorname{H}_{1/2}(\text{Ber}(p))n}. As Figure 1 shows, we have \operatorname{H}_{1/2}(\text{Ber}(p))<1 for every p\neq\frac{1}{2} . Hence, for every constant p\neq\frac{1}{2} , enumerating keys in decreasing order of likelihood improves over brute-force by an exponential factor \frac{|\mathcal{K}|}{T_{C}(\mathcal{D})}=\widetilde{\Theta}\left(\frac{2^{n}}{2^{\operatorname{H}_{1/2}(\text{Ber}(p))n}}\right)=2^{\Omega(n)}. On the other hand, if p=\frac{1}{2} , then \text{Ber}(p)^{n} is the uniform distribution over \{0,1\}^{n} , and we do not improve over brute force. Somewhat curiously, Arikan’s result seems to be widely unknown in the cryptographic community. Consider, for instance, the recent line of research on hybrid attacks on lattice-based crypto [ IDF22 , DP23 , AS22 , BM23 ] . Hybrid attacks try to recover a part of the secret key via key guessing, and the remaining part via lattice-based techniques. The cryptographic literature contains the following results for key guessing in hybrid attacks: • Bernstein [ Ber23 ] uses the loose upper bound T_{C}(\mathcal{D})\leq|\mathcal{K}| in the analysis of his hybrid attack. Since for any \mathcal{D} different from the uniform distribution we have 2^{\operatorname{H}_{1/2}(\mathcal{D})}<|\mathcal{K}| , Arikan’s result shows that Bernstein overestimates the runtime of key guessing. • The analysis of MATZOV [ IDF22 ] claims (without proof) that T_{C}(\mathcal{D})=2^{\operatorname{H}(\mathcal{D})} , with \operatorname{H}(\mathcal{D}) the Shannon entropy of \mathcal{D} . Since for non-uniform \mathcal{D} we have 2^{\operatorname{H}_{1/2}(\mathcal{D})}>2^{\operatorname{H}(\mathcal{D})} , it follows from Arikan’s result that MATZOV underestimates the complexity of key guessing. • Independently of Arikan’s result, MATZOV’s inaccuracy has been criticized by follow-up works: Ducas-Pulles [ DP23 ] give counterexample distributions \mathcal{D} for which MATZOV’s claim is wrong. Albrecht-Shen [ AS22 ] try to improve MATZOV’s analysis by computing an upper bound on T_{C}(\mathcal{D}) with discrete Gaussian \mathcal{D} . Budroni-Mårtensson [ BM23 ] give an efficient algorithm that, for certain distributions \mathcal{D} , can compute T_{C}(\mathcal{D}) numerically. Quantum key guessing from a distribution. For the quantum setting, Ambainis and de Wolf [ ADW01 ] were the first to show super-quadratic speed-ups for non-uniform distributions. Montanaro [ Mon11 ] gave an optimal algorithm that, given a distribution \mathcal{D} , solves the key guessing problem in time T_{Q}(\mathcal{D}):=\sum_{i=1}^{|\mathcal{K}|}\sqrt{i}\cdot p_{i}. Let T_{C}(\mathcal{D})=T_{Q}(\mathcal{D})^{s} for some quantum speed-up s . For any distribution \mathcal{D} , we have \displaystyle T_{Q}(\mathcal{D})\leq\sqrt{T_{C}(\mathcal{D})}. (2) Hence, Montanaro’s quantum algorithm obtains a quantum speed-up over the optimal classical algorithm of at least s=\frac{\log T_{C}(\mathcal{D})}{\log T_{Q}(\mathcal{D})}\geq 2. We call a speed-up with s=2 quadratic , s>2 super-quadratic , s=\Theta(1) polynomial , s=\omega(1) super-polynomial , and with s=\Theta(n) exponential . Montanaro showed that there exist probability distributions for which Equation 2 is strict, i.e., T_{Q}(\mathcal{D})<\sqrt{T_{C}(\mathcal{D})} , achieving a super-quadratic speed-up. However, these distributions

Read the complete text