Visible to the public Accumulators with Applications to Anonymity-Preserving Revocation

TitleAccumulators with Applications to Anonymity-Preserving Revocation
Publication TypeConference Paper
Year of Publication2017
AuthorsBaldimtsi, F., Camenisch, J., Dubovitskaya, M., Lysyanskaya, A., Reyzin, L., Samelin, K., Yakoubov, S.
Conference Name2017 IEEE European Symposium on Security and Privacy (EuroS P)
Keywordsaccumulators, Additives, anonymity, anonymity-preserving revocation, anonymous credential systems, anonymous credentials, anonymous revocation component, ARC, authentication, Braavos construction, communication complexity, Complexity theory, composability, cryptographic applications, cryptography, Heuristic algorithms, Human Behavior, membership revocation, message authentication, Metrics, optimal communication complexity, Plugs, pubcrawl, public key cryptography, resilience, Resiliency, revocation, revocation functionality, RSA-based dynamic accumulator, theorem proving, user authentication, zero-knowledge proofs

Membership revocation is essential for cryptographic applications, from traditional PKIs to group signatures and anonymous credentials. Of the various solutions for the revocation problem that have been explored, dynamic accumulators are one of the most promising. We propose Braavos, a new, RSA-based, dynamic accumulator. It has optimal communication complexity and, when combined with efficient zero-knowledge proofs, provides an ideal solution for anonymous revocation. For the construction of Braavos we use a modular approach: we show how to build an accumulator with better functionality and security from accumulators with fewer features and weaker security guarantees. We then describe an anonymous revocation component (ARC) that can be instantiated using any dynamic accumulator. ARC can be added to any anonymous system, such as anonymous credentials or group signatures, in order to equip it with a revocation functionality. Finally, we implement ARC with Braavos and plug it into Idemix, the leading implementation of anonymous credentials. This work resolves, for the first time, the problem of practical revocation for anonymous credential systems.

Citation Keybaldimtsi_accumulators_2017