  A password composition policy restricts the space of allowable passwords to
eliminate weak passwords that are vulnerable to statistical guessing attacks.
Usability studies have demonstrated that existing password composition policies
can sometimes result in weaker password distributions; hence a more principled
approach is needed. We introduce the first theoretical model for optimizing
password composition policies. We study the computational and sample complexity
of this problem under different assumptions on the structure of policies and on
users' preferences over passwords. Our main positive result is an algorithm
that -- with high probability --- constructs almost optimal policies (which are
specified as a union of subsets of allowed passwords), and requires only a
small number of samples of users' preferred passwords. We complement our
theoretical results with simulations using a real-world dataset of 32 million
passwords.
