Paper 2020/657

Traceable Attribute-Based Anonymous Credentials

Chloé Hébant and David Pointcheval

Abstract

Many attribute-based anonymous credential (ABC) schemes have been proposed allowing a user to prove the possession of attributes, anonymously. They became more and more practical with, for the most recent papers, a constant-size credential to show a subset of attributes issued by a unique credential issuer. However, proving possession of attributes coming from $K$ different credential issuers usually requires $K$ independent credentials to be shown. Only attribute-based credential schemes from aggregatable signatures can overcome this issue. In this paper, we propose new ABC schemes from aggregatable signatures with randomizable tags. We consider malicious credential issuers, with adaptive corruptions and collusions with malicious users. Whereas our constructions only support selective disclosures of attributes, our approach significantly improves the complexity in both time and memory of the showing of multiple attributes: for the first time, the cost for the prover is (almost) independent of the number of attributes \emph{and} the number of credential issuers. Moreover, we propose the first schemes allowing traceability in case of abuse of credentials. We formally define an aggregatable signature scheme with (traceable) randomizable tags, which is of independent interest. We build concrete schemes from linearly homomorphic signatures. As all the recent ABC schemes, our constructions are proven in the bilinear generic group model.