Paper 2013/193

Certificateless Signatures: Structural Extensions of Security Models and New Provably Secure Schemes

Yu-Chi Chen, Raylin Tso, Willy Susilo, Xinyi Huang, and Gwoboa Horng


Certificateless signatures (CLSs) were introduced to solve the key escrow problem of identity-based signatures. In CLS, the full private key is determined by neither the user nor the trusted third party. However, a certificate of a public key is not required in CLS schemes; therefore, anyone can replace the public key. On the formal security, there are two types of adversaries where the Type I adversary acts as the outsider, and the Type II as the key generation center. Huang et al. took a few security issues into consideration and provided some security models. They showed three kinds of Type I adversaries with different security levels. Moreover, Tso et al. found the existence of another Type I adversary that was not discussed by Huang et al.; however, the adversaries are still too subtle to be presently defined. In this paper, we further consider public key replacement and strong unforgeability in certificateless signatures. All feasible situations are revisited along with abilities of adversaries. Additionally, structural extensions of security models are proposed with respect to the described public key replacement and strong unforgeability. Moreover, we also present some schemes, analyze their security against different adversaries, and describe our research results. Finally, one of the proposed certificateless short signature schemes is proven to achieve the strongest security level.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Certificateless signatureSecurity modelPublic key replacementStrong unforgeability
Contact author(s)
wycchen @ ieee org
2013-06-28: revised
2013-04-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yu-Chi Chen and Raylin Tso and Willy Susilo and Xinyi Huang and Gwoboa Horng},
      title = {Certificateless Signatures: Structural Extensions of Security Models and New Provably Secure Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2013/193},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.