An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials

By Jan Camenisch, Markulf Kohlweiss, Claudio Soriente. IACR Cryptology ePrint Archive, 2009

319 citations recorded by the source corpus.

The success of electronic authentication systems, be it e-ID card systems or Internet authentication systems such as CardSpace, highly depends on the provided level of user-privacy. Thereby, an important requirement is an efficient means for revocation of the authentication credentials. In this paper we consider the problem of revocation for certificate-based privacy-protecting authentication systems. To date, the most efficient solutions for revocation for such systems are based on cryptographic accumulators. Here, an accumulate of all currently valid certificates is published regularly and each user holds a witness enabling her to prove the validity of her (anonymous) credential while retaining anonymity. Unfortunately, the users' witnesses must be updated at least each time a credential is revoked. For the know solutions, these updates are computationally very expensive for users and/or certificate issuers which is very problematic as revocation is a frequent event as practice shows. In this paper, we propose a new dynamic accumulator scheme based on bilinear maps and show how to apply it to the problem of revocation of anonymous credentials. In the resulting scheme, proving a credential's validity and updating witnesses both come at (virtually) no cost for credential owners and verifiers. In particular, updating a witness requires the issuer to do only one multiplication per addition or revocation of a credential and can also be delegated to untrusted entities from which a user could just retrieve the updated witness. We believe that thereby we provide the first authentication system offering privacy protection suitable for implementation with electronic tokens such as eID cards or drivers' licenses.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/caca92ad18b690f41a756b0f1a01fc29c39a2f79

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Poseidon: A New Hash Function for Zero-Knowledge Proof Systems (2021, background): “Whereas accumulator-based solutions [20, 21] and algebraic Schnorr proofs exist in the area, they are quite involving and thus error-prone, require a trusted setup, are limited in statement language, and are often slow.”
Vector Commitments and Their Applications (2013, background): “It is worth noting that all known constructions of cryptographic accumulators (dynamic and universal) secure without random oracles either work over composite order groups and use expensive operations for mapping set elements to prime numbers [2] [8], or they work in prime order groups but rely on r”
Structure-Preserving Signatures and Commitments to Group Elements (2010, methodology): “There are efficient signature schemes, e.g., [BB04, CL04, BCKL08, CKS09 ], whose verification predicates are pairingproduct equations, but none of them have signatures and messages that exclusively consist of group elements.”