Cryptanalysis and improvement of a pairing-free certificateless signature scheme

Certificateless signature (CLS) schemes aim to eliminate the need of certificates in traditional public-key signature schemes and also to resolve the inherent key-escrow problem of identity-based signature schemes. There are a vast number of secure CLS schemes in the literature; however, the usage of map-to-point hash functions and bilinear pairings in their constructions makes them less efficient to be applicable in many real-world applications. Recently, Karati et al. proposed an elliptic curve based CLS scheme in which there exists neither any bilinear pairing nor any map-to-points hash function. The authors claimed that the proposed CLS scheme is existentially unforgeable against both types of adversaries considered in certificateless cryptography. However, in this paper, we show that this claim is wrong and a type-1 adversary of certificateless cryptography can forge the signature of any signer on any message of his choice in this scheme. We further slightly modify Karati et al.’s scheme in order to make it secure in the standard security model of a CLS scheme. Meanwhile, the proposed improved scheme preserves all the efficiency properties of Karati et al.’s scheme.