Malicious KGC attacks in certificateless cryptography

ABSTRACT

Identity-based cryptosystems have an inherent key escrow issue, that is, the Key Generation Center (KGC) always knows user secret key. If the KGC is malicious, it can always impersonate the user. Certificateless cryptography, introduced by Al-Riyami and Paterson in 2003, is intended to solve this problem. However, in all the previously proposed certificateless schemes, it is always assumed that the malicious KGC starts launching attacks (so-called Type II attacks) only after it has generated a master public/secret key pair honestly. In this paper, we propose new security models that remove this assumption for both certificateless signature and encryption schemes. Under the new models, we show that a class of certificateless encryption and signature schemes proposed previously are insecure. These schemes still suffer from the key escrow problem. On the other side, we also give new proofs to show that there are two generic constructions, one for certificateless signature and the other for certificateless encryption, proposed recently that are secure under our new models.

REFERENCES

• 1: S. S. Al-Riyami and K. G. Paterson. Certificateless public key cryptography. In Proc. ASIACRYPT 2003, pages 452--473. Springer-Verlag, 2003. LNCS 2894.
• 2: S. S. Al-Riyami and K. G. Paterson. CBE from CL-PKE: A generic construction and efficient schemes. In 8th International Workshop on Theory and Practice in Public Key Cryptography (PKC 2005), pages 398--415. Springer, 2005. LNCS 3386.
• 3: J. Baek, R. Safavi-Naini, and W. Susilo. Certificateless public key encryption without pairing. In 8th Information Security Conference (ISC'05), pages 134--148. Springer, 2005. LNCS 3650.
• 4: M. Bellare, C. Namprempre, and G. Neven. Security proofs for identity-based identification and signature schemes. In Proc. EUROCRYPT 2004, pages 268--286. Springer-Verlag, 2004. LNCS 3027 (Full paper is available at Bellare's homepage URL: http://www-cse.ucsd.edu/users/mihir).
• 5: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 6: K. Bentahar, P. Farshim, J. Malone-Lee, and N. P. Smart. Generic construction of identity-based and certificateless KEMs. Cryptology ePrint Archive, Report 2005/058, 2005. http://eprint.iacr.org/2005/058.
• 7: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 8: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 9: Z. H. Cheng and R. Comley. Efficient certificateless public key encryption. Cryptology ePrint Archive, Report 2005/012, 2005. http://eprint.iacr.org/2005/012.
• 10: A. W. Dent. A survey of certificateless encryption schemes and security models. Cryptology ePrint Archive, Report 2006/211, 2006. http://eprint.iacr.org/2006/211.
• 11: Eiichiro Fujisaki , Tatsuaki Okamoto, Secure Integration of Asymmetric and Symmetric Encryption Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.537-554, August 15-19, 1999
• 12: D. Galindo, P. Morillo, and C. Ràfols. Breaking Yum and Lee generic constructions of certificate-less and certificate-based encryption schemes. In 3rd European PKI Workshop: Theory and Practice (EuroPKI 2006), pages 81--91. Springer, 2006. LNCS 4043.
• 13: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 14: B. C. Hu, D. S. Wong, Z. Zhang, and X. Deng. Key replacement attack against a generic construction of certificateless signature. In Information Security and Privacy: 11th Australasian Conference, ACISP 2006, pages 235--246. Springer-Verlag, 2006. LNCS 4058.
• 15: X. Huang, W. Susilo, Y. Mu, and F. Zhang. On the security of certificateless signature schemes from Asiacrypt 2003. In Cryptology and Network Security, 4th International Conference, CANS 2005, pages 13--25. Springer-Verlag, 2005. LNCS 3810.
• 16: X. Li, K. Chen, and L. Sun. Certificateless signature and proxy signature schemes from bilinear pairings. Lithuanian Mathematical Journal, 45(1):76--83, 2005.
• 17: B. Libert and J.-J. Quisquater. On constructing certificateless cryptosystems from identity based encryption. In 9th International Conference on Theory and Practice in Public Key Cryptography (PKC 2006), pages 474--490. Springer, 2006. LNCS 3958.
• 18: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 19: D. H. Yum and P. J. Lee. Generic construction of certificateless encryption. In ICCSA '04, pages 802--811. Springer, 2004. LNCS 3043.
• 20: D. H. Yum and P. J. Lee. Generic construction of certificateless signature. In Information Security and Privacy: 9th Australasian Conference, ACISP 2004, pages 200--211. Springer-Verlag, 2004. LNCS 3108.
• 21: D. H. Yum and P. J. Lee. Identity-based cryptography in public key management. In EuroPKI'04, pages 71--84. Springer, 2004. LNCS 3093.
• 22: Z. Zhang, D. Wong, J. Xu, and D. Feng. Certificateless public-key signature: Security model and efficient construction. In 4th International Conference on Applied Cryptography and Network Security (ACNS 2006), pages 293--308. Springer, 2006. LNCS 3989.