SCIENCE CHINA Information Sciences, Volume 60, Issue 5: 052107(2017) https://doi.org/10.1007/s11432-016-5522-z

Universally composable anonymous password authenticated key exchange

More info
  • ReceivedOct 12, 2015
  • AcceptedNov 24, 2015
  • PublishedSep 28, 2016


Anonymous password authenticated key exchange (APAKE) is an important cryptographic primitive, through which a client holding a password can establish a session key with a server both authentically and anonymously. Although the server is guaranteed that the client in communication is from a pre-determined group, but the client's actual identity is protected. Because of their convenience, APAKE protocols have been widely studied and applied to the privacy protection research. However, all existing APAKE protocols are handled in stand-alone models and do not adequately settle the problem of protocol composition, which is a practical issue for protocol implementation. In this paper, we overcome this issue by formulating and realizing an ideal functionality for APAKE within the well-known universal composability (UC) framework, which thus guarantees security under the protocol composition operations. Our formulation captures the essential security requirements of APAKE such as off-line dictionary attack resistance, client anonymity and explicit mutual authentication. Moreover, it addresses the arbitrary probabilistic distribution of passwords. The construction of our protocol, which utilizes SPHF-friendly commitments and CCA2-secure encryption schemes, can be instantiated and proven secure in the standard model, i.e., without random oracle heuristics.

Funded by

China Postdoctoral Science Foundation(2014M552524)

National Basic Research Program of China(2013CB338003)

National Basic Research Program of China(2012CB315905)

National Natural Science Foundation of China(61170279)

Foundation of Science and Technology on Information Assurance Laboratory(KJ-14-004)

National Natural Science Foundation of China(61379150)

National High Technology Research and Development Program of China(2012AA01A\\linebreak403)

National Natural Science Foundation of China(61502527)

National Natural Science Foundation of China(61170278)



This work was supported by National Natural Science Foundation of China (Grant Nos. 61502527, 61170278, 61170279, 61379150), National Basic Research Program of China (Grant Nos. 2013CB338003, 2012CB315905), National High Technology Research and Development Program of China (Grant No. 2012AA01A\linebreak403), China Postdoctoral Science Foundation (Grant No. 2014M552524), and Foundation of Science and Technology on Information Assurance Laboratory (Grant No. KJ-14-004).


[1] Wang S B, Zhu Y, Ma D, et al. Lattice-based key exchange on small integer solution problem. Sci China Inf Sci, 2014, 57: 112111 Google Scholar

[2] Zhang J, Zhang Z F, Ding J D, et al. Authenticated key exchange from ideal lattices. In: Oswald E, Fischlin M, eds. Advances in Cryptology--EUROCRYPT 2015, LNCS 9057. Berlin: Springer, 2015. 719--751. Google Scholar

[3] Camenisch J, Lehmann A, Lysyanskaya A, et al. Memento: how to reconstruct your secrets from a single password in a hostile environment. In: Garay J, Gennaro R, eds. Advances in Cryptology--CRYPTO 2014, LNCS 8617. Berlin: Springer, 2014. 256--275. Google Scholar

[4] Bellovin S\,M, Merritt M. Encrypted key exchange: password-based protocols secure against dictionary attacks. In: Proceedings of IEEE Computer Society Symposium on Research in Security and Privacy, Los Alamitos, 1992. 72--84. Google Scholar

[5] Bellare M, Pointcheval D, Rogaway P. Authenticated key exchange secure against dictionary attacks. In: Preneel B, ed. Advances in Cryptology--EUROCRYPT 2000, LNCS 1807. Berlin: Springer, 2000. 139--155. Google Scholar

[6] Katz J, Ostrovsky R, Yung M. Efficient password-authenticated key exchange using human-memorable passwords. In: Pfitzmann B, ed. Advances in Cryptology--EUROCRYPT 2001, LNCS 2045. Berlin: Springer, 2001. 475--494. Google Scholar

[7] Jiang S Q, Gong G. Password based key exchange with mutual authentication. In: Handschuh H, Hasan M, eds. Selected Areas in Cryptography, LNCS 3357. Berlin: Springer, 2005. 267--279. Google Scholar

[8] Benhamouda F, Blazy O, Chevalier C, et al. New techniques for {SPHF}s and efficient one-round {PAKE} protocols. In: Canetti R, Garay J, eds. Advances in Cryptology--CRYPTO 2013, LNCS 8042. Berlin: Springer, 2013. 449--475. Google Scholar

[9] Chien H Y, Wu T C, Yeh M K. Provably secure gateway-oriented password-based authenticated key exchange protocol resistant to password guessing attacks. J Inf Sci Eng, 2013, 29: 249-265 Google Scholar

[10] Li W M, Wen Q Y, Su Q, et al. Password-authenticated multiple key exchange protocol for mobile applications. China Commun, 2012, 9: 64-72 Google Scholar

[11] IEEE. IEEE standard specifications for password-based public-key cryptographic techniques. {IEEE Std 1363.2-2008}. doi: {10.1109/IEEESTD.2009.4773330}. Google Scholar

[12] Sheffer Y, Zorn G, Tschofenig H, et al. An EAP authentication method based on the encrypted key exchange (EKE) protocol. RFC 6124. https://www.rfc-editor.org/info/rfc6124. Google Scholar

[13] Lindell Y. Anonymous authentication. J Priv Confidentiality, 2007, 2: 35-63 Google Scholar

