Paper 2015/1144

Mitigating Server Breaches in Password-Based Authentication: Secure and Efficient Solutions

Olivier Blazy, Céline Chevalier, and Damien Vergnaud


Password-Authenticated Key Exchange allows users to generate a strong cryptographic key based on a shared \human-memorable" password without requiring a public-key infrastructure. It is one of the most widely used and fundamental cryptographic primitives. Unfortunately, mass password theft from organizations is continually in the news and, even if passwords are salted and hashed, brute force breaking of password hashing is usually very successful in practice. In this paper, we propose two efficient protocols where the password database is somehow shared among two servers (or more), and authentication requires a distributed computation involving the client and the servers. In this scenario, even if a server compromise is doable, the secret exposure is not valuable to the adversary since it reveals only a share of the password database and does not permit to brute force guess a password without further interactions with the parties for each guess. Our protocols rely on smooth projective hash functions and are proven secure under classical assumption in the standard model (i.e. do not require idealized assumption, such as random oracles).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. CT-RSA 2016
Password-Authenticated Key ExchangeDistributed ComputationDecision Diffie-HellmanSmooth Projective Hashing
Contact author(s)
olivier blazy @ unilim fr
2015-11-27: last of 2 revisions
2015-11-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Olivier Blazy and Céline Chevalier and Damien Vergnaud},
      title = {Mitigating Server Breaches in Password-Based Authentication: Secure and Efficient Solutions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1144},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.