There has been much interest in password-authenticated keyexchange protocols which remain secure even when users choose passwords
from a very small space of possible passwords (say, a dictionary of English words). Under this assumption, one must be careful
to design protocols which cannot be broken using
off-line dictionary attacks in which an adversary enumerates all possible passwords in an attempt to determine the correct one. Many heuristic
protocols have been proposed to solve this important problem. Only recently have formal validations of security (namely, proofs
in the idealized random oracle and ideal cipher models) been given for specific constructions [3,10,22].
Very recently, a construction based on general assumptions, secure in the standard model with human-memorable passwords, has
been proposed by Goldreich and Lindell [17]. Their protocol requires no public parameters; unfortunately, it requires techniques
from general multi-party computation which make it impractical. Thus, [17] only proves that solutions are possible “in principal”.
The main question left open by their work was finding an efficient solution to this fundamental problem.
We showan efficient, 3-round, password-authenticated key exchange protocol with human-memorable passwords which is provably
secure under the Decisional Diffie-Hellman assumption, yet requires only (roughly) 8 times more computation than “standard”
Diffie-Hellman key exchange [14] (which provides no authentication at all). We assume public parameters available to all parties.
We stress that we work in the standard model only, and do not require a “random oracle” assumption.