Rafail Ostrovsky - Publications

Password-Authenticated Session-Key Generation on the Internet in the Plain Model

Vipul Goyal, Abhishek Jain, Rafail Ostrovsky,


The problem of password-authenticated key exchange (PAKE) has been extensively studies for the last two decades. Despite extensive studies, no construction was known for a PAKE protocol that is secure in the plain model in the setting of concurrent self-composition, where polynomially many protocol sessions with the same password may be executed on the distributed network (such as the Internet) in an arbitrarily interleaved manner, and where the adversary may corrupt any number of participating parties.

In this paper, we resolve this long-standing open problem. In particular, we give the first construction of a PAKE protocol that is secure ( with respect to the standard definition of Goldreich and Lindell) in the fully concurrent setting and without requiring any trusted setup assumptions. We stress that we allow Polynomially-many concurrent sessions, where polynomial is not fixed in advance and can be determined by an adversary an adaptive manner. Interestingly, our proof, among other things, requires important ideas from Precise Zero Knowledge theory recently developed by Micali and Pass in their STOC"06 paper.

comment: Preliminary version appeared in Crypto 2010: 277-294. Full version appeared in J. ACM 57(1): 3:1-3:39 (2009)

Fetch PDF file of the paper

Back to Publications List