Introducing Fault Tolerance into Threshold Password-Authenticated Key Exchange
Ivan Pryvalov, Aniket Kate · 2014
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 leaves the clients frustrated for being denied access even after entering a correct password. In this work, we present a novel T-PAKE protocol (T-PAKEDKG) which solves the above fault management problem by employing a batched and offline phase of distributed key generation (DKG). T-PAKEDKG 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 T-PAKEDKG, and have verified its efficiency using micro-benchmark experiments. Our experimental results show that T-PAKEDKG 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. 1