Paper 2026/1189

Do You Need a Receipt? Anonymous Credential Revocation at Continental Scale via Private Record Certification

Abstract

A key challenge in digital credential systems is revocation, that is, the ability to revoke credentials post-issuance and verify their status upon presentation. While anonymous credentials enhance privacy over classical credentials (e.g., by providing unlinkability), they complicate revocation. Existing revocation schemes for anonymous credentials often suffer from high client or verifier computation, long delays before revocation takes effect (e.g., epoch-based settings), or require updates to all users with each revocation. We present an efficient, real-time revocation system for anonymous credentials with decentralized revocation authorities based on a novel primitive called Private Record Certification (PRC). PRC enables users to obtain a certificate for a record stored in a server-managed database without the servers learning which record was requested. This primitive is of independent interest, and we construct it by combining techniques from private information retrieval and secure multi-party computation. Our revocation scheme outsources its costs to the revocation authorities and has minimal overhead for clients and verifiers, while ensuring the communication costs are sublinear in the number of credentials for the revocation authorities. We build a prototype and demonstrate that our system achieves sub-second real-time latency at a scale of over 1 billion credentials, with an online operational cost of 2.5$ per server for processing 1 million PRC queries.

Note: Added artifact appendix & updated references