Faster and Shorter Password-Authenticated Key Exchange

Abstract This paper presents an improved password-based authenticated key exchange protocols inthe common reference string model. Its security proof requires no idealized assumption (such as random oracles).The protocol is based on the GL framework introduced by Gennaro and Lindell, which gen-eralizes the KOY key exchange protocol of Katz et al. Both the KOY and the GL protocols use(one-time) signatures as a non-malleability tool in order to prevent a man-in-the-middle attack against the protocol. The efficiency of the resulting protocol is negatively affected, since if weuse regular signatures, they require a large amount of computation (almost as much as the rest of the protocol) and further computational assumptions. If one-time signatures are used, theysubstantially increase the bandwidth requirement. Our improvement avoids using digital signatures altogether, replacing them with faster andshorter message authentication codes. The crucial idea is to leverage as much as possible the non-malleability of the encryption scheme used in the protocol, by including various values intothe ciphertexts as labels. As in the case of the GL framework, our protocol can be efficientlyinstantiated using either the DDH, Quadratic Residuosity or N-Residuosity Assumptions.For typical security parameters our solution saves as much as 12 Kbytes of bandwidth if one-time signatures are implemented in GL with fast symmetric primitives. If we use number-theoretic signatures in the GL framework, our solution saves several large exponentiations (al-most a third of the exponentiations computed in the GL protocol). The end result is that webring provable security in the realm of password-authenticated key exchange one step closer to practical. 1 Introduction The central problem of cryptography is to enable reliable and secure communication among parties in the presence of an adversary. In order to do this, parties must share a common secret key to secure communication using known techniques (e.g., applying encryption and message authentication codes to all messages)