Paper 1999/004

Public-key cryptography and password protocols

Shai Halevi and Hugo Krawczyk


We study protocols for strong authentication and key exchange in asymmetric scenarios where the authentication server possesses a pair of private and public keys while the client has only a weak human-memorizable password as its authentication key. We present and analyze several simple password protocols in this scenario, and show that the security of these protocols can be formally proven based on standard cryptographic assumptions. Remarkably, our analysis shows optimal resistance to off-line password guessing attacks under the choice of suitable public key encryption functions. In addition to user authentication, we enhance our protocols to provide two-way authentication, authenticated key exchange, defense against server's compromise, and user anonymity. We complement these results with a proof that public key techniques are unavoidable for password protocols that resist off-line guessing attacks. As a further contribution, we introduce the notion of public passwords that enables the use of the above protocols in situations where the client's machine does not have the means to validate the server's public key. Public passwords serve as "hand-held certificates" that the user can carry without the need for special computing devices.

Available format(s)
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
PasswordsPublic-key protocolsKey exchangeDictionary attacksPassword-guessingPublic passwordsHand-held certificates.
Contact author(s)
shaih @ watson ibm com
1999-02-14: received
Short URL
Creative Commons Attribution


      author = {Shai Halevi and Hugo Krawczyk},
      title = {Public-key cryptography and password protocols},
      howpublished = {Cryptology ePrint Archive, Paper 1999/004},
      year = {1999},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.