Affiliations: [a] College of Computer and Information Engineering, Hohai University, Nanjing, 210098, P. R. China. E-mail: lijiguo@hhu.edu.cn | [b] Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Australia. E-mails: xh068@uow.edu.au, ymu@uow.edu.au, wsusilo@uow.edu.au | [c] School of Computer Science and Technology, Wuhan University, Wuhan, 430072, P. R. China. E-mail: qhwu@xidian.edu.cn | [d] Department of Computer Engineering and Mathematics, University Rovira i Virgili, Tarragona, Catalonia
Note: [*] This is the extended version of the paper “Certificate-based signature: Security models and efficient construction” appeared in EuroPKI’07. This work is supported by the National Natural Science Foundation of China (No. 60842002, 60673070), the National High-Tech Research and Development Plan of China under Grant (No. 2007AA01Z409), Hohai, Jiangsu and China Planned Projects for Postdoctoral Research Funds.
Abstract: In Eurocrypt 2003, Gentry introduced the notion of certificate-based encryption. The merit of certificate-based encryption lies in the following features: (1) providing more efficient public-key infrastructure (PKI) that requires less infrastructure, (2) solving the certificate revocation problem, and (3) eliminating third-party queries in the traditional PKI. Additionally, it also offers the solution to the inherent key escrow problem in the identity-based cryptography. The contributions of this paper are threefold. Firstly, we introduce a new attack called the “Key Replacement Attack” into the certificate-based signature system and refine the security model of certificate-based signature. Secondly, we show that the certificate-based signature scheme presented by Kang, Park and Hahn in CT-RSA 2004 is insecure against key replacement attacks. Thirdly, we present two new certificate-based signature schemes secure against key replacement attacks. Our first scheme is existentially unforgeable against adaptive chosen message attacks under the computational Diffie–Hellman assumption in the random oracle model. Compared with the certificate-based signature scheme in CT-RSA 2004, our first scheme enjoys shorter signature length and less operation cost. Our second scheme is inspired by Waters signature and is the first construction of certificate-based signature secure against key replacement attacks in the standard model.
