Traceable constant-size multi-authority credentials

Many attribute-based anonymous credential (ABC) schemes have been proposed, enabling users to anonymously prove possession of attributes. Recent papers introduced constant-size credentials issued by a single credential issuer for showing a subset of attributes. However, proving possession of attributes from multiple issuers typically requires independent credentials. Only aggregate signature-based attribute-based credential schemes can overcome this limitation. This paper presents new ABC schemes using aggregate signatures with randomizable tags. The schemes consider malicious credential issuers, adaptive corruptions, and collusions with malicious users. While our constructions only support selective attribute disclosures to remain compact, our approach significantly improves the complexity in time and memory for showing multiple attributes. For the first time, the cost for the prover becomes (almost) independent of the number of attributes and issuers. Whereas anonymous credentials require privacy of the user, we also propose the first schemes allowing traceability by a specific tracing authority.