Entropy Suffices for Guessing Most Keys

摘要: Historically, most cryptosystems chose their keys uniformly at random. This is in contrast to modern (lattice-based) schemes, which typically sample their keys from more complex distributions , such as the discrete Gaussian or centered binomial distribution. It is well-known that any key drawn from the uniform distribution can be guessed using at most key guesses, where denotes the entropy of the uniform distribution. However, for keys drawn from general distributions only a lower bound of key guesses is known. In fact, Massey (1994) even ruled out that the number of key guesses can be upper bounded by a function of the entropy alone. When analyzing the complexity of so-called hybrid lattice-attacks (which combine lattice reduction with key guessing) one therefore usually conservatively underestimates the complexity of key guessing by . However, a tight complexity analysis is missing, and due to Massey's result considered impossible. In this work, we bypass Massey's impossibility result by focusing on the typical cryptographic setting, where keys are drawn from -fold product distributions . It is well known that the optimal key guessing algorithm enumerates keys in in descending order of probability. In order to provide a refined analysis, we allow to abort enumeration after a certain amount of key guesses. As our main result, we prove that for any discrete probability distribution the key guessing algorithm that we abort after keys has asymptotically success probability , taken over the random key choice. The aborted algorithm allows for a quantum version with success probability within key …