Abstract. 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] We show an 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.
We heavily use the efficient protocol by Katz, Ostrovsky and Yung in REF which is provably secure in the standard model, i.e. without assuming random oracles.
Efficient Password-Authenticated Key Exchange using Human-Memorable Passwords
IACR Cryptology ePrint Archive
IACR Cryptology ePrint Archive
Computer Science