Two-server password-only authenticated key exchange

Typical protocols for password-based authentication assume a single server that stores all the information (e.g., the password) necessary to authenticate a user. An inherent limitation of this approach, assuming low-entropy passwords are used, is that the userʼs password is exposed if this server is ever compromised. To address this issue, it has been suggested to share a userʼs password information among multiple servers, and to have these servers cooperate (possibly in a threshold manner) when the user wants to authenticate. We show here a two-server version of the password-only key-exchange protocol of Katz, Ostrovsky, and Yung (the KOY protocol). Our work gives the first secure two-server protocol for the password-only setting (in which the user need remember only a password, and not the serversʼ public keys), and is the first two-server protocol (in any setting) with a proof of security in the standard model. Our work thus fills a gap left by the work of MacKenzie et al. (2006) [31] and Di Raimondo and Gennaro (2006) [16]. As an additional benefit of our work, we show modifications that improve the efficiency of the original KOY protocol.