Kristiyan Haralambiev
New York University

Efficient Password-Authenticated Key Exchange Using Human-Memorizable Passwords

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 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.
Very recently, a construction based on general assumptions, secure in the 
standard model with human-memorable passwords, have been proposed by 
Goldreich and Lindell. Their protocol requires no public parameters; 
unfortunately, it requires techniques from general multi-party computation 
which make it impractical. Thus, 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 (roughly) 8 times more computation 
than "standard" Diffie-Hellman key exchange (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" 

Jonathan Katz, Rafail Ostrovsky, and Moti Yung