Ongoing research seeks for efficient and fair solutions that correctly balance access control and privacy requirements in anonymous authentication [6, 9, 3]. A basic goal from the point of view of a user, is authenticating to a service, without revealing the user identity (user untraceability) and without allowing the linkage of different accesses (transaction unlinkability). Another requirement for the user is non-frameability, ie, it should not be possible for anyone, even a collaboration of entities, to successfully simulate an anonymous access that opens back to an innocent user. From the point of view of the service provider, a goal is preventing users from transferring or sharing their credentials with others (non-transferability), from using a one-show credential more than once (nonreusability), but also establishing accountability when users behave dishonestly. In such cases it may be required to trace a transaction (anonymity revocation) and/or revoke all the anonymous credentials of a user (credential revocation).