Paper 2026/555

Improved Issuer Hiding for BBS-based Anonymous Credentials

Abstract

Attribute-based anonymous credential systems often fail to conceal the identity of the credential issuer. Recent attempts to address this limitation either suffer from efficiency issues or rely on security models that make unrealistic assumptions about the behavior of issuers. In this paper, we demonstrate that existing security models, which assume honest issuers, are inadequate for real-world deployments. Concretely, we present attack scenarios in which a malicious user collaborates with a single authorized issuer to forge credentials on arbitrary attributes, effectively allowing the user to assume the role of any trusted issuer without any possibility of identifying the misbehaving issuer. To address these shortcomings, we introduce a stronger security model that explicitly accounts for malicious issuers. We also propose a novel, issuer-hiding, anonymous credential scheme based on the BBS signature scheme (Eurocrypt~2023). This scheme is proven to be secure under the new model using a signed-policy approach. Our construction is fully based on BBS signatures, facilitating integration into existing standards, and resolves several open challenges posed by Katz and Sefranek (PKC~2026): (1)~it is proven secure in the Algebraic Group Model (AGM) rather than the Generic Group Model (GGM); (2)~it eliminates secret policy keys, enabling verification without any secret values; and (3)~it supports delegation of policy generation to a trusted certification authority. We further observe that issuer hiding inherently creates a tension between privacy and accountability: while concealing the issuer's identity protects honest users, it may grant plausible deniability to malicious issuers that deliberately certify false attributes. To resolve this, we introduce \emph{Accountable Issuer Hiding} (AIH), augmenting traditional issuer hiding with a controlled opening capability. Under AIH, every presentation contains an encryption of the issuer's public key under a designated opening authority's key, bound via zero-knowledge proofs to the credential and the verifier's policy. This ensures that fraudulent presentations remain attributable to the responsible issuer, even when malicious issuers provide users with opaque devices that generate valid presentations on demand. Finally, we introduce the first pairing-free issuer-hiding anonymous credential scheme, based on algebraic MACs. Formal security proofs and implementation results confirm that our schemes achieve unforgeability, everlasting issuer-hiding anonymity, and accountable issuer hiding, establishing them as practical and secure solutions for the forthcoming European Digital Identity (EUDI) Wallet.

Note: This revision introduces two main updates. First, we add a new section on \emph{Accountable Issuer Hiding} (AIH). Traditional issuer-hiding credentials create an inherent tension between privacy and accountability: concealing the issuer's identity may grant plausible deniability to malicious issuers that deliberately certify false attributes. To address this, we introduce the AIH notion and present its first practical realization, which augments issuer-hiding presentations with a controlled opening capability allowing a designated authority to identify the issuer responsible for a fraudulent presentation, while preserving issuer privacy during normal operation. Second, the Related Work section has been updated to reflect the recent the recent ePrint report 2026/870 and the revised version of ePrint report 2026/369.