Paper 2026/1373

Formalizing Privacy of Anonymous Credentials: A Provably Secure Framework with Predicate Proofs

Abstract

Anonymous credentials enable privacy-preserving authentication but existing systems either lack support for predicate proofs or are tied to specific signature schemes without a formal framework. We propose the first constructive framework for anonymous credentials with native predicate proof support. The framework provides definitions of entities, operations, adversary models, and security properties—unforgeability, unlinkability, and minimal disclosure. To demonstrate its feasibility, we instantiate the framework with BBS signatures, Pedersen commitments, and ring signature based proofs. The instantiation yields compact credentials and efficient zero-knowledge predicate proofs. We prove that the instantiation satisfies all security properties under standard assumptions (q-SDH, discrete logarithm, and the zero-knowledge of the ring signature based proof). A performance evaluation confirms that credential issuance, verification, and predicate prove/verify are practical on standard hardware, with compact credentials and proofs whose communication cost grows modestly with the number and encoding length of proved attributes, and favorable runtime and storage relative to a CL-based baseline. Our framework provides a modular foundation for designing and analyzing anonymous credential systems with fine-grained attribute disclosure.