Guesswork

The security of systems is often predicated on a user or application selecting an object, a password or key, from a large list. If an inquisitor wishing to identify the object in order to gain access to a system can only query each possibility, one at a time, then the number of guesses they must make in order to identify the selected object is likely to be large. If the object is selected uniformly at random using, for example, a cryptographically secure pseudo-random number generator, then the analysis of the distribution of the number of guesses that the inquisitor must make is trivial. If the object has not been selected perfectly uniformly, but with a distribution that is known to the inquisitor, then the quantification of security is relatively involved. This thesis contains contributions to the study of this subject, dubbed Guesswork, motivated both by fundamental investigations into computational security as well as modern applications in secure storage and communication. This thesis begins with two introductory chapters. One describes existing results in Guesswork and summarizes the contributions found in the thesis. The other recapitulates some of the mathematical tools that are employed in the thesis. The other five chapters of contain new contributions to our understanding of Guesswork, much of which has already experienced peer review and been published. The chapters themselves are designed to be self-contained and so readable in isolation