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

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α(•) 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. 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 = Θ(n -1/2 ) as in Alekhnovich encryption, we even achieve unbounded quantum speedup s = Ω(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 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.