CRSet: Private Non-Interactive Verifiable Credential Revocation
Felix Hoops, Jonas Gebele, Florian Matthes · 2025
Read CRSet: Private Non-Interactive Verifiable Credential Revocation by Felix Hoops, Jonas Gebele, Florian Matthes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17089.txt.
Introduction
Felix Hoops, Jonas Gebele, and Florian Matthes present CRSet, a private way to cancel digital credentials without leaking who issued them. Past cancel lists can reveal a firm's churn, like staff loss from canceled work badges. Their method hides issuer acts by design.
Issuers pack cancel data in blobs and post them on a public chain for safe storage. Checkers fetch the data and test a credential at home, with no calls out. No wallet or talk rules need to change, which eases uptake. Tests match the math, and one blob holds data for a vast count of credentials.
Catalog record
| CREATOR | Felix Hoops, Jonas Gebele, Florian Matthes |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-17089
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CRSet: Private Non-Interactive Verifiable Credential Revocation Felix Hoops, Jonas Gebele, Florian Matthes Abstract Like any digital certificate, Verifiable Credentials (VCs) require a way to revoke them in case of an error or key compromise. Existing solutions for VC revocation, most prominently Bitstring Status List, are not viable for many use cases because they may leak the issuer’s activity, which in turn leaks internal business metrics. For instance, staff fluctuation through the revocation of employee IDs. We identify the protection of issuer activity as a key gap and propose a formal definition for a corresponding characteristic of a revocation mechanism. Then, we introduce CRSet, a non-interactive mechanism that trades some space efficiency to reach these privacy characteristics. For that, we provide a proof sketch. Issuers periodically encode revocation data and publish it via Ethereum blob-carrying transactions, ensuring secure and private availability. Relying Parties (RPs) can download it to perform revocation checks locally. Sticking to a non-interactive design also makes adoption easier because it requires no changes to wallet agents and exchange protocols. We also implement and empirically evaluate CRSet, finding its real-world behavior to match expectations. One Ethereum blob fits revocation data for about 170,000 VCs. 1 Introduction Self-Sovereign Identity (SSI) [ 2 ] is gaining traction as a user-centric approach to digital identity, offering tangible benefits in security and efficiency. Government-led initiatives like the European Blockchain Service Infrastructure and the U.S. Department of Homeland Security are already working on SSI-based systems for issuing digital credentials like diplomas [ 9 ] and immigration records [ 31 ] . Verifiable Credentials (VCs)are digitally signed, structured data objects used to represent attestable claims such as identity documents, professional licenses, or organizational roles [ 30 ] . As with any credential system, the ability to revoke previously issued VCsis essential to correct errors, respond to key compromise, or reflect changes in status. Revocation, however, remains poorly addressed in the SSIecosystem [ 21 , 26 , 27 ] . No existing solution protects issuers from leaking operational information such as the number or timing of revocations. This missing capability poses a significant barrier to adoption. Organizations issuing revocable VCstoday risk exposing sensitive internal data. Most mechanisms reveal each revocation publicly, enabling observers to infer patterns such as employee departures when VCsare used for access or staff credentials. Conventional mechanisms from public-key infrastructures like Certificate Revocation List (CRL)or the Online Certificate Status Protocol (OCSP)are equally problematic. They either expose aggregate revocation counts [ 4 ] or leak usage metadata during verification [ 11 ] , making them unsuitable for SSI’s privacy requirements. OCSPstapling is closest, but it still leaks when a credential is intended to be used. The most widely used SSI-native mechanisms also fall short. The W3C Bitstring Status List (BSL) [ 17 ] compresses revocation data efficiently but makes individual revocations observable. Hyperledger Anonymous Credentials (AnonCreds)Revocation [ 8 ] offers subject anonymity, but still discloses issuer-level revocation information through public accumulator data. Table 1: Comparison of Credential Revocation Mechanisms for SSI Mechanism Revocation Data Subject Privacy RP Privacy Issuer Privacy Non-Interactive Bitstring Status List <1 bit/cap. PIR 1 1 1 Private Information Retrieval No Rate 2 2 2 Revocation Rate Hiding Yes AnonCreds Rev. >12 B/cap. PIR Yes No No Prevoke [ 19 ] ? Yes Yes Rate No Evoke [ 20 ] \geq 32 B/rev. Yes Depends 3 3 3 Depends on the exact workings of the used gossip protocol. Rate No Sitouah et al. [ 29 ] \geq 2 B/valid 4 4 4 Practical measurement from paper for parameterization with at least 10^{5} capacity. Yes Yes Rate No CRSet \approx 6 bit/cap. Yes Yes Yes Yes We introduce Credential Revocation Set (CRSet), a revocation mechanism for non-anonymous credentials that require strong protection of issuer activity. CRSet uses Bloom filter cascades [ 16 ] combined with fixed-size padding and a regular publishing schedule to conceal both the total number and frequency of revocations. It enables revocation checks without active participation of issuers, and without exposing metadata, ensuring privacy for issuers, Relying Partys (RPs), and credential holders alike. No prior revocation mechanism we are aware of protects absolute and relative issuer activity to the level that CRSet does. We provide a high-level comparison of CRSet and other existing SSI-native revocation mechanisms in Table 1 . Our contributions are: • We provide a structured analysis of privacy concerns in credential revocation mechanism within SSIecosystems, with a focus on issuers. We formalize issuer privacy using a game-based definition of activity indistinguishability. • We introduce CRSet, a space-efficient, non-interactive status revocation mechanism that improves metadata privacy for issuers, RPs, and subjects. We prove that CRSet satisfies the defined issuer privacy properties. • We implement both a standalone prototype of the CRSet data structure and a complete end-to-end demonstrator. Our empirical evaluation confirms CRSet’s privacy properties and analyzes performance and scalability. The remainder of this paper is organized as follows: First, we perform a brief survey of related research work in Section 2 . Next, in Section 3 , we describe stakeholders and privacy concerns before setting goals and reflecting on possible underlying data structures. Then, we present the CRSet design in Section 4 , covering data structure and publishing. In Section 5 , we introduce a formal definition for an issuer’s privacy along with notation and a proof sketch showing that CRSet meets that level of privacy. In Section 6 , we implement and empirically evaluate CRSet, before coming to a conclusion in Section 7 . 2 Related Work The arguably most notable revocation mechanism for VCsis the W3C’s Bitstring Status List (BSL) [ 17 ] . As the name suggests, it is a bitstring of pre-allocated length. Every issued VCis associated with a unique index, which can be set to one to revoke it. Since most values will typically be zero, GZIP compression is applied to great effect before publicly hosting it on the internet. RPsfetch a full status list for a local revocation check, which creates some level of private information retrieval. However, when checking a VC, the RPwill notify the corresponding issuer that it is doing so when fetching from the issuer’s server. BSLalso reveals every individual revocation an issuer makes. The only other practically relevant mechanism is one tailored to Hyperledger’s AnonCredscredential standard [ 8 ] . AnonCreds’ focus is to enable subjects to interact with RPswhile staying anonymous, which requires anonymous revocation checks. An approach based on a cryptographic accumulator is used. Subjects have to interactively construct a zero-knowledge proof (ZKP) of inclusion in that accumulator, which can be verified by an RP. Inclusion signifies that a VChas not been revoked. But once again, this mechanism has privacy issues. The ZKP relies on a public set of prime numbers (i.e., a tails file), where one prime is associated with each issued credential. Due to the immense size, this file is usually on a web server owned by the issuer, making access trackable. In addition, the ZKP construction requires knowing which of these primes belong to revoked credentials. That information is also public in the form of what is effectively a bitstring using a one to indicate revocation. Although the exact implementation can vary (e.g., expressed as deltas), the information is present and