Paper 2013/833

Verifier-Based Password-Authenticated Key Exchange: New Models and Constructions

Fabrice Benhamouda and David Pointcheval


While password-authenticated key exchange (or PAKE) protocols have been deeply studied, a server corruption remains the main threat, with many concrete cases nowadays. Verifier-based PAKE (or VPAKE) protocols, initially called Augmented-PAKE, have been proposed to limit the impact of any leakage. However, no satisfactory security model has ever been proposed to quantify the actual security of a protocol in the standard model. The unique model proposed so far is an ideal functionality in the universal composability (\UC) framework, but is only meaningful in idealized models. In this paper, we first formally define some properties for the transform (password hashing) applied to the password for the storage on the server-side, for an efficient VPAKE use. A tight one-wayness is required to prevent improved password searches. We then enhance the Bellare-Pointcheval-Rogaway game-based model for PAKE to VPAKE protocols, in such a way that it allows a VPAKE protocol to be secure in the standard model. In addition, we show how to further extend this model to handle non-uniform and related passwords, both in case of PAKE and VPAKE. Finally, we propose very efficient constructions of password hashing and \VPAKE protocols, which are nearly as efficient as the best PAKE protocols to date.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Multi-linear mapssmooth projective hash functionsauthenticationkey exchange
Contact author(s)
fabrice ben hamouda @ ens fr
2014-10-14: revised
2013-12-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fabrice Benhamouda and David Pointcheval},
      title = {Verifier-Based Password-Authenticated Key Exchange: New Models and Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/833},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.