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

Timo Glaser, Alexander May, Julian Nowakowski

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 classic…