Certificateless cryptography  is a new paradigm that not only removes the inherent key escrow problem of identity based public cryptography  (ID-PKC for short), but also eliminates the cumbersome certificate management in traditional PKI. In CL-PKC, the actual private key of a user is comprised of two secrets: a secret value and a partial private key. The user generates a secret value by himself, while the partial private key is generated by a third party called Key Generating Center (KGC), who makes use of a system wide master key and the user’s identity information. In this way, the key escrow problem in identity-based public key cryptosystems is removed. A user’s public key is derived from his/her actual private key, identity and system parameters. It could be available to other entities by transmitting along with signatures or by placing in a public directory. Unlike the traditional PKI, there is no certificate in certificateless public key cryptography to ensure the authenticity of the entity’s public key. A number of certificateless signature schemes [3–14] have been proposed. Some of them are analysed under reasonable security models with elaborate security proofs [8, 11, 13, 14], while some others are subsequently broken due to flawed security proof or unreasonable model [3, 6–8, 12].