Mon, 01 Sep 2025

In this talk, we consider the fundamental problem of guessing cryptographic keys, drawn from some distribution $\mathcal{D}$. 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}(\mathcal{D})/2}$, where $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}(\mathcal{D})}$.

Since $H_{2/3}(\mathcal{D}) < H_{1/2}(\mathcal{D})$ for every non-uniform distribution $\mathcal{D}$, we thus obtain a super-quadratic quantum speed-up $s>2$ over classical key guessing. To give some numerical examples, for the binomial distribution used in Kyber, we obtain quantum speed-up $s>2.04$. For $n$-dimensional small error LPN keys, we achieve unbounded quantum speedup $s = \Omega(n^{1/12})$.

Additionally, 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 $\mathcal{D} = \chi^n$, we show that any constant fraction of keys can be guessed within $2^{H(\mathcal{D})}$ classically and $2 ^{H(\mathcal{D})/2}$ quantumly per key, where $H(\chi)$ denotes Shannon entropy. In contrast, Arikan's Inequality implies that guessing a single key costs $2^{H_{1/2}(\mathcal{D})}$ classically and $2^{H_{2/3}(\mathcal{D})/2}$ quantumly. Since $H(\mathcal{D}) < H_{2/3}(\mathcal{D}) < 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.