[Resource Topic] 2004/182: Simpler Session-Key Generation from Short Random Passwords

Welcome to the resource topic for 2004/182

Simpler Session-Key Generation from Short Random Passwords

Authors: Minh-Huyen Nguyen, Salil Vadhan


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, i.e. the password is a
short random string (like an ATM PIN number). Our protocol can be converted into one
for arbitrary dictionaries using a common reference string of logarithmic length. 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(\mathrm{poly}(n)/|D|)^{\Omega(1)}, whereas the GL protocol
guarantees a bound of O(1/|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.

ePrint: https://eprint.iacr.org/2004/182

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .