International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Simpler Session-Key Generation from Short Random Passwords

Minh-Huyen Nguyen
Salil P. Vadhan
Search ePrint
Search Google
Abstract: 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.
  title={Simpler Session-Key Generation from Short Random Passwords},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / Password authentication, key exchange},
  note={An extended abstract of this paper has appeared in the First Theory of Cryptography Conference (TCC `04). 12636 received 6 Aug 2004},
  author={Minh-Huyen Nguyen and Salil P. Vadhan},