Rosario Gennaro
IBM Research

Faster and Shorter Password-Authenticated Key Exchange

This paper presents an improved password-based authenticated key
exchange protocols 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 {\em 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 practic