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 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^{\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 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=\varTheta (n^{-1/2})\) as in Alekhnovich encryption, we even achieve unbounded quantum speedup \(s = \varOmega (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 a one-out-of-m setting, we obtain \(2^{\operatorname {H}_{1-{1}/{(m+1)}}(\mathcal {D})}\) classically and \(2^{\operatorname {H}_{1-{1}/{(2m+1)}}(\mathcal {D})/2}\) quantumly. Moreover, 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.