Paper 2026/870

Issuer-Hiding BBS-Based Anonymous Credentials without Policy Keys

Abstract

Anonymous-credential (AC) schemes equip users with credentials on attested attributes such that users can later prove possession of a credential certifying (a subset of) those attributes without revealing anything else. In standard AC schemes, such proofs reveal the issuer of the credential, which may be more information than intended or necessary. Lately, there has been significant interest in designing stronger issuer-hiding anonymous-credential schemes that only reveal that the user has a credential from an issuer in a certain policy set. Katz and Sefranek recently showed how to add issuer hiding to BBS-based anonymous credentials. However, their scheme requires per-verifier policy keys with corresponding secret keys needed for verification; this means proofs are no longer publicly verifiable, and may pose a barrier to practical deployment. As another drawback, security of their scheme relies on the generic group model (GGM). In this work, we propose a template for constructing issuer-hiding, BBS-based anonymous credentials that does not require policy keys and whose security can be reduced to security of the BBS signature scheme (in particular, without relying on the GGM). At the core of our template is a technique to randomize BBS public keys and adapt signatures accordingly, which we show also has applications to tight multi-user security of BBS signatures. We design, implement, optimize, and experimentally compare various instantiations of our template that offer tradeoffs in proving time, verification time, and proof size. All instantiations offer good performance for policy sets of up to 64 issuers.