Paper 2014/247

Introducing Fault Tolerance into Threshold Password-Authenticated Key Exchange

Ivan Pryvalov and Aniket Kate


A threshold password-authenticated key exchange (T-PAKE) protocol allows a set of n servers to collectively authenticate a client with a human-memorizable password such that any subset of size greater than a threshold t can authenticate the client, while smaller subsets of servers learn no information about the password. With its protection against offline dictionary attacks, T-PAKE provides a practical solution for an important real-life problem with password authentication. However, the proposed T-PAKE constructions cannot tolerate any misbehavior---not even a crash---by a participating server during a protocol execution; the protocol has to be re-executed until all participating servers behave correctly. This not only presents a fault management challenge for the servers, but more importantly also can leave the clients frustrated for being denied access even after entering a correct password. In this work, we present a novel T-PAKE protocol which solves the above fault management problem by employing a batched and offline phase of distributed key generation (DKG). Our protocol is secure against any malicious behavior from up to any t < n servers under the decisional Diffie-Hellman assumption in the random oracle model, and it ensures protocol completion for t < n/2. Moreover, it is efficient (16n + 7 exponentiations per client, 20n + 14 per server), performs explicit authentication in three communication rounds, and requires a significantly lesser number of broadcast rounds compared to previous secure T-PAKE constructions. We have implemented our protocol, and have verified its efficiency using micro-benchmark experiments. Our experimental results show that the protocol only introduces a computation overhead of few milliseconds at both the client and the server ends, and it is practical for use in real-life authentication scenarios.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
password authenticationkey exchangefault tolerancethreshold cryptographyround complexitydistributed key generationdictionary attack
Contact author(s)
pryvalov @ cs uni-saarland de
2014-07-30: revised
2014-04-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivan Pryvalov and Aniket Kate},
      title = {Introducing Fault Tolerance into Threshold Password-Authenticated Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2014/247},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.