SCS Undergraduate Thesis Topics
|Shaun Allison||Manuel Blum||A Secure Human-Computable Authentication Scheme|
In a world where everyone is constantly watching, secure authentication is still possible. We propose a provably-secure authentication protocol that is both resistant to eavesdropping attacks, and can be carried out directly between you, the human user, and the authenticating computer, without any additional devices. The catch is that you must perform all the calculations in your head. However, we demonstrate that most humans are capable of this. We also give evidence that an adversary would have to spy on a significant number of authentications before being able to impersonate you. (Compared to the standard password scheme, where the adversary only has to see it once.) Specifically, we show that statistical adversaries must see 10^Omega(r) authentications in order to break the protocol, where r measures the length of the secret that the human user memorizes. Our work is based on recent results of Blocki et al. and Feldman et al. on statistical algorithm lower bounds which we apply to our protocol relying on the intractability of the k-junta problem.