Abstract Certificate-based cryptography is a new public key cryptographic paradigm that has many appealing features since it simultaneously solves the certificate revocation problem in conventional public key cryptography and the key escrow problem in identity-based cryptography. Till now, three certificate-based Authenticated Key Agreement (AKA) protocols have been proposed. However, our cryptanalysis shows that none of them is secure under the public key replacement attack. To overcome the security weaknesses in these protocols, we develop a new certificate-based AKA protocol. In the random oracle model, we formerly prove its security under the hardness of discrete logarithm problem, computational Diffie-Hellman problem and bilinear Diffie-Hellman problem. Compared with the previous proposals, it enjoys lower computation overhead while providing stronger security assurance. To the best of our knowledge, it is the first certificate-based AKA protocol that resists the public key replacement attack in the literature so far.

References

[1] Al-Riyami S. and Paterson K., “Certificateless public key cryptography,” in Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Taipei, pp. 452-473, 2003.

[2] Bellare M. and Rogaway P., “Random Oracles are Practical: A Paradigm for Designing Efficient Protocols,” in Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, pp. 62-73, 1993.

[3] Blake-Wilson S. and Menezes A., “Authenticated Diffie-Hellman Key Agreement Protocols,” in Proceedings of the 6th Annual International Workshop on Selected Areas in Cryptography, Kingston, pp. 339-361, 1999.

[4] Boneh D. and Franklin M., “Identity-based Encryption from the Weil Pairing,” in Proceedings of Annual International Cryptology Conference, Santa Barbara, pp. 213-229, 2001.

[5] Boyen X., “The BB1 Identity-Based Cryptosystem: A Standard for Encryption And Key Encapsulation,” IEEE Standard 1363.3, 2006.

[6] Chen L. and Kudla C., “Identity Based Authenticated Key Agreement Protocols from Pairings,” in Proceedings of the 16th IEEE Computer Security Foundations Workshop, Pacific Grove, pp. 219-233, 2003.

[7] Diffie W. and Hellman M., “New directions in Cryptography,” IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644-654, 1976.

[8] Galindo D., Morillo P., and Ràfols C., “Improved Certificate-Based Encryption in The Standard Model,” Journal of Systems and Software, vol. 81, no. 7, pp. 1218-1226, 2008.

[9] Gentry C., “Certificate-Based Encryption and The Certificate Revocation Problem,” in Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, pp. 272-293, 2003.

[10] Jeong I., Katz J., and Lee D., “One-round Protocols for Two-Party Authenticated Key Exchange,” in Proceedings of the 2nd International Conference on Applied Cryptography and Network Security, Yellow Mountain, pp. 220-232, 2004.

[11] Kang B., Park J., and Hahn S., “A Certificate- Based Signature Scheme,” in Proceedings of Cryptographers’ Track at the RSA Conference, San Francisco, pp. 99-111, 2004.

[12] Law L., Menezes A., Qu M., Salinas J., and Vanstone S., “An Efficient Protocol for Authenticated Key Agreement,” Technical Report CORR98-05, University of Waterloo, 1998.

[13] Li J., Huang X., Mu Y., Susilo W., and Wu Q., “Constructions of Certificate-Based Signature Secure Against Key Replacement Attacks,” Journal of Computer Security, vol. 18, no. 3, pp. 421-449, 2010.

[14] Li J., Guo Y., Yu Q., Lu Y., Zhang Y., and Zhang F., “Continuous Leakage-Resilient Certificate-Based Encryption,” Information Sciences, vol. 355-356, pp. 1-14, 2016.

[15] Li J., Huang X., Zhang Y., and Xu L., “An Efficient Short Certificate-Based Signature 764 The International Arab Journal of Information Technology, Vol. 16, No. 4, July 2019 Scheme,” Journal of Systems and Software, vol. 85, no. 2, pp. 314-322, 2012.

[16] Li J., Teng H., Huang X., Zhang Y., and Zhou J., “A Forward-Secure Certificate-Based Signature Scheme,” The Computer Journal, vol. 58, no. 4, pp. 853-866, 2015.

[17] Li J., Wang Z., and Zhang Y., “Provably Secure Certificate-Based Signature Scheme without Pairings,” Information Sciences, vol. 233, pp. 313-320, 2013.

[18] Lim M., Lee S., and Lee H., “An Improved Variant of Wang-Cao’s Certificated-Based Authenticated Key Agreement Protocol,” in Proceedings of 4th International Conference on Networked Computing and Advanced Information Management, Gyeongju, pp. 198-201, 2008.

