Abstract or Summary:
Secure cryptographic protocols to authenticate humans typically assume that the human will receive assistance from trusted hardware or software. One interesting challenge for the cryptography community is to build authentication protocols that are so simple that a human can execute them without relying on assistance from a trusted computer. We propose several candidate human authentication protocols in a setting in which the user can only receive assistance from a semi-trusted computer --- a computer that can be trusted to store information and perform computations correctly, but cannot be trusted to ensure privacy. In our schemes, a semi-trusted computer is used to store and display public challenges. The user memorizes a random secret mapping and authenticates by computing responses to a sequence of public challenges, where is a function that is easy for the human to evaluate. We prove that any statistical adversary needs to sample challenge-response pairs to recover for a security parameter that depends on two key properties of. Our statistical dimension lower bounds apply to arbitrary functions --- not just functions that are easy for a human to evaluate --- and may be of independent interest. For our particular schemes, we show that forging passwords is equivalent to recovering the secret mapping. We also show that for our first scheme and that in our second scheme. Thus, our human computable password schemes can maintain strong security guarantees even after an adversary has observed the user login to many different accounts (e.g., 100). We also issue a public challenge to the cryptography community to crack passwords that were generated using our human computable password schemes.