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

Abstract

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.