Abstract
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. 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 = χⁿ, 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.