Paper 2026/369

Constant-Size Issuer Hiding for BBS Credentials via Randomizable Keys

Abstract

Anonymous credentials (AC) equip users with credentials on attested attributes, which enable them to prove data-minimizing statements over their attributes. However, in standard ACs, each credential presentation reveals the credential issuer, which could be more information than intended and necessary, e.g., when merely proving age or personhood. Issuer-Hiding Anonymous Credentials (IHAC) address this limitation and hide the issuer in the presentation. That is, they only reveal that the user has a credential from an issuer within a certain trust set, referred to as the policy. Recent works by Sanders and Traore', and Katz and Sefranek show how to add issuer hiding to PS - and BBS - based credentials while keeping presentations constant-size, i.e., not scaling in the number of issuers. However, both constructions require the verifier to generate dedicated policy-key pairs, turning verification into a secret-key operation. Managing these verifier-specific keys introduces additional complexity and affects the resulting practical privacy and security guarantees. An orthogonal work by Flamini et al. avoids verifier - specific keys but at the cost of presentations that scale linearly - or logarithmically when using more involved proof systems - in the policy size, which becomes a bottleneck for scenarios with hundreds or thousands of issuers. In this work, we close this gap and propose IHBBS, the first IHAC scheme from standard BBS signatures that achieves constant-size presentations and is publicly verifiable, i.e., does not rely on any verifier-specific secret keys. At the core of our construction is a new technique to multiplicatively randomize BBS public keys and adapt the signatures accordingly, which we believe to be of independent interest.

Note: An earlier version of this work contained both a Type-0 and a Type-1 BBS-based IHAC construction. The Type-0 scheme has been split off and merged into a separate paper (ePrint 2026/870), which now also contains a detailed study of how the linear size overhead of OR-proof-based presentations can be reduced through more advanced proof techniques such as Stacking Sigmas and Groth--Kohlweiss proofs. This paper now focuses exclusively on the constant-size Type-1 construction, and additionally develops a common framework and security model that covers all three IHAC types, together with a systematic discussion of their respective privacy and efficiency trade-offs.