A Lower-Bound of Complexity for RSA-Based Password-Authenticated Key Exchange

  • SeongHan Shin
  • Kazukuni Kobara
  • Hideki Imai
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3545)


Some RSA-based PAKE protocols have been proposed using a challenge-response method for verifying the validity of the server’s RSA public key due to the lack of a PKI. However, these kind of RSA-based PAKE protocols cannot specify the exact overall complexity of their protocols since there exists a system parameter l needed for the challenge-response method. In this paper we present an RSA-based PAKE (RSA-PAKE) protocol, followed by its lower-bound of complexity and the actual computation and communication costs.


Random Oracle Model Dictionary Attack Perfect Forward Secrecy Correct Password PAKE Protocol 
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.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bao, F.: Security analysis of a password authenticated key exchange protocol. In: Boyd, C., Mao, W. (eds.) ISC 2003. LNCS, vol. 2851, pp. 208–217. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  2. 2.
    Bresson, E., Chevassut, O., Pointcheval, D.: New security results on encrypted key exchange. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 145–158. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  3. 3.
    Bellovin, S.M., Merritt, M.: Encrypted Key Exchange: Password-based Protocols Secure against Dictionary Attacks. In: Proc. of IEEE Symposium on Security and Privacy, pp. 72–84. IEEE Computer Society, Los Alamitos (1992)CrossRefGoogle Scholar
  4. 4.
    Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: Proc. of ACM CCS 1993, pp. 62–73 (1993)Google Scholar
  5. 5.
    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)Google Scholar
  6. 6.
    Bellare, M., Rogaway, P.: The exact security of digital signatures - how to sign with RSA and rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996)CrossRefGoogle Scholar
  7. 7.
    Catalano, D., Pointcheval, D., Pornin, T.: IPAKE: Isomorphisms for password-based authenticated key exchange. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 477–493. Springer, Heidelberg (2004), The full version is available at
  8. 8.
    Frier, A., Karlton, P., Kocher, P.: The SSL 3.0 Protocol. Netscape Communication Corp (1996), Available at
  9. 9.
    Harkins, D., Carrel, D.: The Internet Key Exchange (IKE). IETF RFC 2409 (November 1998), Available at
  10. 10.
    Housley, R., Polk, T.: Planning for PKI: Best Practices Guide for Deploying Public Key Infrastructure. WILEY (March 2001)Google Scholar
  11. 11.
    IETF (Internet Engineering Task Force). Secure Shell (secsh) Charter, Available at
  12. 12.
    IETF (Internet Engineering Task Force). Transport Layer Security (tls) Charter, Available at
  13. 13.
    Kaufman, C.: Internet Key Exchange (IKEv2) Protocol (May 2003) (to be published as an RFC), Available at http://draft-ietf-ipsec-ikev2-03.txt
  14. 14.
    Lucks, S.: Open Key Exchange: How to Defeat Dictionary Attacks without Encrypting Public Keys. In: Proc. of Workshop on Security Protocols (1997)Google Scholar
  15. 15.
    Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography, pp. 613–616. CRC Press, Boca Raton (1997)zbMATHGoogle Scholar
  16. 16.
    MacKenzie, P.D., Patel, S., Swaminathan, R.: Password-authenticated key exchange based on RSA. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 599–613. Springer, Heidelberg (2000), A full version is available at
  17. 17.
    Patel, S.: Number Theoretic Attacks on Secure Password Schemes. In: Proc. of IEEE Symposium on Security and Privacy, pp. 236–247. IEEE Computer Society, Los Alamitos (1997)Google Scholar
  18. 18.
    Rosen, K.H.: Elementary Number Theory and Its Applications, 4th edn. Addison Wesley Longman, Luguna Hills (2000)zbMATHGoogle Scholar
  19. 19.
    Shoup, V.: On Formal Models for Secure Key Exchange. IBM Research Report RZ 3121 (1999), Available at
  20. 20.
    Wong, D.S., Chan, A.H., Zhu, F.: More efficient password authenticated key exchange based on RSA. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 375–387. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  21. 21.
    Zhang, M.: Further analysis of password authenticated key exchange protocol based on RSA for imbalanced wireless networks. In: Zhang, K., Zheng, Y. (eds.) ISC 2004. LNCS, vol. 3225, pp. 13–24. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  22. 22.
    Zhang, M.: New approaches to password authenticated key exchange based on RSA. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 230–244. Springer, Heidelberg (2004); Cryptology ePrint Archive, Report 2004/033, available at
  23. 23.
    Zhu, F., Wong, D.S., Chan, A.H., Ye, R.: Password authenticated key exchange based on RSA for imbalanced wireless networks. In: Chan, A.H., Gligor, V.D. (eds.) ISC 2002. LNCS, vol. 2433, pp. 150–161. Springer, Heidelberg (2002)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • SeongHan Shin
    • 1
  • Kazukuni Kobara
    • 1
  • Hideki Imai
    • 1
  1. 1.Institute of Industrial ScienceThe University of TokyoTokyoJapan

Personalised recommendations