Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords
Jonathan Katz, Rafail Ostrovsky, Moti Yung
Abstract:
There has been much interest in password-authenticated key-exchange 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 \emph{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 [BPR00,BMP00,MPS00].
Very recently, a construction based on general assumptions, secure in the standard model with human-memorable passwords, has been proposed by Goldreich and Lindell [GL00]. Their protocol requires no public parameters; unfortunately, it requires techniques from general multi-party computation which make it impractical. Thus, [GL00] 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 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 [DH76] (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.
comment: Appeared in Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
Fetch PostScript file of the paper Fetch PDF file of the paper