In this paper we revisit the security models of certificatelesssignatures and propose two new constructions which are provably securein the random oracle model. We divide the potential adversaries accordingto their attack power, and for the first time, three new kinds of adversariesare introduced into certificateless signatures. They are NormalAdversary, Strong Adversary and Super Adversary (ordered by their attackpower). Combined with the known Type I Adversary and TypeII Adversary in certificateless system, we then define the security ofcertificateless signatures in different attack scenarios. Our new models,together with the others in the literature, will enable us to better understandthe security of certificateless signatures. Two concrete schemeswith different security levels are also proposed in this paper. The firstscheme, which is proved secure against Normal Type I and Super TypeII Adversary, enjoys the shortest signature length among all the knowncertificateless signature schemes. The second scheme is secure against SuperType I and Type II adversary. Compared with the scheme in ACNS2006 which has a similar security level, our second scheme requires loweroperation cost but a little longer signature length.