Attribute-Based Threshold Issuance Anonymous Counting Tokens and Its Application to Sybil-Resistant Self-Sovereign Identity

Self-sovereign identity (SSI) systems empower users to (anonymously) establish and verify their identity when accessing both digital and real-world resources, emerging as a promising privacy-preserving solution for user-centric identity management. While prior work, such as CanDID (IEEE S& P 2021) made strides toward decentralized and Sybil-resistant SSI, significant limitations remain. Specifically, CanDID fails to ensure unlinkability in the presence of a single malicious issuer and requires frequent user-issuer interactions to obtain each application-specific credential, contradicting the non-interactive ideals of SSI, whose core aim is to give users full control over their identities. This paper first introduces the concept of publicly verifiable threshold anonymous counting tokens (tACT). Unlike recent approaches confined to centralized settings (Benhamouda et al., ASIACRYPT 2023), tACT operates in a distributed-trust environment. Accompanied by a formal security model and a provably secure instantiation, tACT introduces a novel dimension to token issuance, which, we believe, holds independent interest. Next, the paper leverages the proposed tACT scheme to construct an efficient Sybil-resistant SSI system. This system supports various functionalities, including threshold issuance, unlinkable multi-show selective disclosure, and non-interactive, non-transferable credentials. The proposed construction is backed by rigorous security definitions and proofs. In particular, we formalize the notion of strong unlinkability and prove our system secure under this model, addressing the privacy limitations of CanDID and ensuring robust privacy guarantees even in the presence of issuer-verifier collusion. Finally, our benchmark results show an efficiency improvement in our construction when compared to CanDID, all while accommodating a greater number of issuers and additionally reducing to a one-round protocol that can be run in parallel with all issuers.