[14] Viet D, Yamamura A, Tanaka H. Anonymous password-based authenticated key exchange. In: Maitra S, Veni M C, Venkatesan R, eds. Progress in Cryptology--INDOCRYPT 2005, LNCS 3797. Berlin: Springer, 2005. 244--257. Google Scholar

[15] Shin S, Kobara K, Imai H. A secure threshold anonymous password-authenticated key exchange protocol. In: Miyaji A, Kikuchi H, Rannenberg K, eds. Advances in Information and Computer Security, LNCS 4752. Berlin: Springer, 2007. 444--458. Google Scholar

[16] Yang J, Zhang Z F. A new anonymous password-based authenticated key exchange protocol. In: Chowdhury D, Rijmen V, Das A, eds. Progress in Cryptology--INDOCRYPT 2008, LNCS 5365. Berlin: Springer, 2008. 200--212. Google Scholar

[17] Jablon D P. Strong password-only authenticated key exchange. ACM SIGCOMM Comput Commun Rev, 1996, 26: 5-26 Google Scholar

[18] Shin S, Kobara K, Imai H. Anonymous password-authenticated key exchange: new construction and its extensions. IEICE Trans Fund Electron Commun Comput Sci, 2010, 93: 102-115 Google Scholar

[19] Yang Y J, Zhou J Y, Weng J, et al. A new approach for anonymous password authentication. In: Proceedings of the 25th Annual Computer Security Applications Conference, Honolulu, 2009. 199--208. Google Scholar

[20] Yang Y J, Zhou J Y, Wong J W, et al. Towards practical anonymous password authentication. In: Proceedings of the 26th Annual Computer Security Applications Conference. New York: ACM, 2010. 59--68. Google Scholar

[21] Qian H F, Gong J Q, Zhou Y. Anonymous password-based key exchange with low resources consumption and better user-friendliness. Secur Commun Netw, 2012, 5: 1379-1393 CrossRef Google Scholar

[22] Abdalla M, Benhamouda F, Pointcheval D, et al. SPOKE: simple password-only key exchange in the standard model. Cryptology ePrint Archive, Report 2014/609. https://eprint.iacr.org/eprint-bin/versions.pl?entry=2014/609. Google Scholar

[23] Canetti R. Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, Washington, 2001. 136--145. Google Scholar

[24] Canetti R, Halevi S, Katz J, et al. Universally composable password-based key exchange. In: Cramer R, ed. Advances in Cryptology--EUROCRYPT 2005, LNCS 3494. Berlin: Springer, 2005. 404--421. Google Scholar

[25] Abdalla M, Catalano D, Chevalier C, et al. Efficient two-party password-based key exchange protocols in the {UC} framework. In: Malkin T, ed. Topics in Cryptology--CT-RSA 2008, LNCS 4964. Berlin: Springer, 2008. 335--351. Google Scholar

[26] Groce A, Katz J. A new framework for efficient password-based authenticated key exchange. In: Proceedings of the 17th ACM Conference on Computer and Communications Security--CCS'10. New York: ACM, 2010. 516--525. Google Scholar

[27] Hu X X, Zhang Z F, Liu W F. Universal composable password authenticated key exchange protocol in the standard model (in Chinese). J Softw, 2011, 22: 2820-2832 CrossRef Google Scholar

[28] Abdalla M, Benhamouda F, Blazy O, et al. {SPHF}-friendly non-interactive commitments. In: Sako K, Sarkar P, eds. Advances in Cryptology--ASIACRYPT 2013, LNCS 8269. Berlin: Springer, 2013. 214--234. Google Scholar

[29] Gennaro R, Lindell Y. A framework for password-based authenticated key exchange. In: Biham E, ed. Advances in Cryptology--EUROCRYPT 2003, LNCS 2656. Berlin: Springer, 2003. 524--543. Google Scholar

[30] Canetti R, Rabin T. Universal composition with joint state. In: Boneh D, ed. Advances in Cryptology-CRYPTO 2003, LNCS 2729. Berlin: Springer, 2003. 265--281. Google Scholar

[31] Abdalla M, Chevalier C, Pointcheval D. Smooth projective hashing for conditionally extractable commitments. In: Halevi S, ed. Advances in Cryptology--CRYPTO 2009, LNCS 5677. Berlin: Springer, 2009. 671--689. Google Scholar

[32] Cramer R, Shoup V. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen L, ed. Advances in Cryptology--EUROCRYPT 2002, LNCS 2332. Berlin: Springer, 2002. 45--64. Google Scholar

[33] Katz J, Vaikuntanathan V. Round-optimal password-based authenticated key exchange. J Cryptol, 2013, 26: 714-743 CrossRef Google Scholar

[34] Haralambiev K. Efficient cryptographic primitives for non-interactive zero-knowledge proofs and applications. Dissertation for Ph.D. Degree. New York: New York University, 2011. Google Scholar

[35] Cramer R, Shoup V. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk H, ed. Advances in Cryptology--CRYPTO'98, LNCS 1462. Berlin: Springer, 1998. 13--25. Google Scholar

[36] Bellare M, Boldyreva A, Palacio A. An uninstantiable random oracle model scheme for a hybrid-encryption problem. In: Cachin C, Camenisch J, eds. Advances in Cryptology--EUROCRYPT 2004, LNCS 3027. Berlin: Springer, 2004. 171--188. Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有