Paper 2024/1552

Revisiting Keyed-Verification Anonymous Credentials

Abstract

Keyed-verification anonymous credentials (KVACs) have demonstrated their practicality through large-scale deployments in privacy-critical systems like 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, rate-limiting credentials only need a weaker unforgeability notion (one-more unforgeability), yet the framework cannot easily accommodate this relaxation. Similarly, identity-based applications require stronger properties than unforgeability -—specifically, extractability for security proofs when adversaries can observe other users' credentials. In this work, we address these limitations, 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 $$ to $$. We update the proof of Chase et al. in the algebraic group model. - The scheme by Barki et al. (SAC 2016), known as BBDT or BBS MAC can be issued more efficiently (one less group element). 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. Any interactive oracle proof can be used in tandem with it, leading to designated-verifier fully-succinct zk-SNARKs without pairings for algebraic groups. Our model can improve the deployment of larger protocols relying on KVACs. We show this with some examples that benefit from our approach.

Note: Preprint. Update presentation and layout. Fix of a minor bug affecting unforgeability of uCMZ with a message = 0.