Goldreich and Lindell (CRYPTO ’01) recently presented the first protocol for password-authenticated key exchange in the standard
model (with no common reference string or set-up assumptions other than the shared password). However, their protocol uses
several heavy tools and has a complicated analysis.
We present a simplification of the Goldreich–Lindell (GL) protocol and analysis for the special case when the dictionary is
of the form
D={0,1}d\mathcal{D}=\{0,1\}^{d}
i.e., the password is a short string chosen uniformly at random (in the spirit of an ATM PIN number). The security bound achieved
by our protocol is somewhat worse than the GL protocol. Roughly speaking, our protocol guarantees that the adversary can “break”
the scheme with probability at most
O(poly(n)/|D|)W(1)O(\mathrm{poly}(n)/|\mathcal{D}|)^{\Omega(1)}
, whereas the GL protocol guarantees a bound of
O(1/|D|)O(1/|\mathcal{D}|)
.
We also present an alternative, more natural definition of security than the “augmented definition” of Goldreich and Lindell,
and prove that the two definitions are equivalent.
Keywords Human-memorizable passwords - Key exchange - Authentication - Cryptographic protocols - Secure two-party computation
Communicated by Oded Goldreich
An extended abstract of this paper appeared in the First Theory of Cryptography Conference (TCC ’04) [22].
Minh-Huyen Nguyen: Supported by NSF grant CCR-0205423 and ONR grant N00014-04-1-0478.
Salil Vadhan: Supported by NSF grant CCR-0205423, a Sloan Research Fellowship, and ONR grant N00014-04-1-0478. Part of this
work done while at the Radcliffe Institute for Advanced Study.