More efficient password-authenticated key exchange

In this paper we show various techniques for improving the efficiency of the PAK and PAK-X password-authenticated key exchange protocols while maintaining provable security. First we show how to decrease the client-side computation by half in the standard PAK protocol (i.e., PAK over a subgroup of Z(p)(*)). Then we show a version of PAK that is provably secure against server compromise but is conceptually much simpler than the PAK-X protocol. Finally we show how to modify the PAK protocol for use over elliptic curve and XTR groups, thus allowing greater efficiency compared to running PAK over a subgroup of Z(p)(*).