Password Authentication

A growing number of Internet services, such as email or stock-trading, require client authentication. Clients typically authenticate themselves to a website with a login and password. To prevent impersonation attacks, a different password must be chosen for each website. This approach to client authentication scales poorly. It is difficult for clients to choose, let alone remember, a large number of good passwords. In this talk, we propose an authentication scheme which allows a client to authenticate herself to a large number of websites, while remembering only a single master password. The master password is shared among the websites in a scheme akin to secret sharing. Unlike secret sharing however, our scheme degrades gracefully as the size of the coalition increases. We propose both a randomized construction and a deterministic construction. Unlike other solutions to the problem of multiple authentication, our scheme does not assume that the master password is secure against exhaustive search. Our scheme is information-theoretically secure and well adapted to master passwords as short as 40 bits.