Faster and Shorter Password-Authenticated Key Exchange

This paper presents an improved password-based authenticated key exchange protocol in the 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 generalizes 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 we use 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, they substantially increase the bandwidth requirement.

Our improvement avoids using digital signatures altogether, replacing them with faster and shorter 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 into the ciphertexts as

labels

. As in the case of the

GL

framework, our protocol can be efficiently instantiated 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 (almost a third of the exponentiations computed in the

GL

protocol). The end result is that we bring provable security in the realm of password-authenticated key exchange one step closer to practical.