Threshold password-authenticated key exchange

In most password-authenticated key exchange systems there is a single server storing password verification data. To provide some resilience against server compromise, this data typically takes the form of a one-way function of the password (and possibly a salt, or other public values) rather than the password itself. However, if the server is compromised, this password verification data can be used to perform an off-line dictionary attack on the user's password. In this paper we propose an efficient password-authenticated key exchange system involving a set of servers with known public keys, in which a certain threshold of servers must participate in the authentication of a user, and in which the compromise of any fewer than that threshold of servers does not allow an attacker to perform an off-line dictionary attack. We prove our system is secure in the random oracle model under the Decision Diffie-Hellman assumption against an attacker that may eavesdrop on, insert, delete, or modify messages between the user and servers, and that compromises fewer than that threshold of servers.