[19] Lippold G., Boyd C., and Nieto J., “Strongly Secure Certificateless Key Agreement,” in Proceedings of International Conference on Pairing-Based Cryptography, Palo Alto, pp. 206- 230, 2009.

[20] Liu J., Baek J., Susilo W., and Zhou J., “Certificate Based Signature Schemes without Pairings Or Random Oracles,” in Proceedings of the 11th International Conference on Information Security, Taipei, pp. 285-297, 2008.

[21] Liu J. and Zhou J., “Efficient Certificate-Based Encryption in The Standard Model,” in Proceedings of the 6th International Conference on Security and Cryptography for Networks, Amalfi, pp. 144-155, 2008.

[22] Lu Y. and Li J., “Efficient Construction of Certificate-Based Encryption Secure Against Public Key Replacement Attacks in the Standard Model,” Journal of Information Science and Engineering, vol. 30, no. 5, pp. 1553-1568, 2014.

[23] Lu Y. and Li J., “A Provably Secure Certificate- Based Encryption Scheme against Malicious CA Attacks in the Standard Model,” Information Sciences, vol. 372, pp. 745-757, 2016.

[24] Lu Y. and Li J., “An Improved Certificate-Based Signature Scheme without Random Oracles,” IET Information Security, vol. 10, no. 2, pp. 80-86, 2016.

[25] Luo M., Wen Y., and Zhao H., “A Certificate- Based Authenticated Key Agreement Protocol for SIP-Based Voip Networks,” in Proceedings of IFIP International Conference on Network and Parallel Computing, Shanghai, pp. 3-10, 2008.

[26] McCullagh N. and Barreto P., “A New Two-Party Identity-Based Authenticated Key Agreement,” in Proceedings of Cryptographers’ Track at the RSA Conference, San Francisco, pp. 262-274, 2005.

[27] Shi Y. and Li J., “Two-Party Authenticated Key Agreement in Certificateless Public Key Cryptography,” Wuhan University Journal of Natural Sciences, vol. 12, no. 1, pp. 71-74, 2007.

[28] Smart N., “An Id-Based Authenticated Key Agreement Protocol Based on The Weil Pairing,” Electronic Letters, vol. 38, no. 13, pp. 630-632, 2002.

[29] Wang S. and Cao Z., “Escrow-Free Certificate- Based Authenticated Key Agreement Protocol from Pairings,” Wuhan University Journal of Natural Science, vol. 12, no. 1, pp. 63-66, 2007.

[30] Wang S., Cao Z., and Dong X., “Certificateless Authenticated Key Agreement Based on the MTI/CO Protocol,” Journal of Information and Computation Science, vol. 3, no. 3, pp. 575-581, 2006.

[31] Yang Y., Hu Y., Sun C., Lv C., and Zhang L., “An Efficient Group Key Agreement Scheme for Mobile Ad-Hoc Networks,” The International Arab Journal of Information Technology, vol. 10, no. 1, pp. 10-17, 2013.

[32] Yu Q., Li J., and Zhang Y., “Leakage-Resilient Certificate-Based Encryption,” Security and Communication Networks, vol. 8, no. 18, pp. 3346-3355, 2015.

[33] Yu Q., Li J., Zhang Y., Wu W., Huang X., and Xiang Y., “Certificate-based Encryption Resilient to Key Leakage,” Journal of Systems and Software, vol. 116, pp. 101-112, 2016.

[34] Zhang L., Zhang F., Wu Q., and Domingo-Ferrer J., “Simulatable Certificateless Two-Party Authenticated Key Agreement Protocol,” Information Sciences, vol. 180, no. 6, pp. 1020- 1030, 2010. A Certificate-Based AKA Protocol Secure Against Public Key Replacement Attacks 765 Yang Lu received the Ph.D. degree from PLA University of Science and Technology in 2009. He has been working in HoHai University from 2003. Currently, he is an Associate Professor in College of Computer and Information Engineering. His major research interests include information security and cryptography, network security and cloud security, etc. He has published more than 50 scientific papers in international conferences and journals. Quanling Zhang has been studying in HoHai University from 2013. Currently, he is a postgraduate student in College of Computer and Information Engineering. His major research interests include information security and cryptography. Jiguo Li received the Ph.D. degree from Harbin Institute of Technology in 2003. He has been working in HoHai University from 2003. Currently, he is a Professor in College of Computer and Information Engineering. His major research interests include information security and cryptography, network security, wireless security etc. He has published more than 100 scientific papers.