Vulnerabilities in Anonymous Credential Systems

We show the following:(i)In existing anonymous credential revocation systems, the revocation authority can link the transactions of any user in a subset T of users in O(log|T|) fake failed sessions.(ii)A concern about the DLREP-I anonymous credentials system described in [Stefan Brands: Rethinking public key infrastructure and Digital Certificates; The MIT Press, Cambridge Massachusetts, London England. ISBN 0-262-02491-8] and [Stefan Brands: A Technical Overview of Digital Credentials; February 2002 (was a white paper in credentica.com)].