Certificateless Signatures: New Schemes and Security Models

We present a study of security in certificateless signatures. We divide potential adversaries according to their attack power, and for the first time, three new kinds of adversaries are introduced into certificateless signatures. They are Normal Adversary, Strong Adversary and Super Adversary (ordered by their attack power). Combined with the known Type I Adversary and Type II Adversary in certificateless cryptography, we then define the security of certificateless signatures in different attack scenarios. Our new security models, together with others in the literature, provide a clear definition of the security in certificateless signatures. Two concrete schemes with different security levels are also proposed in this paper. The first scheme, which is proven secure (in the random oracle model) against Normal Type I and Super Type II adversaries, has the shortest signature length among all known certificateless signature schemes. The second scheme is secure (in the random oracle model) against Super Type I and Type II adversaries. Compared with another scheme that has a similar security level, our second scheme requires less operational cost but a little longer signature length. Two server-aided verification protocols are also proposed to reduce the verification cost on the verifier.