Paper 2023/797

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

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^{\operatorname{H}_{2/3}(\mathcal D)/2}$, where $\operatorname{H}_{\alpha}(\cdot)$ denotes Rényi 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^{\operatorname{H}_{1/2}(\mathcal D)}$. Since $\operatorname{H}_{2/3}(\mathcal D) < \operatorname{H}_{1/2}(\mathcal D)$ for every non-uniform distribution $\mathcal D$, we thus obtain a \emph{super-quadratic} quantum speed-up $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$. For the $n$-fold Bernoulli distribution with parameter $p=0.1$ as in LPN, we obtain $s > 2.27$. For small error LPN with $p=\Theta(n^{-1/2})$ as in Alekhnovich encryption, we even achieve \emph{unbounded} quantum speedup $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 $\mathcal D = \chi^n$, we show that any constant fraction of keys can be guessed within $2^{\operatorname{H}(\mathcal D)}$ classically and $2 ^{\operatorname{H}(\mathcal D)/2}$ quantumly per key, where $\operatorname{H}(\chi)$ denotes Shannon entropy. In contrast, Arikan's Inequality implies that guessing a single key costs $2^{\operatorname{H}_{1/2}(\mathcal D)}$ classically and $2^{\operatorname{H}_{2/3}(\mathcal D)/2}$ quantumly. Since $\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.