Certificate-Based Signature: Security Model and Efficient Construction

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. In addition, it also solves the inherent key escrow problem

in the identity-based cryptography. In this paper, we first introduce

a new attack called the Key Replacement Attack in the certificatebased

system and refine the security model of certificate-based signature.

We show that the certificate-based signature scheme presented by Kang,

Park and Hahn in CT-RSA 2004 is insecure against key replacement attacks.

We then propose a new certificate-based signature scheme, which

is shown to be 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 scheme enjoys shorter signature length and less operation

cost, and hence, our scheme outperforms the existing schemes in

the literature