Abstract: Based on the bilinear pairing, an improved certificateless signature scheme is presented to overcome the Yap-Heng-Goi scheme’s drawback that it is vulnerable to public key replacement attacks. This proposed scheme uses a short signature to generate the user’s partial private key which straightly constructs the private key with the secret value chosen by the user. Two Hash functions are used to generate signatures in the signature algorithm. The correction of the public key can be checked implicitly by verifying the signature, and thus the Yap-Heng-Goi scheme’s security problem is solved. In the proposed scheme, no pairing computation is needed in the signing algorithm and the verification algorithm requires only three pairings computations. A security analysis shows that the proposed scheme is proved secure against existential forgery on an adaptively chosen message attack under the assumption of Computational Diffie-Hellman in the random oracle model.

Key words: bilinear pairing, certificateless signature, random oracle model