Revisiting Keyed-Verification Anonymous Credentials

Keyed-verification anonymous credentials (KVACs) have demonstrated their practicality through large-scale deployments in Apple, Google, Signal, and Tor. Despite their widespread adoption, the theoretical framework underlying KVACs lacks the flexibility needed to support diverse applications, which in general require different security properties. For instance, ratelimiting credentials only need a weaker unforgeability notion (one-more unforgeability), yet the framework cannot easily accommodate this relaxation. Similarly, digital identity protocols require stronger properties than unforgeability, specifically extractability for security proofs when adversaries can observe other users' credentials. We address these limitations by introducing new notions of extractability and one-more unforgeability. We improve two foundational works in the space: • The scheme by Chase et al. (CCS 2014), commonly referred to as CMZ or PS MAC can be made statistically anonymous, and issuance cost reduced from O(n) to O(1). • The scheme by Barki et al. (SAC 2016), known as BBDT or BBS MAC can be issued more efficiently (one less group element). We provide a rigorous security proof for both schemes in the algebraic group model (CRYPTO 2018) and describe how these "core credential schemes" can be extended to construct more complex anonymous credential systems such as time-based policies, pseudonyms, and rate-limiting extensions. Finally we note that, for KVACs, designated-verifier proofs suffice since the verifier is known in advance. We introduce designated-verifier polynomial commitment schemes and instantiate a variant of the popular KZG commitment scheme without pairings. We introduce a new IOP compiler for designated-verifier proofs, and use it to build designated-verifier fully-succinct zk-SNARKs without pairings for algebraic groups.