Why Ordinary Status Lists Do Not Solve Anonymous Revocation
The PRC-based anonymous-credential revocation system becomes clearer when set beside the status mechanisms it is not simply trying to copy. This chapter compares identifier-based checks, anonymous-credential revocation techniques, and the W3C Bitstring Status List by asking the same four questions of each: who learns which fact, how quickly a status change takes effect, who pays the update and computation cost, and whether a holder can prove validity without exposing a stable identity. The result is not a universal ranking. It is a way to see why PRC treats revocation as private certification rather than as the publication of one more list.
The identifier that makes a lookup easy
The ordinary status check has an appealingly simple shape. A credential contains an identifier, or points to a location associated with that identifier. When a verifier wants to know whether the credential is still valid, they send the identifier to an issuer or status service and receive an answer. The identifier solves the central lookup problem: it tells the service exactly which record to read.
It also creates a record of use. If the status endpoint is operated by the issuer, a request may reveal that a particular credential was presented, when it was presented, and—depending on the surrounding network and account information—where or to whom it was presented. Repeated checks can turn a sequence of otherwise unlinkable interactions into a recognizable pattern. The W3C Bitstring Status List specification describes this risk directly: a one-to-one mapping between a credential and a status URL can allow the publisher to correlate the holder, time, and verifier. Caching, content-distribution networks, and Oblivious HTTP can reduce that exposure, but they do not change the fact that the basic lookup uses a link between a credential and its status.
That link is particularly awkward for an anonymous credential. An anonymous credential is not just a credential whose name has been hidden from casual view. Its presentation is designed to reveal selected claims while making different presentations difficult to connect. A verifier might learn that a holder is above a required age without learning a government identifier, or learn that a qualification is valid without receiving a stable handle that can be reused elsewhere. If revocation requires sending that handle to an authority, the status mechanism restores the very connection that the credential presentation was designed to avoid.
The paper's answer is to put a revocation index inside the credential as a private attribute rather than disclose it during use. The index tells the authorities which database position matters, but the holder must be able to use it without revealing it. That changes the requirement from “look up this identifier” to “certify the value at a row that the server cannot identify.” The distinction is the reason the paper says revocation mechanisms based on credential identifiers do not fit anonymous credentials when those identifiers cannot be disclosed.
Earlier anonymous-credential approaches move the privacy boundary in other ways, but each pays for it somewhere. Dynamic accumulators represent a set of valid or revoked credentials in one cryptographic value. A holder keeps a witness and proves membership or non-membership without naming the credential. The difficulty is maintenance: when the accumulator changes, existing witnesses may become invalid. Holders must update them after revocations or obtain fresh witnesses from an authority. A method that avoids public identifiers can therefore create a recurring update burden for every user.
Blacklist-based approaches reverse the set being represented: the system records what must be blocked, and a holder proves that their credential is not on the list. Non-membership proofs can be expensive, particularly when the list changes frequently or must be distributed widely. A sorted collection of signed identifiers can make a proof more compact, but constructing, updating, and distributing that collection remains a cost. The privacy benefit also depends on whether the proof reveals a stable value or lets an authority recognize repeated queries.
Epochs offer another compromise. Instead of handling each revocation immediately, the authority updates a status structure at fixed intervals. Holders can then reuse a token or witness within an epoch, reducing interaction and update traffic. But the interval is also an opportunity window: a credential revoked just after an update may continue to work until the next epoch. Shorter epochs improve freshness but bring back more network and computation work. Longer epochs improve efficiency but weaken the meaning of “revoked now.”
These mechanisms are not failures in every setting. They optimize different constraints. A system that can tolerate a daily status refresh may reasonably choose a different balance from a system that must stop a credential within seconds. The PRC proposal selects the demanding corner: on-demand status checks, small client and verifier costs, and a database that can change at any time. Its design question follows from that selection: can authorities do the expensive private work while returning an object that a holder can use in an anonymous proof?
A fair comparison must therefore follow the credential through time, not just compare the size of one proof. At issuance, who receives a durable identifier or witness? When a status changes, which party must update data? At presentation, does the holder need a network connection, does the verifier contact an issuer, or does an authority learn the request? And after the decision, can any participant recognize the same credential the next time it appears? These questions expose why two systems can both be called privacy-preserving while protecting different observations. An accumulator may hide membership but require a witness refresh. An epoch token may reduce traffic but tolerate a delay. A status list may hide a credential in a large group but still expose a list entry to a verifier. PRC's distinctive target is the authority-side query: the database operator should certify the right record without learning which record was selected.
What a bitstring list solves—and what PRC must still do
The W3C Bitstring Status List is a strong example of a different answer. Instead of creating a separate, large status object for every credential, it puts the status of many credentials into a shared bitstring inside a signed verifiable credential. Each credential carries a status-list index and a reference to the list credential. A verifier retrieves the signed list, expands its compressed representation, and reads the bit at the indicated position.
The sharing is intentional. The specification sets a minimum list length of 131,072 entries, equivalent to 16 KB of uncompressed one-bit values, so that an individual status is placed in a group rather than exposed as a one-to-one object. When most credentials remain valid, long runs of identical bits compress well with GZIP; a list with only a small number of changes can be much smaller than its uncompressed form. The list is also itself a verifiable credential, so a holder can provide it directly to a verifier through “certificate stapling,” avoiding a fresh request to the issuer during presentation.
The list index is meant to be a position, not a second copy of the holder's identity. The specification says that indexes should be assigned randomly so that an observer cannot easily infer when an entry was allocated or how large a group is. It also makes clear that the status-list credential can have a different issuer from the original credential. Those choices reduce unnecessary linkage and allow responsibility for revocation to be separated from responsibility for issuance. They do not make the list anonymous in every context: a verifier that can connect a particular position to a holder may still watch that position as the list changes.
This addresses real privacy and performance problems. A verifier need not contact an issuer for every individual credential. A shared list can be served from a cache or a content-distribution network, and the W3C specification recommends mechanisms such as Oblivious HTTP or an arrangement in which access logs are not available to the issuer's analysts and administrators. The issuer of the original credential and the issuer of the status-list credential may also be different, which can be useful when responsibility for issuance and revocation belongs to different institutions.
But group privacy is not the same as query privacy. The status-list design hides a credential among the population represented by the list; it does not make the verifier's indexed read invisible to every participant in the publication and retrieval path. The index, URL, list size, update pattern, and any global identifier can still create correlation opportunities. The specification advises issuers to avoid unnecessary global identifiers and to make status information selectively disclosable or concealable when the presentation does not require it. It also warns that a verifier who learns a holder's list and entry can monitor later changes to that entry.
The status bit itself illustrates why architecture matters. In the W3C revocation purpose, a set bit expresses a true status such as revoked and an unset bit expresses a valid credential. The PRC paper uses a different convention for its own database: it defines a valid credential as one for which D[idx] = 1. The two conventions are not interchangeable, even though both use binary records. A reader who merges them can invert the meaning of a successful check. More broadly, a status-list entry is a public, indexed representation of status, while a PRC response is a private certificate about a hidden index; similar words do not imply the same mechanism.
The W3C specification does allow more precise retrieval choices. A status-list URL may support a timestamp parameter so that a verifier can ask for the list as it existed at a chosen time. Verifiers are also encouraged to cache lists and use proxies that hide retrieval behavior from the issuer. Those recommendations reveal a design tension rather than eliminate it. A longer validity period and aggressive caching reduce bandwidth and tracking, but may delay recognition of a change. A shorter validity period improves freshness but increases retrieval and availability demands. The W3C document leaves that balance to the credential ecosystem because credential types and regulatory expectations differ.
Imagine a credential being revoked immediately after a verifier's cache was refreshed. A cached list may remain acceptable until its validity period ends, depending on the ecosystem's rules. A holder-stapled list has the same basic question: how recent must the supplied artifact be before the verifier rejects it? The W3C design gives implementers tools for managing that question, but it does not choose one answer for every use case. PRC makes a more aggressive choice by asking for a fresh certificate before presentation. That reduces the intended window for using a revoked credential, yet it also makes the revocation authorities a live dependency on every protected transaction. The difference is a policy and availability decision as much as a data-structure decision.
PRC starts from the opposite side of this boundary. The authorities keep the status database and compute a certificate for the requested row, but the request is secret-shared so they do not learn which row the holder selected. The holder then proves that the certificate corresponds to the hidden index in their anonymous credential. The verifier receives evidence of current validity without receiving the index itself. This is not a claim that PRC makes a public status list unnecessary. It is a claim that a shared list, even a privacy-aware one, does not by itself supply the specific authority-side query privacy required by the paper's anonymous-credential setting.
The practical choice follows from the ecosystem's most sensitive observation. If the verifier can use a shared, cacheable status artifact and the main concern is preventing the issuer from seeing every fetch, a bitstring list combined with careful caching or proxying may fit the need. If the concern is that a revocation authority must not learn which credential is being checked, a public list does not answer the central question, even if it is compressed and signed. Conversely, PRC's stronger query-privacy target is not free: it requires a live authority service, a compatible anonymous-credential proof, and a trust arrangement in which the authorities do not all collude. The comparison should therefore produce a conditional design decision, not a declaration that one mechanism supersedes the other.
The comparison therefore has two axes. One axis asks how much status information is exposed to a verifier and to observers of a public status service. The other asks whether the authority that owns the database can recognize the holder's query. A W3C list can be a sensible choice when group privacy, caching, and holder stapling meet the ecosystem's freshness needs. PRC is aimed at the harder case in which the authority itself must not learn which credential is being checked and the holder needs a fresh, proof-friendly certificate.
Neither choice removes operational responsibility. A malicious issuer could create a one-to-one status list and defeat group privacy. A malicious verifier could share presentation information with an issuer. A small population may offer a weak anonymity set even when the list meets its formal minimum, and detailed status messages can reveal more about a person's process or circumstances than a simple valid/revoked bit. PRC changes the authority-side query, but it still depends on independent authorities, secure channels, and a network path that is available when a fresh token is required.
That leaves a precise capability still to define. A public list can publish many statuses efficiently, and an anonymous credential can hide a holder's identity. PRC must connect those two goals in another way: it must certify a known record at a private index, preserve the binding between the index and the record, and return evidence that can survive a later anonymous presentation. The next question is not how to publish one more list, but what this private certificate actually says.