Attribute-based signatures from RSA

An attribute-based signature with respect to a signing policy, chosen ad hoc by the signer, convinces the verifier that the signer holds a subset of attributes satisfying that signing policy. The verifier must obtain no other information about the identity of the signer or the attributes he holds. This primitive has many applications in real scenarios requiring both authentication and anonymity/privacy properties.We propose in this paper an attribute-based signature scheme which uses RSA-like operations and keys. It is the first such scheme which does not need bilinear pairings. The scheme is proved to enjoy the required properties of privacy and unforgeability in the random oracle model, under well-established computational assumptions. Although we describe and analyze the scheme for threshold signing policies, for the sake of simplicity, it can be easily modified to support more general signing policies. Finally, the scheme admits modifications so that a special entity can identify authors of dishonest signatures, and so that users that are rejected from the system cannot compute more valid signatures. These two last properties are very desirable for real-life applications of attribute-based signatures.