Abstract
We consider the problem of password-authenticated key exchange (PAK) also known as session-key generation using passwords: constructing session-key generation protocols that are secure against active adversaries (person-in-the-middle) and only require the legitimate parties to share a low-entropy password (e.g. coming from a dictionary of size poly(n)).
We study the relationship between PAK and other cryptographic primitives. The main result of this paper is that password-authenticated key exchange and public-key encryption are incomparable under black-box reductions. In addition, we strengthen previous results by Halevi and Krawczyk [14] and Boyarsky [5] and show how to build key agreement and semi-honest oblivious transfer from any PAK protocol that is secure for the Goldreich-Lindell (GL) definition [11].
We highlight the difference between two existing definitions of PAK, namely the indistinguishability-based definition of Bellare, Pointcheval and Rogaway (BPR) [1] and the simulation-based definition of Goldreich and Lindell [11] by showing that there exists a PAK protocol that is secure for the BPR definition and only assumes the existence of one-way functions in the case of exponential-sized dictionaries. Hence, unlike the GL definition, the BPR definition does not imply semi-honest oblivious transfer for exponental-sized dictionaries under black-box reductions.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure against dictionary attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 139–155. Springer, Heidelberg (2000)
Bellare, M., Rogaway, P.: Entity authentication and key distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994)
Bellovin, S., Merritt, M.: Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks. In: ACM/IEEE Symposium on Research in Security and Privacy, pp. 72–84 (1992)
Bellovin, S., Merritt, M.: Augmented Encrypted Key Exchange: A Password-Based Protocol Secure against Dictionary Attacks and Password File Compromise. In: ACM Conference on Computer and Communications Security, pp. 244–250 (1993)
Boyarsky, M.: Public-Key Cryptography and Password Protocols: The Multi-User Case. In: ACM Conference on Computer and Communications Security, pp. 63–72 (1999)
Boyko, V., MacKenzie, P.D., Patel, S.: Provably secure password-authenticated key exchange using diffie-hellman. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 156–171. Springer, Heidelberg (2000)
Canetti, R., Halevi, S., Katz, J., Lindell, Y., MacKenzie, P.: Universally Composable Password-Based Key Exchange (2004) (unpublished manuscript)
Gennaro, R., Lindell, Y.: A Framework for Password-Based Authenticated Key Exchange. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 524–543. Springer, Heidelberg (2003)
Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The Relationship between Public-Key Encryption and Oblivious Transfer. In: IEEE Symposium on the Foundations of Computer Science, pp. 325–335 (2001)
Goldreich, O.: Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (2004)
Goldreich, O., Lindell, Y.: Session-key generation using human passwords only. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 408–432. Springer, Heidelberg (2001)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proofs. Journal of the ACM 38(3), 691–729 (1991)
Goldreich, O., Nisan, N., Wigderson, A.: On Yao’s XOR Lemma. In: Electronic Colloquium on Computational Complexity (1995) TR95-050
Halevi, S., Krawczyk, H.: Public-Key Cryptography and Password Protocols. In: ACM Conference on Computer and Communications Security, pp. 122–131 (1998)
Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-way Permutations. In: ACM Symposium on Theory of Computing, pp. 44–61 (1989)
Katz, J.: Efficient Cryptographic Protocols Preventing ‘Man-in-the-Middle’ Attacks. Ph.D. Thesis. Columbia University (2002)
Katz, J., Ostrovsky, R., Yung, M.: Efficient password-authenticated key exchange using human-memorable passwords. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 475–494. Springer, Heidelberg (2001)
Kilian, J.: A General Completeness Theorem for Two-Party Games. In: ACM Symposium on Theory of Computing, pp. 553–560 (1991)
Full version of this paper at, http://www.people.fas.harvard.edu/~mnguyen
Nguyen, M.-H., Vadhan, S.P.: Simpler session-key generation from short random passwords. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 428–445. Springer, Heidelberg (2004)
Nisan, N., Zuckerman, D.: Randomness is Linear in Space. Journal of Computer and System Sciences 52(1), 43–52 (1996)
Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004)
Rudich, S.: The use of interaction in public cryptosystems. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 242–251. Springer, Heidelberg (1992)
Steiner, M., Tsudik, G., Waidner, M.: Refinement and Extension of Encrypted Key Exchange. Operating Systems Review 29(3), 22–30 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nguyen, MH. (2005). The Relationship Between Password-Authenticated Key Exchange and Other Cryptographic Primitives. In: Kilian, J. (eds) Theory of Cryptography. TCC 2005. Lecture Notes in Computer Science, vol 3378. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30576-7_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-30576-7_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24573-5
Online ISBN: 978-3-540-30576-7
eBook Packages: Computer ScienceComputer Science (R0)