The Revocation Check That Should Not Identify You
At USENIX Security 2026, Kasra EdalatNejad, Sebastian Faust, Jonas Hofmann, Philipp-Florens Lehwalder, and Thomas Schneider proposed an anonymous-credential revocation system built around a primitive called Private Record Certification, or PRC. Its central question is simple to state and difficult to satisfy: how can a holder prove that a credential is still valid without telling the revocation authority which credential they hold? This opening establishes the actors, the stakes, and the three constraints—privacy, freshness, and scale—that the system is designed to balance. Those constraints are the basis for judging what PRC contributes and where its assumptions begin.
Revocation is a second decision about a credential
Issuance and revocation answer different questions. When an issuer creates a digital credential, they attest that certain facts were true or that the holder was entitled to receive it. Revocation asks whether that credential should still be accepted later. The answer can change because a credential was lost, stolen, misused, or tied to conduct that makes it invalid. A verifier therefore needs more than a signature proving that the credential once existed; they need a current status decision.
That decision can create a privacy problem of its own. Consider an anonymous age credential used to enter an establishment. The verifier should learn only the fact needed for the transaction, such as whether the holder meets an age threshold. If checking the credential sends a stable identifier or a one-to-one status URL to its issuer, the issuer may be able to correlate the holder, time, and context of the interaction. A system meant to prevent cross-context linkability would then reintroduce a trace through its revocation mechanism.
The difficulty is not merely that an issuer might learn a status. A conventional lookup can reveal that a particular credential is being used at all, and repeated lookups can create a usage history. Anonymous credentials are designed to make separate presentations difficult to link, so a revocation check that exposes the credential's identity defeats an important part of the credential's purpose. Yet omitting the check creates a different danger: a credential that has been revoked remains usable.
The PRC proposal treats this as a systems problem rather than as a choice between privacy and accountability. The authorities should be able to enforce a status change—for example, to stop a fraudulent professional credential from being accepted—without turning every legitimate presentation into a report about the holder. The holder, meanwhile, needs a way to obtain evidence of current validity without revealing the database row that corresponds to their credential.
Four parties divide the information
The proposed system has four distinct roles. An issuer creates an anonymous credential. A client, or holder, keeps that credential and wants to use it. A verifier checks the credential before providing a service or granting access. Finally, a group of decentralized revocation authorities jointly maintains a replicated database of credential status.
This division matters because each party needs different information. The issuer knows the credential at issuance, but the revocation interaction should not become a new tracking channel. The holder knows which credential they possess and can ask whether it is valid. The verifier needs a trustworthy yes-or-no result, but should not need to learn the holder's hidden revocation index. The authorities maintain the status records, yet should not learn which record a holder has asked about.
The paper uses an index to connect these views. A credential contains a private attribute that identifies its position in the authorities' status database. The holder can use that index internally, but does not disclose it during the revocation request or the later presentation. The database records whether the credential is currently valid. The PRC protocol is intended to let the authorities certify the record at that hidden index without learning which index was selected.
There is a second privacy surface as well. Hiding a request from the authorities does not automatically stop a dishonest client from asking about somebody else's record. The paper therefore distinguishes revocation unlinkability, which protects the holder's interaction with the authorities, from database privacy, which restricts clients to records for which they hold authorization. The basic construction addresses the former; an extension adds an authorization credential and a zero-knowledge proof for the latter.
These are different risks. One concerns what an authority can infer from a legitimate query. The other concerns what a client can learn by making illegitimate queries. Treating both as “privacy” without separating them would make the system's guarantees sound broader than they are.
The status database itself is not necessarily hidden from the authorities that operate it. They need to maintain the records and apply revocations. What they should not learn from an individual request is which row the holder selected, what status the holder is testing, or which verifier will later receive the credential. That distinction is important: PRC is designed to protect the privacy of a query against the database operator, not to pretend that the operator has no access to the database they are responsible for maintaining.
The authorities are distributed to avoid making one organization the sole observer of those queries. In the paper's any-trust model, privacy can survive the compromise of all but one authority, and the holder does not need to know which authority is the honest one. This makes institutional separation part of the privacy design. It does not mean that several servers automatically provide anonymity: if every authority colludes, the hidden query can be reconstructed. Nor does it mean that the authorities are harmless if they actively deviate from the protocol. The paper treats privacy and correctness as related but distinct properties, with different assumptions behind each.
The diagram captures the intended information flow, not a claim that every channel is automatically safe. The paper assumes confidentiality and integrity for communication channels, such as TLS, and excludes side-channel attacks from its model. A real deployment would therefore have to protect the network and the surrounding operational systems as carefully as the cryptographic protocol protects the index.
Three requirements pull in different directions
First is privacy. The holder should not become linkable across presentations merely because they request a fresh status. The authorities should not learn the holder's attributes, validity, or the verifier with whom the credential will be used. Privacy also includes the status database itself: a client should not be able to discover the status of credentials they do not own.
Second is freshness. The paper targets an on-demand setting in which a holder requests a new non-revocation token immediately before each presentation. The token carries auxiliary information such as a timestamp, and the verifier applies an application-specific validity limit. A revocation can then take effect after the database changes instead of waiting for a long epoch to end. The trade-off is direct: a short validity window reduces the opportunity to use a revoked credential, but it makes network access part of the presentation experience.
In this model, “real time” does not mean that every verifier continuously watches every credential. It means that the next status request is evaluated against a database that can change dynamically, and that an old token is not meant to remain acceptable indefinitely. If a holder has no connection to the authorities, they may not be able to obtain a fresh token. The paper describes an offline-client extension in which a verifier performs the authority interaction on the holder's behalf, but that changes who must be online and leaves the holder unable to detect the failed status locally before presenting. Freshness is therefore a system policy involving timestamps, reachability, and acceptable delay, not a property delivered by a signature in isolation.
Third is scale and efficiency. The paper frames its target as nationwide deployment exceeding 100 million users, while its prototype evaluates databases above one billion credentials. Mobile clients and constrained networks cannot be expected to download or process a database-sized object for every presentation. Nor can a verifier be asked to perform a large non-membership proof each time a credential is used.
Scale also has several dimensions. A design may make the status update cheap but make every holder download a large witness; it may reduce client traffic while requiring expensive work at the authorities; or it may look efficient only because updates are batched into epochs. PRC shifts much of the work toward the authorities, where repeated interactions and shared preprocessing can be engineered, while keeping the holder's request small. That is a meaningful architectural choice, but it means the system's reported scale must be read together with server computation, communication among authorities, and the number of authorities that must be available. “Continental scale” is not a single measurement independent of those choices.
Existing mechanisms emphasize different points in this triangle. Dynamic accumulators can make revocation witnesses stale and require updates. Blacklist approaches can make proving non-membership expensive. Epoch-based designs can reduce update frequency, but leave a period during which a revoked credential may still be accepted. A public status list can distribute many statuses efficiently, but its privacy depends on how identifiers, fetches, caches, list size, and monitoring are handled.
The W3C Bitstring Status List illustrates that last approach. It packages many credential statuses into a compressible bitstring and recommends group privacy, caching, content-distribution networks, or Oblivious HTTP to reduce tracking through retrieval. That is a useful and privacy-aware design for verifiable credentials. It is not the same privacy boundary as PRC. A status list primarily asks how to publish and retrieve a shared status artifact without unnecessary correlation. PRC asks how authorities can certify a particular, hidden database record on demand and how the holder can bind that certificate to an anonymous presentation.
The difference is not a contest between a private system and a public one. A shared list can make any one credential harder to isolate, and its holder may staple a signed list to a presentation so the verifier does not have to contact the issuer. But the list still has an index and a publication endpoint whose size, update pattern, identifiers, and access logs affect privacy. The W3C specification explicitly discusses these risks, including the possibility that a verifier who learns a holder's list entry can monitor later changes. PRC starts from a stronger per-query requirement: the authority should not learn which entry is being certified. It consequently accepts a different operational shape, including live interaction and dependence on a set of cooperating authorities.
The proposed answer is private certification
PRC's promise can be stated without cryptographic notation. The holder asks the revocation authorities to certify the record at a secret index. The authorities jointly process a concealed query and return a signed certificate. The holder can check that certificate against the status they expect—for revocation, the valid value—and then prove to the verifier that the certificate refers to the same hidden index contained in the anonymous credential.
That approach changes the object being exchanged. The holder is not asking the authorities to reveal a public identity, and the authorities are not simply publishing an answer that names a credential. They are producing evidence that a hidden index currently has a particular value. Later chapters will examine how PRC constructs that evidence, how it becomes a fresh non-revocation token, and what the prototype measurements actually establish.
The promise should be read with its conditions attached. The system relies on decentralized authorities in an any-trust model: privacy is preserved as long as at least one authority remains honest and does not collude with the others. The paper also acknowledges that actively malicious authorities can affect correctness or forge tokens under the described assumptions, and that the prototype does not implement the TLS and certificate-management work required in deployment. PRC is therefore not a claim that privacy, revocation, and infrastructure cost disappear. It is a proposal for moving their boundary: keep the index hidden from the authorities, keep the proof unlinkable to the verifier, and pay for freshness through a tightly bounded interaction.
The unresolved question is now precise. Which existing revocation mechanisms protect a holder but leave an identifier, a fetch pattern, an update burden, or a delay behind—and what must a private certificate do differently to avoid those compromises?