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 $$, where $$ denotes Rényi 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 $$. Since $$ for every non-uniform distribution $$, we thus obtain a \emph{super-quadratic} quantum speed-up $$ 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 $$. For the $$-fold Bernoulli distribution with parameter $$ as in LPN, we obtain $$. For small error LPN with $$ as in Alekhnovich encryption, we even achieve \emph{unbounded} quantum speedup $$. 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 $$, and aim to guess a fraction of them. For product distributions $$, we show that any constant fraction of keys can be guessed within $$ classically and $$ quantumly per key, where $$ denotes Shannon entropy. In contrast, Arikan's Inequality implies that guessing a single key costs $$ classically and $$ quantumly. Since $$, 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.