An attribute-based digital signature system comprises a signature generation unit (1) for signing a message (m) by generating a signature (σ) based on a user secret key (SK) associated with a set of user attributes, wherein the signature generation unit (1) is arranged for combining the user secret key (SK) with revocation data (R) to form at least part of the signature (σ), wherein the revocation data (R) complements respective ones of a plurality of valid user secret keys and wherein the revocation data (R) prevents a revoked user secret key (SK) from being used to validly sign a message (m) with the set of user attributes. The system further comprises a revocation unit (2) for selectively removing at least part of the signing capability of a to-be-revoked user secret key (SK), by generating updated revocation data (R), wherein the updated revocation data (R) is based on at least part of the to-be-revoked user secret key (SK). A plurality of attribute authorities 301 may independently issue cryptographic keys.