Private Delegation of (Non-)Membership Proof Updates in Cryptographic Accumulators: Applications to Revocable Anonymous Credentials

Abstract: Anonymous credentials are poised for large-scale deployment worldwide.  In the United States, verifiable digital credentials and mobile driver's licenses are increasingly being developed for privacy-preserving digital identity applications, while the European Union is moving toward the deployment of European Digital Identity Wallets at a scale of approximately 450 million potential users.  A crucial challenge for these deployments is credential revocation.  The main proposed privacy-preserving revocation systems use cryptographic accumulators.  In the envisioned system, whenever a typically resource-constrained client presents their credential, they additionally prove in zero knowledge that their credential has not been revoked by issuing a non-membership proof with respect to the latest accumulator digest of revoked credentials.  However, each revocation changes the accumulator state and can render existing non-membership witnesses stale.  Thus, intermittently connected clients may need to process numerous missed updates before they can present their anonymous credentials.  Computing and updating these non-membership proofs can be computationally intensive.  Naively outsourcing these updates to a server, however, would forfeit the privacy guarantees of the anonymous credential system by revealing information about the credential being updated.  In this presentation, we introduce new privacy-preserving delegation techniques for cryptographic accumulator (non-)membership proofs, enabling scalable and privacy-preserving anonymous credential deployments.  In particular, we construct private proof-delegation protocols for RSA and bilinear accumulators in which the online client cost is constant in the number of missed accumulator updates.

Joint work: Botond Glasz, Alireza Kavousi, Istvan A. Seres, Bence Soóki-Tóth.

Suggested readings

• Private Delegation of (Non-)Membership Proof Updates in Cryptographic Accumulators (ia.cr/2026/832)
• Rust Implementation of the Private Accumulator Proof Delegation Protocols (GitHub repository)
• Specification for Implementation of ZKP based on multi-message signatures in the EUDI Wallet (GitHub TS14-zkp-from-mms)