Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Password authentication, key exchange

Publication Info: An extended abstract of this paper has appeared in the First Theory of Cryptography Conference (TCC `04).

Date: received 6 Aug 2004

Contact author: mnguyen at eecs harvard edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040807:042839 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]