Constructions of certificate-based signature secure against key replacement attacks

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.