Paper 2004/196

Password Based Key Exchange with Mutual Authentication

Shaoquan Jiang and Guang Gong


A reasonably efficient password based key exchange (KE) protocol with provable security without random oracle was recently proposed by Katz, {\em et al.} \cite{KOY01} and later by Gennaro and Lindell \cite{GL03}. However, these protocols do not support mutual authentication (MA). The authors explained that this could be achieved by adding an additional flow. But then this protocol turns out to be 4-round. As it is known that a high entropy secret based key exchange protocol with MA\footnote{we do not consider a protocol with a time stamp or a stateful protocol (e.g., a counter based protocol). In other words, we only consider protocols in which a session execution within an entity is independent of its history, and in which the network is asynchronous.} is optimally 3-round (otherwise, at least one entity is not authenticated since a replay attack is applicable), it is quite interesting to ask whether such a protocol in the password setting (without random oracle) is achievable or not. In this paper, we provide an affirmative answer with an efficient construction in the common reference string (CRS) model. Our protocol is even simpler than that of Katz, {\em et al.} Furthermore, we show that our protocol is secure under the DDH assumption ({\em without} random oracle).

Available format(s)
Publication info
Published elsewhere. An extended abstract appeared in SAC 2004. This is the full version.
ProtocolKey ExchangePassword
Contact author(s)
jiangshq @ calliope uwaterloo ca
2004-08-14: revised
2004-08-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shaoquan Jiang and Guang Gong},
      title = {Password Based Key Exchange with Mutual Authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2004/196},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.