The amount and value of information we store in computers, servers or the collective cloud keeps growing while the ways of protecting it are mostly limited by the strength of a memorizable password. Even when the valuable information is stored with strong security, retrieval authorization often boils down to knowing a weak password. In spite of some protection being added against online attacks via two-factor authentication tools, the main vulnerability of passwords, and of the information they protect, remains offline dictionary attacks against compromised servers. Indeed, loss of millions of passwords to such attacks are common news nowadays. A natural approach to strengthening the protection of data against server compromise is to distribute storage among a set of servers, for example using a secret sharing scheme. However, how does the user access these servers? Using the same password in each of these servers makes the off-line password recovery attack even worse (as it can be performed against any of these servers) while memorizing a different password for each server is impractical and further weakens the password.

In this talk I will describe a practical (t,n)-PPSS (Password-Protected Secret Sharing) scheme in which a user Alice stores secret information among n servers so that she can later recover the information solely based on her password. The security requirement is similar to a (t,n)-threshold secret sharing, i.e., Alice can recover her secret as long as she can communicate with t+1 honest servers but an attacker gaining access to t servers cannot learn any information about the secret (and the password). In particular, the system is secure against offline password attacks by an attacker controlling up to t servers. The presented PPSS scheme is round-optimal, requiring just one message from user to server and from server to user, is computationally very efficient and is proved secure in the password-only setting where users are not assumed to carry, or have access to, an authenticated public key. As an important application we build the first single-round password-only Threshold-PAKE protocol in the CRS and ROM models for arbitrary (t,n) parameters with no PKI requirements for any party (clients or servers) and no inter-server communication.

Time permitting I will mention some other recent work on two-factor authentication where an auxiliary device is used to strengthen password authentication not only against on-line attacks but also against server compromise (without assuming PKI).

The talk is based on works with co-authors Stas Jarecki, Aggelos Kiayas, Jiayu Xu, Nitesh Saxena and Maliheh Shirvanian.