Speaker: CMU Postdoc Fellow Jeremiah Blocki

Title: Human Computable Passwords

Abstract:

 An interesting challenge for the cryptography community is to design authentication protocols that are so simple that a human can execute them without relying on a fully trusted computer. In this talk I will present a human computable password scheme in which the user can only receive assistance from a semi-trusted computer---a computer that stores and retrieves information correctly but does not provide confidentiality of the information it stores. To begin using our challenge-response scheme the user first memorizes a secret mapping $\sigma$ from $n$ images to digits, and learns to evaluate a simple function f in his head. The user authenticates by computing the responses to a sequence of public challenges (each challenge consists of several images and the response is computed by applying the function f to the corresponding secret values given by $\sigma$). While the challenges in our scheme are stored on a semi-trusted computer, we stress that all of the computation is done in the user’s head.We provide strong evidence that our human computable password scheme remains secure even after an adversary has observed the user login to many different accounts. In particular, we prove that any statistical adversary needs to sample at least $n^{s(f)-\epsilon}$ challenge-response pairs to recover the secret mapping, for a security parameter s(f) that depends on two key properties of the function f that the user computes to respond to each challenge. Our lower bound generalizes recent results of Feldman et al. who proved analogous results for the special case when f is a binary function. To obtain our results, we apply the general hypercontractivity theorem to lower bound the statistical dimension of the distribution over challenge-response pairs induced by f and the user’s secret mapping. Our statistical dimension lower bounds apply to arbitrary functions f (not just to functions that are easy for a human to evaluate). We propose a family of human computable password functions $f_{k_1,k_2}$ in which the user needs to perform $2k_1+2k_2+1$ primitive operations (e.g., adding two digits or looking up a secret value), and we show that $s(f) = min{k_1+1, (k_2+1)/2}$. For these schemes, we prove that forging passwords is equivalent to recovering the secret mapping. Thus, our human computable password schemes can maintain strong security guarantees even after an adversary has observed the user login to many different accounts.

Biography: 

Jeremiah Blocki is a post-doctoral fellow in the Computer Science Department at Carnegie Mellon University. He completed his PhD at Carnegie Mellon University in 2014 under the supervision of Manuel Blum and Anupam Datta. His research interests include: Passwords, Usable and Secure Human Authentication, Human Computable Cryptography, Differential Privacy and the intersection of Game Theory and Security. He is generally interested in applying fundamental ideas from theoretical computer science to address practical problems in privacy and security.