Provably Secure Threshold Password-Authenticated Key Exchange

We present two protocols for threshold password authenticated key exchange. In this model for password authentication, the password is not stored in a single authenticating server but rather shared among a set of n servers so that an adversary can learn the password only by breaking into t + 1 of them. The protocols require n > 3t servers to work. The goal is to protect the password against hackers attacks that can break into the authenticating server and steal password information. All known centralized password authentication schemes are susceptible to such an attack. Ours are the first protocols which are provably secure in the standard model (i.e., no random oracles are used for the proof of security). Moreover, our protocols are reasonably efficient and implementable in practice. In particular a goal of the design was to avoid costly zero-knowledge proofs to keep interaction to a minimum.