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 formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20040807:042839 (All versions of this report) Discussion forum: Show discussion | Start new discussion