Paper 2007/236

Certificateless Ring Signatures

Sherman S. M. Chow and Wun-She Yap

Abstract

Ring signature scheme is a cryptographic construct that enables a signer to sign on behalf of a group of $n$ different people such that the verifier can only ensure someone in the group signed, but not exactly whom. Ring signatures are utilized in many security applications. It is tricky to deploy multi-user cryptographic construct due to the complexity involved by certificates. Specifically, ring signatures working under traditional public key infrastructure requires the transfer and verification of $n$ certificates, making the scheme both space and time inefficient. On the other hand, the key-escrow problem of identity-based solution makes the authenticity of the ring signature in question. This paper studies ring signature in certificateless cryptography, one with neither certificate nor key-escrow. Designing a certificateless ring signature scheme is not entirely trivial. Many certificateless signatures require public key validity checking. In the context of ring signatures, this means both the signer and the verifier need to deal with the complexity in the verification of $n$ public keys. We propose the first certificateless ring signature scheme, without such public key validity checking.

Note: The authors would like to thank the anonymous reviewer of UASS '07 for his/her comment. The presentation of this paper has been improved for readers who may not be familiar with Sakai-Kasahara identity-based crpyosystem, the study of $k$-CAA problem and malicious KGC attack.