Paper 2004/182

Simpler Session-Key Generation from Short Random Passwords

Minh-Huyen Nguyen and Salil Vadhan

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.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. An extended abstract of this paper has appeared in the First Theory of Cryptography Conference (TCC `04).
Keywords
Password authenticationkey exchange
Contact author(s)
mnguyen @ eecs harvard edu
History
2004-08-07: received
Short URL
https://ia.cr/2004/182
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/182,
      author = {Minh-Huyen Nguyen and Salil Vadhan},
      title = {Simpler Session-Key Generation from Short Random Passwords},
      howpublished = {Cryptology ePrint Archive, Paper 2004/182},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/182}},
      url = {https://eprint.iacr.org/2004/182}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.