A short certificate-based signature scheme with provable security

Certificate-based signature (CBS) is an attractive paradigm since it simultaneously solves the certificate revocation problem in conventional signatures and the key escrow problem in ID-based signatures. In particular, short certificate-based signatures are useful in bandwidth reduction for communication due to their short signature lengths. However, it is still a challenging and open problem to design a secure short certificate-based signature (SCBS) scheme. Recently, to solve this problem, Li et al. proposed an efficient SCBS scheme. However, in this article, we will show that Li et al.’s scheme is insecure against Type I adversary (i.e. uncertified entity) under an accredited security model. Moreover, we propose a new SCBS scheme with provable security. Based on the computational Diffie–Hellman (CDH) assumption, we demonstrate that our SCBS scheme possesses existential unforgeability against adaptive chosen-message attacks under the same accredited security model. When compared with previous SCBS schemes, our scheme is the first provably secure SCBS scheme while retaining efficiency.