arXiv:2609.18811v1 [cs.CR] 16 Sep 2026
Differential Trust: Dynamic Multi-Authority Anonymous Credentials with Epoch-Weighted Updates Chen Li Tianjin University [email protected]
Jianting Ning∗ Zhejiang Sci-Tech University [email protected]
Xiulong Liu Tianjin University [email protected]
Yulin Liu Wuhan University [email protected]
Abstract Anonymous credentials (ACs) are fundamental to privacypreserving authentication, allowing users to prove possession of attributes without revealing their identities. State-of-the-art ACs distribute credential issuance across multiple authorities, typically employing techniques such as Shamir’s secret sharing or aggregate signatures. While this approach enhances system robustness and eliminates single point of failure, it treats all authorities equally in the credential issuance phase. This uniform treatment disregards the varying levels of trustworthiness or stake held by different authorities. Such limitation has become particularly problematic in modern decentralized systems like Proof-of-Stake networks, where the inherent trust differentiation among nodes cannot be leveraged in the credential issuance process. To address this limitation, we propose the notion of Multi-Authority Anonymous Credentials with Epoch-Based Weights (MA-ACEW), the first Multi-Authority Anonymous Credential (MA-AC) model that considers authorities’ weight distribution in credential issuance. Crucially, MA-ACEW enables efficient credential updates when authority weight distributions change across epochs. The core of MA-ACEW is our novel Epoch-Bound Pointcheval-Sanders Signature (EBPS) primitive, which binds signatures to specific time epochs. This temporal binding enables both weight-based credential issuance within epochs and efficient non-interactive credential updates across epochs. We formalize the EUF-eCMA unforgeability requirement for EB-PS and prove our construction satisfies it under a novel STB-GPS assumption. We then prove that our MA-ACEW construction achieves unforgeability, anonymity, and blindness. Finally, we present benchmarks demonstrating the efficiency of EB-PS and MA-ACEW. Remarkably, presenting a credential aggregated from 128 partial ones takes only 10.68 ms on average. 1 ∗ Corresponding author. Part of this work was done while the author was at Wuhan University. 1 This is the full version of the paper published in the Proceedings of the 35th USENIX Security Symposium (USENIX Security 2026).
1
Introduction
Digital authentication has evolved into a fundamental security primitive bridging digital and physical identities. Such authenticated identities enable secure cross-domain access to real-world services and resources without physical presence requirements. A prominent example is Estonia’s e-Residency program, launched in 2014, which enables global users from over 170 countries to obtain digital identities for accessing e-government services (e.g., company registration, tax filing), generating over C150 million in direct economic value [34]. However, despite providing convenient service access, this approach raises significant privacy concerns as users’ digital identities become vulnerable to unauthorized exposure and potential misuse. At first glance, one might perceive privacy preservation and identity authentication as inherently contradictory objectives: How can one prove their identity while maintaining privacy? Yet, already in the 1980s, Chaum [24], [25] provided an elegant solution to this challenge through his pioneering work on cryptographic techniques for creating privacy-friendly and user-centric authentication solutions. Later, anonymous credentials (ACs) emerged as a cryptographic primitive that enables users to prove specific attributes (such as being over 18) without revealing any additional personal information or creating linkable traces across different authentications. Over the past decades, ACs have attracted significant research attention, resulting in a vast body of research exploring diverse approaches [5, 6, 18–21, 38, 41, 45, 61]. Beyond theoretical research, anonymous credentials have found their way into various practical applications. A notable example is Direct Anonymous Attestation (DAA), which has been integrated into the Trusted Platform Module specification [15] and has seen continued development [53, 68]. More recent applications include PrivacyPass for anonymous web authentication [31], privacy-preserving point collection systems [10], and anonymous tokens [49, 52] for secure authorization. Despite significant advances in functionality and adoption,
ACs face two critical challenges in today’s distributed landscape. First, reliance on a single trusted issuer creates a centralization vulnerability where compromised signing keys could produce unauthorized yet valid credentials. Second, the emergence of blockchain credential platforms such as Hyperledger Indy [37], Veramo [36], and Okapi [64] has created a paradigm shift toward distributed architectures that fundamentally conflicts with centralized issuance models. These challenges motivate the need for distributed anonymous credential systems that maintain traditional security and privacy properties while supporting multiple authorities. Recent research has pursued two approaches: threshold issuance schemes [28, 32, 63] that distribute trust among multiple parties using Shamir’s secret sharing [62], and Multi-Authority Anonymous Credentials (MA-ACs) [46, 56] that enable independent issuers to coexist within a single system through aggregate signatures with randomizable tags, allowing users to combine credentials from different sources into compact proofs while preserving privacy. Even so, these distributed credential schemes face a significant misalignment with the inherent nature of modern distributed networks. In decentralized ecosystems, participants hold different levels of authority and trust, fundamentally shaping network dynamics and consensus mechanisms. However, existing ACs, both threshold-based and multi-authority, treat all partial credentials uniformly, disregarding the inherent trust asymmetry among issuing authorities. This uniform treatment fails to capture the natural heterogeneity of trustworthiness in blockchain governance. For instance, in Proof-ofStake (PoS) systems [30, 50] or Decentralized Autonomous Organizations (DAOs) [66], a validator with a substantial stake or a governance delegate with high reputational backing inherently warrants greater influence than a peripheral node with minimal investment. Such differential weighting is crucial for security and fairness [60], ensuring that decisionmaking power accurately reflects the stakeholders’ tangible commitment to the ecosystem. Moreover, these power structures are not static but evolve over time, stake distributions fluctuate due to slashing events, delegation updates, or token transfers, requiring dynamic weight adjustments. Addressing this mismatch requires a paradigm shift from static, unweighted credential schemes toward dynamic, weighted mechanisms to foster sustainable decentralized ecosystems. We provide detailed motivation in Section 2. Our analysis of this limitation led us to explore weighted authority models, from which we derive the following research challenge: How to design an anonymous credential system with weight distribution among different authorities and simultaneously support dynamic weight updates? While existing works [28,32,56,63] have primarily focused on systems with equal or static weights, our work extends this line of research by considering dynamic weight distribution among authorities. To this end, we introduce an epoch-based mechanism that assigns and refreshes authority weights over
time, together with efficient credential updates that ensure only epoch-valid credentials can be verified. Our main contributions are summarized as follows: • The EB-PS Primitive. To enforce temporal constraints on signature validity, we introduce a new primitive called Epoch-Bound Pointcheval-Sanders Signature (EB-PS). In this primitive, the signing process is split into two phases: message signing and epoch-specific binding. Our construction of EB-PS builds upon AtoSa [56], which itself extends the multi-message PS signature scheme [58]. Our key innovation is the introduction of a dynamic management process for one of the secret key components. Specifically, we designate a component, the epoch key zj , which, unlike the other static key components, must be periodically updated. Upon a transition to a new epoch j ′ , a freshly generated zj ′ replaces the old zj . This mandatory key rotation is the core mechanism that binds the signature to a specific time frame. Consequently, a valid EB-PS signature can be viewed as a combination of a long-term signature and a short-term, epoch-specific signature. While preserving the randomization properties of AtoSa, EB-PS achieves remarkable efficiency: a signature aggregated from n messages remains compact at only two group elements. • The MA-ACEW Construction. Based on our EB-PS construction and the Weighted Threshold Signature scheme proposed by Das et al. [29], we present a new AC construction, named Multi-Authority Anonymous Credentials with Epoch-Based Weights (MA-ACEW). To the best of our knowledge, MA-ACEW is the first anonymous credential system that enables weighted trust evaluation across multiple authorities (i.e., multiple issuers). MA-ACEW addresses practical scenarios where each issuer is assigned different weights according to the issuer’s trust level or computational capability. Additionally, the redistribution or adjustment of issuer weights is allowed during epoch transitions. For credential updates during epoch transitions, we eliminate the need for users to re-interact with each issuer. Instead, users perform a one-time interactive obtaining process with an issuer, and subsequent operations involve the issuer computing epoch-specific partial credentials for users holding long-term credentials. When a user wants to present their credential to a verifier during epoch j, they only need to compute the corresponding proofs and combine the partial credentials into one. Finally, we extend the core framework to natively support three crucial features: (i) multi-attribute credentials, (ii) issuer hiding, and (iii) selective disclosure of attributes under arbitrary predicates. Collectively, these properties make MA-ACEW particularly suitable for practical scenarios, especially in distributed networks. • New Assumption and Formal Security Proofs. We introduce and formalize a new hardness assumption, the Separable Time-Bound Generalized PS (STB-GPS) assumption. This assumption extends the well-established Generalized
PS (GPS) assumption [51, 58] to more accurately capture the security requirements of epoch-based signature schemes where signature components are separable and time-bound, and we analyze its hardness in the Generic Group Model (GGM). We then establish a formal security model for our epoch-based primitive, defining Existential Unforgeability under chosen-message and Epoch-corruption Attack (EUF-eCMA). This model is formulated in the chosen-key setting [13, 54, 56] and is specifically designed to handle the dynamics of epoch transitions and, crucially, allows the adversary to perform epoch-secret corruptions. We then rigorously prove that our EB-PS construction achieves EUFeCMA security under the STB-GPS assumption. Furthermore, for our MA-ACEW construction, we provide formal security definitions for its three key properties: unforgeability, anonymity, and blindness. Building upon the security models from [38], [46], and [56], our models introduce additional oracles to capture epoch transitions and partial credential issuance, which are crucial for our system. We then provide rigorous proofs demonstrating that MA-ACEW satisfies all these specified security features. • Implementation. We implement both the EB-PS and MAACEW constructions in Golang. Additionally, we develop a smart contract for credential issuance and verification operations in MA-ACEW. For credential presentation, users need just 10.68 ms to show credentials aggregated from 128 partials. On-chain verification requires 1077K gas on Ethereum with pre-computed G2 exponentiation.
2 2.1
Problem Statement Problem Description
In modern decentralized ecosystems, PoS has established itself as the fundamental mechanism for securing trust and consensus. Unlike traditional identity-based systems, authority in a PoS setting is derived strictly from economic backing, where entities exercise power for governance or resource allocation proportional to their held stake. A valid authorization is defined by accumulating a super-majority of the total stake, rather than a simple majority of entities. However, when applying decentralized privacy-preserving credentials to this setting, a structural misalignment arises. Existing decentralized anonymous credentials are inherently stake-agnostic, they treat every issuer’s signature as identical, disregarding the fact that authority in PoS is strictly stake-dependent. Consequently, these schemes limit the applicability of privacypreserving mechanisms in scenarios that require fine-grained, stake-based governance. To bridge this gap, it is necessary to construct a credential system that is compatible with the PoS trust model while strictly preserving user privacy. However, realizing such a system presents two core challenges: A.1: The scheme must support a trust model where issuers
possess differential weights corresponding to their specific stake or institutional credibility. A.2: The scheme must support dynamic weight adjustments to reflect that issuer trust levels change over time, allowing weights to increase or decrease in response to changes in stake or confidence. Limitation of Existing Works. Current distributed anonymous credential systems adopt two main approaches. The first approach, threshold issuance for ACs [32, 63], typically employs a (t, n) Shamir’s secret sharing scheme [62], where each of the n issuers holds a share of the signing key, and any subset of t issuers can collaboratively generate a credential. Alternatively, MA-ACs [46, 56] are based on aggregate signatures with randomizable tags, allowing users to aggregate showings of credentials from different issuers (with respect to the same tag) into one compact showing, and can be viewed as a multi-signature scheme. While these approaches effectively distribute the issuing responsibility, they all adopt a uniform-weight paradigm, assigning equal importance to all credential issuers. Naive Solutions. A straightforward approach to adapt existing ACs to support arbitrary weights is through virtualization. In this model, an issuer with weight w simply holds w distinct signing keys and emulates w separate virtual issuers. However, this method suffers from several critical limitations: (i) The signing cost, partial signature size, and user’s computational load all scale linearly with the total weight W, imposing severe scalability constraints. (ii) Any modification to the weight vector w necessitates costly key regeneration and credential re-issuance across the entire system. (iii) Requiring issuers to maintain numerous signing keys significantly increases system complexity and the risk of key compromise. The severe scalability issues of virtualization, particularly the linear growth in cost and data size, naturally lead to considering more specialized solutions like Weighted Secret Sharing (WSS) schemes. While the concept dates back to Shamir’s work [62], a notable recent development is the Weighted Ramp Secret Sharing (WRSS) scheme by Garg et al. [40]. Their construction, which is based on the Chinese Remainder Theorem (CRT), appears highly promising as it directly addresses the primary scaling limitation of virtualization: the share size for a party with weight w is only O(w) bits. This efficiency is achieved in the ramp setting [9], which allows for a gap between the privacy and reconstruction thresholds, seemingly providing a direct path to our desired functionality. Despite its elegance in solving the scaling problem, this solution is ultimately not a robust one. The core efficiency of WRSS is predicated on a fundamental constraint: its reliance on a ramp setting. This introduces a predefined gap between the reconstruction threshold T , the minimum combined weight of participants needed to recover the secret, and the privacy threshold t, the maximum combined weight that is guaranteed to learn no information about it. This gap (i.e.,
T − t = Ω(λ)), while enabling efficiency, also introduces its own severe limitations for practical systems: i) Its reconstruction is set-dependent, meaning the algorithm to recover the secret changes based on the exact set of participants. This requires a preliminary coordination step to identify all active members, creating a bottleneck that is impractical for dynamic or decentralized networks. ii) It introduces security vulnerabilities for small weights, as an O(w)-bit share can be discovered via a brute-force attack if a party’s weight w is small. iii) It imposes a rigid and static weight structure, since a party’s weight is intrinsically tied to its public parameter, and any change requires a costly, system-wide reset. Summary of Challenges. In summary, naive approaches are unsuitable for dynamic ACs: virtualization incurs prohibitive linear costs, while CRT-based WRSS rigidly binds weights to public parameters. Neither supports weight changes without costly resets. A practical solution must enable efficient updates and decouple weights from credentials—our work is the first to achieve both.
2.2
Solution Overview
Here we present a high-level overview of our solution, which is efficient and conceptually simple. To construct our anonymous credential system, we partition the system into epochs. Each epoch typically spans a fixed duration (e.g., one day or one week), during which issuers’ weights remain constant. Our approach is structured into two phases: embedding time epochs into the signature scheme, followed by integrating weight settings based on this modified signature scheme. Basic Signature Scheme. Our anonymous credential system leverages the Pointcheval-Sanders (PS) signature scheme. In its general form, a signer can sign a vector of messages (m1 , . . . , mn ) using a secret key sk = (x, y1 , . . . , yn ). A sign nature is a pair of group elements σ = (h, hx+∑i=1 yi mi ) for a random h ∈ G. This structure supports efficient randomization for anonymity: a user can re-randomize a signature using n a random r ∈ Fp to obtain σ ′ = (hr , (hx+∑i=1 yi mi )r ), which is a valid signature that cannot be linked to the original. Our innovation is to enable dynamic credential updates by partitioning the secret key vector. One component, zj , serves as the epoch-specific key for epoch j, while the remaining (y1 , . . . , yk ) sign user attributes (m1 , . . . , mk ). The update protocol works as follows: 1. Key Updates: At each epoch j, the issuer replaces zj −1 with zj , keeping (x, y1 , . . . , yk ) unchanged. 2. Signature Updates: With a small public update token, users transform prior signatures into ones valid for the new epoch without re-issuance. To build intuition for our construction, we begin by describing a basic version. In this simplified exposition, the signature base is the fundamental public parameter h, devoid
of any user-specific tag, and the credential contains only a single attribute m. The signature form thus simplifies to σ = (h, hx+y·m+zj ·F (ctx,j ) ). The term zj · F (ctx, j) functions as a pseudo random function (PRF) output to provide domain separation for different credential contexts (identified by ctx). While the element h is a randomly chosen parameter in the original PS signature scheme, it is often adapted in ACs to serve as a user-specific base. Our design leverages this concept by having the issuer store this base h after a user’s initial enrollment. Building on this, the issuer can unilaterally issue credential updates for each epoch j by computing and distributing the temporal component hF (ctx,j )·zj . The exponent is carefully constructed: the epoch-specific secret zj ensures the value is fresh for each period, while the function F binds the update to the specific context ctx and epoch j. Consequently, as zj is regenerated for each epoch, the credential update for users is a simple, non-interactive process that only requires fetching this new component. Incorporating weight setting. Now we first consider the weight distribution across all issuers. In each epoch j, we denote this distribution by a vector w j . Weight vector adjustments occur only during epoch transitions, based on various factors beyond the scope of this paper. We note that each issuer is assigned a specific weight under epoch j. Consider a set of n issuers, we use a bit vector b to represent the participating issuers in the multi-issuer credential cred for a user, where b[i] = 1 denotes participation and b[i] = 0 represents non-participation. Consequently, the total w j , b ⟩, weight of the credential cred can be expressed as W = ⟨w which is the inner product of vectors w j and b . Recall that each issuer’s secret key is composed of (xi , yi , zi ), where yi and zi are used for signing a message and incorporating epoch information, respectively. The public key component Xi = v xi corresponds to private key element xi and correlates with weight wi,j . Thus, X = ⟨ppk x , b ⟩ represents the aggregated keys of participating issuers, where p k x = (X1 , . . . , Xn ). To prove the validity of a weight-based credential, we simultaneously demonstrate three crucial properties: i) the user’s aggregated credential is validly obtained from the participating issuers represented by the vector b ; ii) the user’s provided combined weight sum W exceeds the threshold defined by the verifier; and iii) the corresponding aggregated verification key X is correctly computed using the same vector b . By verifying these properties, we confirm both the credential’s validity and its compliance with the weight requirements, where issuers are weighted rather than treated equally. w j , b ⟩, Das For the proofs of inner products ⟨ppk x , b ⟩ and ⟨w et al. [29] provide an elegant solution that substantially reduces verification complexity. We will demonstrate in Section 5 how to integrate their approach with several minor but important modifications tailored to our construction. During epoch transitions, our solution requires recomputing only the criti′ w j ′ , b⟩, which cal components (hF (ctx,j )·zj ′ ) and the proof ⟨w significantly reduces the computational overhead associated
3.2
with authority set updates.
3
Preliminaries
3.1
Assumptions
Definition 1 (Separable Time-Bound Generalized PS (STB-GPS) Assumption). Given an asymmetric pairing setting S = (p, G1 , G2 , GT , u, v, e), a challenger chooses random master secrets x, y ∈ Fp and a set of independent random epoch secrets {zj }Tj=1 ⊂ Fp . The challenger initializes empty lists Qh , Qsign , Qcorrupt . An adversary A is given the public parameters (u, v, uy , v x , v y ) and access to the following oracles: • Oracle Oh (·): Outputs a uniformly distributed element h ∈ G1 and adds h to a list Qh . / Qh , or j ∈ Qcorrupt , or • Oracle Osign (j, m, h, ctx): If h ∈ the identity (m, h, ctx) has already been signed for any epoch (i.e., (m, h, ctx, ⋆) ∈ Qsign ), it returns ⊥. Otherwise, it computes: slt = hx+m·y , sep,j = hF (ctx,j )·zj It adds the tuple (m, h, ctx, j, slt , sep,j ) to Qsign and returns (slt , sep,j ).
Weighted Threshold Signature
Our work builds on the weighted threshold signature (WTS) scheme by Das et al. [29], which is based on the inner product arguments of Campanelli et al. [23]. For our purposes, we adapt the original construction with a key structural modification. Specifically, we decompose the monolithic Combine algorithm into three more granular components: CombPk for public key aggregation, CombWt for weight combination, and MergePf for aggregating proofs. The complete formal definition of our adapted scheme is provided in Appendix B.1.
4 4.1
Epoch-Bound Pointcheval-Sanders Signature Syntax and Security Definitions
We now introduce the syntax of EB-PS, which extends the framework proposed by Mir et al. [56]. Formally, an EB-PS consists of the following algorithms: Setup(1λ , T) → pp: On input the security parameter λ and the total number of time periods T, this algorithm outputs the public parameters pp. KGen(pp, n) → {lski , lvki }i∈[n] : On input the public parameters pp and the total number of signers n, the algorithm outputs a set of long-term key pairs {lski , lvki }i∈[n] .
• Oracle Oupdate (j, m, h, ctx): Upon input (j, m, h, ctx), if the tuple for epoch j, (m, h, ctx, j, ⋆), is not in Qsign , or if a tuple for epoch j +1 already exists, or if the target epoch j + 1 is corrupted (i.e., j + 1 ∈ Qcorrupt ), the oracle returns ⊥. Otherwise, it computes sep,j +1 ← hF (ctx,j +1)·zj+1 . It finds the corresponding long-term part slt from the record for epoch j, adds the new tuple (m, h, ctx, j + 1, slt , sep,j +1 ) to Qsign , and returns sep,j +1 .
TKGen(pp, n, j) → {tski,j , tvki,j }i∈[n] : On input the public parameters pp, the total number of signers n, and an epoch index j ∈ [T], it outputs a set of n epoch-specific key pairs where tski,j denotes the signing key and tvki,j denotes the verification key for signer i under epoch j.
• Oracle Ocorrupt (j): Returns the secret key zj for epoch j and adds j to the corruption list Qcorrupt .
SignLt(lski , mi , aux, tg) → σlt,i : On input the long-term secret key lski , message mi , auxiliary data aux, and tag tg, the algorithm outputs a long-term signature σlt,i .
The STB-GPS assumption holds if for any PPT adversary A, the probability of outputting a valid forgery tuple (j ∗ , m∗ , h∗ , ctx∗ , s∗lt , s∗ep,j ∗ ) is negligible. A tuple is a valid forgery if it satisfies all of the following conditions:
GenAuxTag(S) → (aux, tg): On input a message-key set S, the algorithm outputs auxiliary information aux associated with set S and a tag tg.
SignEp(j, tg, tski,j , F (ctx, j)) → σep,i,j : Under epoch j, given a tag tg, an epoch-specific secret key tski,j , and a timedependent function evaluation F (ctx, j) where ctx remains constant across epochs and serves solely for epoch binding, ∗ ∗ e(s∗ep,j ∗ , v) = e(h∗ , v F (ctx ,j )zj ∗ ) the algorithm outputs an epoch-specified signature σ ep,i,j .
∗ ∗ x+m∗ y ), e(slt , v) = e(h , v ∗ ∗ h ∈ Qh , j ∈ / Qcorrupt ∗ ∗ (m , h , ctx∗ , j ∗ , s∗lt , s∗ep,j ∗ ) ∈ / Qsign
Theorem 3.1. The STB-GPS assumption holds in the generic group model. After an adversary makes a total of q queries to the assumption’s oracles (Oh , Osign , Oupdate , Ocorrupt ) and qG queries to the group operation oracles, its probability of producing a valid forgery is no more than (2 + q + qG )2 /p, where p is the prime order of the groups. We defer the proof of the theorem to Appendix D.1.
CombSig(j, tg, σlt,i , σep,i,j ) → σi,j : Under epoch j, and the same tg, given a long-term signature σlt,i and an epochspecified signature σep,i,j for signer i, the algorithm outputs a combined signature σi,j under epoch j. Verify(j, tg, lvki , tvki,j , mi , F (ctx, j), σi,j ) → {0, 1}: Under epoch j, given a tag tg, long-term verification key lvki , an epoch-specified verification key tvki,j , message mi , the common time-dependent function evaluation F (ctx, j), and a combined signature σi,j for signer i, the algorithm outputs 1 if the signature is valid and 0 otherwise.
AggSigLt(tg, {(lvki , mi , σlt,i )}ℓi=1 ) → (σagg,lt , M, avklt ): Under the same tag tg, given a set of ℓ long-term signatures σlt,i for the messages {mi }i∈[ℓ] under the verification keys {lvki }i∈[ℓ] , the algorithm outputs an aggregate signature σagg,lt , a message set M, and an aggregated verification key avklt . AggSigEp(j, tg, {tvki,j , σep,i,j }ℓi=1 , F (ctx, j)) → (σagg,ep,j , avkep,j ): Under epoch j and the same tg, given a set of ℓ epoch-specified signatures σep,i,j under the verification keys {tvki,j }i∈[ℓ] with respect to the common time-dependent function evaluation F (ctx, j), the algorithm outputs an aggregate epoch signature σagg,ep,j and an aggregated epoch verification key avkep,j . CombAggSig(j, tg, σagg,lt , σagg,ep,j ) → σagg,j : Under epoch j and the same tg, given an aggregated long-term signature σagg,lt and an aggregated epoch signature σagg,ep,j , the algorithm outputs a combined aggregate signature σagg,j . AggVerify(j, tg, avkj , M, σagg,j , F (ctx, j)) → {0, 1}: Under epoch j, given a tag tg, an aggregated verification key avkj = (avklt , avkep,j ), a message set M, a combined aggregate signature σagg,j , and the common time-dependent function evaluation F (ctx, j), the algorithm outputs 1 if the aggregate signature is valid and 0 otherwise. ′ RndSigTag(avkj , tg, σagg,j , r) → (σagg,j , tg′ ): Under aggregated verification key avkj , given a tag tg, an aggregate signature σagg,j , and a random value r, the algorithm outputs a ′ randomized aggregate signature σagg,j and a randomized tag ′ tg .
Correctness. EB-PS ensures both basic and aggregation correctness, as formalized in Appendix C.1. Unforgeability. To formalize the security of our epoch-based scheme, we work within the chosen-key model of security, following the line of work in [13, 54, 56]. Our security notion, Existential Unforgeability under chosen-message and Epochcorruption Attack (EUF-eCMA), by building an interactive game where the adversary is given a single challenge public key vk′ and access to a corresponding signing oracle. Definition 2 (Existential Unforgeability under chosen-message and Epoch-corruption Attack (EUF-eCMA)). An epoch-bound digital signature scheme Σ = (Setup, KGen, TKGen, SignLt, SignEp, AggVerify) is EUF-eCMA secure if for any PPT adversary A, the probability of winning the following game is negligible. Setup. The challenger C runs pp ← Setup(1λ , T) to generate the public parameters. Then, C generates a long-term key pair (lvk∗ , lsk∗ ) ← KGen(pp), where the secret key lsk∗ is never revealed. For each epoch j ∈ [1, T], C computes the epochspecified key pair (tvk∗j , tsk∗j ) ← TKGen(pp, j). C initializes an empty query log Q ← 0/ and an empty set of corrupted / Finally, C provides the adversary A with epochs QCE ← 0. the public parameters pp, the long-term public key lvk∗ , and all epoch public keys {tvk∗j }j ∈[1,T] .
Queries. The adversary A can adaptively issue the following queries: • Initial Signing Query: On input an epoch j ∈ [1, T], a tag tg, a message m, auxiliary info aux, and a context ctx: – If epoch j ∈ QCE , return ⊥. – Else compute σlt ← SignLt(lsk∗ , m, aux, tg) and σep,j ← SignEp(j, tg, tsk∗j , F (ctx, j)). – Return (σlt , σep,j ) to A and update Q ← Q ∪ {(j, tg, m)}. • Epoch Update Query: For a transition from epoch j to j + 1 (j < T), on input a tag tg and context ctx: – If j + 1 ∈ QCE , return ⊥. – Otherwise, compute σep,j +1 ← SignEp(j + 1, tg, tsk∗j +1 , F (ctx, j + 1)) and return it to A. • Epoch Corruption Query: On input an epoch index j ∈ [1, T], add j to QCE and return tsk∗j . Winning Condition. The adversary A outputs a forgery tuple ∗ ∗ ∗ ℓ (j ∗ , tg∗ , M∗ , σagg,j ∗ , avkj ∗ ), where M = {mk }k=1 . A wins if all of the following conditions hold: ∗ ∗ AggVerify(j ∗ , tg∗ , avkj ∗ , M∗ , σagg,j ∗ , F (ctx, j )) = 1 (lvk∗ , tvk∗j ∗ ) ∈ avkj ∗ , j ∗ ∈ / QCE ∗ ∃mk ∈ M∗ s.t. (j ∗ , m∗k , tg∗ ) ∈ /Q
4.2
The EB-PS Construction
In this subsection, we present our EB-PS construction. Inspired by [28,56], we derive the auxiliary data aux by hashing relevant information to ensure a uniform h component. Following [56], we adopt a unique tag tg for partial aggregation, requiring all partial signatures to share the same tag. The EB-PS scheme proceeds as follows: Setup(1λ , T) → pp: On input a security parameter λ and the number of epochs T, this algorithm generates bilinear groups BG = (p, G1 , G2 , GT , u, v, e) ← BGGen(1λ ), where p is a prime order, u is a generator of G1 , and v is a generator of G2 . Then, it selects a hash function H : {0, 1}∗ → G1 and outputs the public parameters pp = {BG, T, H}. KGen(pp, n) → {lski , lvki }i∈[n] : For the i-th signer, this algorithm randomly samples (xi , yi ) ∈ F2p , sets the long-term secret key as lski = (xi , yi ) and computes the corresponding verification key as lvki = (Xi , Yi ) = (v xi , v yi ). TKGen(pp, n, j) → {tski,j , tvki,j }i∈[n] : For epoch j ∈ [T] and the i-th signer, this algorithm randomly samples zi,j ∈ Fp , sets the epoch-specific secret key as tski,j = zi,j and computes the corresponding verification key as tvki,j = Zi,j = v zi,j . GenAuxTag(S) → (aux, tg): Given a message-key set S = {(mi , lvki )i∈[ℓ] }, the algorithm randomly samples (γ, δ) ∈ F2p , sets aux = uγ ∥ uδ ∥ {(mi , lvki )}i∈[ℓ] , computes h = H(aux), and outputs auxiliary data aux and tag tg = (Γ = hγ , ∆ = hδ ), where all verification keys lvki must be distinct.
SignLt(lski , mi , aux, tg) → σlt,i : Given a long-term secret key lski = (xi , yi ) for the i-th signer, message mi , auxiliary data aux, and tag tg, the algorithm checks that aux has the form (uγ ∥ uδ ∥ {(mi , lvki )}i∈[ℓ] ), and verifies that (mi , lvki ) ∈ aux; if not, it outputs ⊥. Otherwise, the algorithm computes σlt,i = (h′ , slt,i ) where: h′ = hγ ,
slt,i = (hγ )xi +mi ·yi
SignEp(j, tg, tski,j , F (ctx, j)) → σep,i,j : Under the epoch j, given a tag tg, an epoch-specific secret key tski,j = zi,j for the i-th signer, and a time-dependent function evaluation F (ctx, j), the algorithm outputs: σep,i,j = sep,i,j = (hδ )F (ctx,j )·zi,j CombSig(j, tg, σlt,i , σep,i,j ) → σi,j : Under epoch j and the same tag tg, given a long-term signature σlt,i , and an epochspecific signature σep,i,j , the algorithm outputs a combined signature σi,j computed as:
σagg,lt and an aggregated epoch signature σagg,ep,j , this algorithm combines them to output an aggregate signature σagg,j , where: σagg,j = h′ , s = σagg,lt · σagg,ep,j AggVerify(j, tg, avkj , M, σagg,j , F (ctx, j)) → {0, 1}: Under epoch j, given an aggregate verification key avk = {(lvki , tvki,j )}ℓi=1 where lvki = (Xi , Yi ) and tvki,j = Zi,j , a message set M = {mi }ℓi=1 , a time-dependent function evaluation F (ctx, j), and an aggregate signature σagg,j = (h′ , s), outputs 1 if h′ ̸= 1G and the following equation holds: ! ! ℓ
i e h′ , ∏ Xi · Ym i
i=1
ℓ
· e (hδ )F (ctx,j ) , ∏ Zi,j
= e(s, v)
i=1
′ RndSigTag(avkj , tg, σagg,j , r) → (σagg,j , tg′ ): Under a given aggregated verification key avkj and with a tag tg, an aggregate signature σagg,j , and a random value r, the algorithm simultaneously randomizes the signature and tag as: ′ σagg,j = ((h′ )r , sr ),
′
tg′ = ((hγ )r , (hδ )r )
σi,j = (h , si = slt,i · sep,i,j ) Verify(j, tg, lvki , tvki,j , mi , F (ctx, j), σi,j ) → {0, 1}: Under epoch j, given a tg, a long-term verification key lvki = (Xi , Yi ) and an epoch-specific verification key tvki,j = Zi,j for the i-th signer, messages mi and F (ctx, j), and a signature σi,j , this algorithm parses σi,j as (h′ , si ) and outputs 1 if the equation holds: δ F (ctx,j ) i e(h′ , Xi · Ym , Zi,j ) = e(si , v) ∧ h′ ̸= 1G i )e((h )
AggSigLt(tg, {(lvki , mi , σlt,i )}ℓi=1 ) → (σagg,lt , M, avklt ): Under the same tg, given a set of ℓ long-term signatures σlt,i for the messages {m1,i }i∈[ℓ] under the verification keys {lvki }i∈[ℓ] , this algorithm outputs the set of messages M = {mi }ℓi=1 , the aggregated verification key avklt = {lvki }i∈[ℓ] , and an aggregate long-term signature: ℓ
σagg,lt = (h′ , ∏ slt,i ) i=1
AggSigEp(j, tg, {tvki,j , σep,i,j }ℓi=1 , F (ctx, j)) → (σagg,ep,j , avkep,j ): Under epoch j and the same tg, given a set of ℓ epoch-specified signatures σep,i,j under the verification keys {tvki,j }i∈[ℓ] with respect to the common time-dependent function evaluation F (ctx, j), this algorithm outputs the aggregated epoch verification key avkep,j = {tvki,j }i∈[ℓ] and an aggregate epoch signature: ℓ
σagg,ep,j = ∏ sep,i,j i=1
CombAggSig(j, tg, σagg,lt , σagg,ep,j ) → σagg,j : Under epoch j and the same tg, given an aggregated long-term signature
Correctness. We refer readers to Appendix C.2 for the correctness. Unforgeability. The formal security proof of unforgeability for our EB-PS scheme is presented in Appendix D.2. Theorem 4.1. The EB-PS scheme is EUF-eCMA secure under the STB-GPS assumption in the random oracle model.
5
Multi-Authority Anonymous Credentials with Epoch-Based Weights
In this section, we present Multi-Authority Anonymous Credentials with Epoch-Based Weights (MA-ACEW), the first AC scheme supporting weighted trust across distributed authorities. Existing multi-authority schemes [46, 56, 63] treat issuers uniformly, lacking the ability to capture varying trust levels. The weighted threshold signature (WTS) scheme of Das et al. [29] suggests a direction but depends on BLS signatures, making it unsuitable for standard ACs and dynamic weight updates. MA-ACEW overcomes this by integrating a modified WTS with our EB-PS framework.
5.1
Formal Definition
Suppose there are n credential issuers CIi (i ∈ [n]). In the first epoch, each CIi generates long-term keys (lski , lvki ) via KGen and epoch-specific keys (tski,1 , tvki,1 ) via TKGen, together with an initial weight vector w 1 = (w1,1 , . . . , wn,1 ). In epoch j, users interacting with CIi obtain a long-term credential credlt,i signed under lski and an epoch-specific credential credep,i,j signed under tski,j . At transition j → j + 1, the weight vector updates to w j +1 (based on external factors), each issuer erases (tski,j , tvki,j ),
and generates (tski,j +1 , tvki,j +1 ). Using the new key, CIi non-interactively derives fresh epoch-specific credentials credep,i,j +1 for all users with valid long-term credentials, ensuring uniqueness via tag tg. In the context of credentials, we treat messages as attributes, while retaining the original notation m. Definition 3. (MA-ACEW). A Multi-Authority Anonymous Credentials with Epoch-Based Weights (MA-ACEW) is defined by the following algorithms/protocols: Setup: On input a security parameter λ, output public parameter pp. IniEpKGen: Initialize the system by generating epoch-1 state and key materials for each issuer {CIi }i∈[n] , including longterm key pair (lski , lvki ) ← KGen(1λ ), epoch-specific key pair (tski,1 , tvki,1 ) ← TKGen(1λ ) for credential issuance, and aggregation key aki for inner-product argument generation. A global verification key vk is derived from all issuers’ aggregation keys, along with the initial weight vector w 1 ∈ Fnp . UKGen: Given a message-key space S, generate a user key pair (usk, uvk) as the user’s identity along with the auxiliary information aux. Issuance: During epoch j, each user performs a one-time interaction with credential issuer CIi to obtain a credential tuple (credlt,i , credep,i,j ) consisting of a long-term credential credlt,i and an epoch-specific credential credi,j , where: ⟨CredObtain(tg, aux, M) ↔ CredIssue(j, lski , tski,j )⟩ → credlt,i , credep,i,j EpUpdate: To initiate epoch j + 1, the system first updates the weight vector from w j to w j +1 . Then, each CIi generates a new, epoch-specific key pair (tski,j +1 , tvki,j +1 ). Subsequently, for every user holding a valid long-term credential credlt , CIi issues a fresh epoch credential credep,i,j +1 , computed as follows: CredIssueEp(tski,j +1 , tg, j + 1) → credep,i,j +1 Gen-Policies : For clarity, we first introduce our protocol within a simplified framework. In this model, the verifier’s policy is constrained to two components: the current epoch j + 1 and a minimum weight threshold Wacc , denoted as pol = (j + 1, Wacc ). To satisfy this policy, the user must present a set of certified attributes M whose cumulative weight meets or exceeds Wacc for epoch j + 1. Our construction readily extends to support a more expressive policy framework, enabling verifiers to specify arbitrary attribute disclosure requirements and complex predicates over hidden attributes. We defer the full details of this extension to Section 5.5. Show: To satisfy a verifier’s policy pol = (j + 1, Wacc ), a user holding an aggregated credential credagg,j +1 and a corresponding tag tg engages in an interactive protocol with
the verifier. Here, tg serves as the user’s pseudonymous identity. The interaction involves the user providing a zeroknowledge proof π and disclosing a set of certified attributes M = {mk }k∈[ℓ] . The proof π demonstrates that the credential’s aggregated weight W satisfies the policy threshold, i.e., W ≥ Wacc . CredShow(tg, credagg,j +1 , M, π) ↔ → {0, 1} CredVerify(pp, M, pol, {lvki , tvki,j +1 }i∈[ℓ] , π) Here, we assume the full set M is disclosed for simplicity. In Section 5.5, we extend our construction to support flexible selective disclosure, which is achieved by partitioning the attribute set into disclosed (MD ) and hidden (MH ) subsets. As a final simplification for this presentation, we also denote the time function as j, using only the epoch index.
5.2
Secuirty Definition
We formalize security in a game-based model adapted from prior work [38, 46, 56]. To capture the dynamics of epochbased weights, we extend this model with three new oracles: OUpdEp , OObtIssEp , and OIssEp . The full formalization, detailing the game mechanics and oracle interactions, is deferred to Appendix E. Correctness. The correctness ensures that a credential showing for a non-empty attribute subset M always verifies successfully when the credential was honestly issued for an attribute set {mi }i∈[ℓ] , and the aggregate weight of the attributes in M satisfies the threshold specified in the policy pol. The aggregated credential must be newly issued or properly updated within the current epoch. Unforgeability. The unforgeability asserts that no adversary A can produce a valid aggregated credential credagg,j with non-negligible probability, without possessing the required credentials from the set of accepted issuers CI = {lvki , tvki,j }i∈[n] . The credential must show for a policy pol and a set of disclosed attributes M. Here, A can obtain (lvki , tvki,j ) ∈ CI through the oracles OHCI (i) and OCCI (i). Furthermore, all credentials used in the aggregation must be updated to the current epoch to ensure the validity of the showing. Anonymity. The anonymity ensures that no adversary A, acting as a malicious verifier, can distinguish between two users with non-negligible advantage. Furthermore, different showings of the same credential should be computationally unlinkable. In the security game, the adversary has adaptive access to an oracle that, on the input of two distinct user indexes id0 and id1 , acts as one of the two credential owners (depending on bit b) in the verification. Blindness. The blindness prevents the issuer from learning which user receives which credential, thus preserving unlinkability between issuance and presentation. Formally, it guarantees that a malicious issuer, A, cannot distinguish between
two honest users during the issuance protocol, thereby severing the link between a credential’s issuance and its subsequent presentation. Definition 4 (Unforgeability). The unforgeability is defined by the security game in Fig.1. MA-ACEW is unforgeable if for any PPT adversary A, there exists a negligible function ϵ(λ) satisfies: EU-CMA
AdvA
Pr[ExpUNF MA-ACEW,A (λ) = 1]
=
-b ExpBLI MA-ACEW,A (λ)
1. pp ← Setup(1λ ), b ∈ {0, 1}; 2. ⟨O⟩ ← ⟨OHCI , OCCI , OUser ⟩; 3. (id, pol, {lvki , tvki,j }i∈[ℓ] , Mb ) ← A⟨O⟩ (pp)⟩; 4. ⟨O⟩ ← ⟨OObtlss , OObtain ⟩; 5. b′ ← A⟨O,O
Blch-b ⟩
(st); If b′ = b, return 1, else return 0.
≤ ϵ(λ) Figure 3: Blindness Security Game
ExpUNF MA-ACEW,A (λ): λ
5.3
CCI HCI ); CI ← A⟨O ,O ⟩ (pp);
1. pp ← Setup(1 2. {lsk′ , lvk′ } ← KGen(pp); {tsk′ , tvk′j } ← TKGen(pp); S 3. CI′ ← CI lvk′ ; pol ← GenPolicy(CI′ ); 4. (cred′lt , cred′ep,j ) ← A⟨O 5. cred′ep,j +1 ← A⟨O 6. b ← ⟨AO
CredShow
User, O Obtlss ,O Issue ⟩
UpdEp ,O ObtIssEp ,O IssEp ⟩
(pol, lvk′ , tvk′j )
(pol, tvk′j )
Figure 1: Unforgeability Security Game Definition 5 (Anonymity). The anonymity is defined by the security game in Fig.2. MA-ACEW is anonymous if for any PPT adversary A, there exists a negligible function ϵ(λ) satisfies:
-b -b AdvANO = Pr[ExpANO A MA-ACEW,A (λ)] −
1 ≤ ϵ(λ) 2
-b ExpANO MA-ACEW,A (λ)
1. pp ← Setup(1λ ); b ∈ {0, 1}; 2. ⟨O⟩ ← ⟨OHCI , OCCI , OUser ⟩; 3. (id0 , id1 , pol, {lvki , tvki,j }i∈[ℓ] ) ← A⟨O⟩ (pp); 4. ⟨O⟩ = {OObtIss , OObtain , OUpdEp , OIssEp } 5. b′ ← A⟨O,O
Before presenting our MA-ACEW construction, we recall the weighted threshold signature (WTS) scheme of Das et al. [29], which ensures that aggregated credential weights in each epoch satisfy the policy. The scheme relies on the polynomial identity from [7], widely used in succinct SNARK constructions:
↔ CredVerify(pol, avk, M′ , cred′agg,j +1 )⟩
7. If ∀id ∈ CU , ∃i′ ∈ [ℓ] : lvki′ = lvk′ ∧ {lvki }i∈[ℓ] ⊂ CI′ ∧ S ′ M ̸⊂ i∈[ℓ] {mi }, b = 1, return 1. Otherwise, return 0.
Anch-b ⟩
(st); If b′ = b; Otherwise, return 0.
Figure 2: Anonymity Security Game
Definition 6 (Blindness). The blindness is defined by the security game in Fig.3. MA-ACEW is blind if for any PPT adversary A, there exists a negligible function ϵ(λ) satisfies: -b -b AdvBLI = Pr[ExpBLI A MA-ACEW,A (λ)] −
1 ≤ ϵ(λ) 2
Building Blocks for MA-ACEW
x(t)b(t) = q(t) · zH (t) + t · r(t) + ⟨x, b⟩ · n−1 . We adapt WTS to our framework with two changes: (i) moving from symmetric to asymmetric pairings, and (ii) splitting the Combine phase into CombPk and CombWt, which enables WTS integration. The full construction appears in Appendix B.2.
5.4
MA-ACEW construction
In this subsection, we present the concrete construction of MA-ACEW. For simplicity, we denote the EB-PS scheme as Ψ1 and the WTS scheme as Ψ2 , and we instantiate the time-independent function F (ctx, j) with access only to j in MA-ACEW. These notations and the function are consistently used in Fig. 4 and throughout this subsection. Interactive issuing. To prevent issuers from learning user attributes, we build upon techniques from [56, 63]. For clarity, we refer to the GenAuxTag algorithm as GenUserTag and detail the credential issuance protocol. In the original EB-PS scheme, the GenAuxTag algorithm exposed plaintext attributes within its output: aux = uγ ∥ uδ ∥ {(mi , lvki )}i∈[ℓ] . Our core modification is to replace these plaintext attributes {mi } with their ElGamal encryptions. Concretely, the user first generates an ElGamal key pair (esk, evk) = (d, ζ = ud ). For each attribute mi , the user then computes its ciphertext ci = Enc((h′ )mi , evk) = (uki , ζ ki · (h′ )mi ) and, in parallel, a commitment to the attribute cmi = umi ho1i . The values (d, oi , ki ) are sampled uniformly at random from Fp , and h1 ∈ G1 . Additionally, the user needs to generate a corresponding proof: πCIi = ZKPOK{(d, mi , oi , ki ) : ζ = ud ∧ cmi = umi ho1i ∧ ci = (uki , ζ ki · (h′ )mi )}
→ − − − Setup Phase: Run ppΨ1 ← Ψ1 .Setup(1λ , T) ∧ ppΨ2 ← Ψ2 .Setup(1λ ), output pp = (ppΨ1 , ppΨ2 ) = (BG, CRS, → v L, → α L , β , α, θ, v η ). Initial Epoch IKGen Phase: Initialize the epoch state by setting the current epoch j := 1. • IKG.1 Generate the long-term keys for each issuer {(lski , lvki )}i∈[n] ← Ψ1 .KGen(ppΨ1 ), where lski = (xi , yi ), lvki = (Xi , Yi ). • IKG.2 Set initial weight vector w 1 := [w1,1 , . . . , wn,1 ], where wi,1 corresponds to CIi ’s public key Xi . • IKG.3 Generate the epoch-specific keys for CIi : {tski,1 , tvki,1 }i∈[n] ← Ψ1 .TKGen(ppΨ1 , n, 1), where tski,1 = zi , tvki,1 = Zi,1 . • IKG.4 Compute the verification and aggregated keys from (aki , vk) ← Ψ2 .KGen(ppΨ2 , n, w 1 ), where vk = (v, α, β, v x(τ ) , v w1 (τ ) , v τ , ατ , uzH (τ ) ), aki = (v xi , vixi , αixi , θxi , v ηxi , {βkxi }k∈[n] ) w (τ ) 1 // Note that v is only utilized in epoch j = 1, and aki is to assist user to persists across all epochs. UKGen phase: Run (aux, tg) ← Ψ1 .GenAuxTag(S), return (usk = (γ, δ), uvk = (Γ, ∆), aux = (uγ ∥ uδ ∥ {cmi , ci , lvki }i∈[ℓ] )) to user. Gen-Policies Phase: The verifier sets threshold Wacc and only accepts credentials of current epoch j. Return pol = (Wacc , j). Issuance Phase: The user interacts with CIi to obtain partial credentials at epoch j: • IS.1 The user sends (tg, aux, πtg , πCIi ) to an issuer CIi , where defined as: aux = (uγ ∥ uδ ∥ {cmi , ci , lvki }i∈[ℓ] ),
πtg = ZKPOK{(γ, δ) : tg1 = hγ ∧ tg2 = hδ ∧ Γ = uγ ∧ ∆ = uδ },
πCIi = ZKPOK{(d, mi , oi , ki ) : ζ = ud ∧ cmi = umi ho1 i ∧ ci = (uki , ζ ki · (h′ )mi )} \ • IS.2 CIi verifies πCIi and πtg , checks the format of aux, and if all pass, then computes (cred lt,i , credep,i,j ) for the user, where: ′ yi ′ xi yi \ cred lt,i = (h , ci,1 , (h ) ci,2 ),
credep,i,j = (hδ )j·zi,j
• IS.3 The user unblinds the long-term credential to obtain credlt,i = (hγ , (hγ )xi +mi yi ) and stores (credlt,i , credep,i,j ). // Note that the user only interacts with CIi once, as credlt,i remains valid across all epochs. Epoch Update: When the system transitions from epoch j to epoch j + 1, the following operations are performed: • EP.1 Securely erase CIi ’s previous (tski,j , tvki,j ), and run {tski,j+1 , tvki,j+1 }i∈[n] ← Ψ1 .TKGen(pp, n, j + 1) for epoch j + 1. • EP.2 Reset the epoch weight vector w j+1 and recompute the weight verification key v wj+1 (τ ) , which is part of vk. • EP.3 Each issuer CIi computes credep,i,j+1 = (hδ )(j+1)·zi,j+1 for its credentialed users as part of the credential update. • EP.4 The verifier updates pol to (W′acc , j + 1). // Upon receiving credep,i,j from each CIi , the user replaces the previous epoch signature credep,i,j with credep,i,j+1 . Show phase: The user interacts with the verifier to show a credential in epoch j + 1: • SH.1 The user computes the combined credential credagg,j+1 with disclose set M in current epoch, where: credagg,lt ← Ψ1 .AggSigLt(tg, {(lvki , mi , credlt,i )}ℓi=1 ),
credagg,ep,j+1 ← Ψ1 .AggSigEp(j + 1, tg, {tvki,j+1 , σep,i,j }ℓi=1 ),
credagg,j ← Ψ1 .CombAggSig(j + 1, tg, credagg,lt , credagg,ep,j ) • SH.2 According to the disclosed set M, set the bit vector b[i] = 1 for i ∈ M, and compute the proof as: (πb , πIPA,pk , X) ← Ψ2 .CombPk(bb, {aki }i∈[n] , vk),
w j+1 , {aki }i∈[n] ) (πIPA,wt , Wclaim ) ← Ψ2 .CombWt(w
• SH.3 Run πIPA ← Ψ2 .MergePf(πIPA,pk , πIPA,wt , X, Wclaim ), (cred′agg,j+1 , tg′ ) ← Ψ1 .RndSigTag(avkj+1 , tg, credagg,j+1 , r). • SH.4 The user sends (cred′agg,j+1 , tg′ , ub , πb , πIPA , X, Wclaim , M) to the verifier. CredVerify Phase: The verifier checks if the randomized credential is valid and satisfies the acceptance threshold defined in pol. • CV.1 Run Ψ1 .AggVerify(j + 1, tg′ , avkj+1 , M, cred′agg,j+1 ) and Ψ2 .Verify(πIPA , vk, X, Wclaim ). • CV.2 Check if W′acc ≤ Wclaim . Return 1 if all verification checks are successful; otherwise, return 0.
Figure 4: MA-ACEW Construction
The auxiliary information aux is now defined as aux = (uγ ∥ uδ ∥ {cmi , ci , lvki }i∈[ℓ] ) And the issuing phase between user and issuer CIi as: • The user transmits (tg, aux, πCIi , πtg ) to the credential issuer CIi , where n πtg = ZKPOK (γ, δ) : tg1 = hγ ∧ tg2 = hδ ∧ o Γ = uγ ∧ ∆ = uδ is uniformly utilized for all credential issuers. • The issuer CIi parses aux and verifies the validity of proofs πCIi and πtg . Upon successful verification, CIi executes blind issuance on the attribute mi , computing: ′ yi ′ xi yi \ cred lt,i = (h , ci,1 , (h ) ci,2 ),
credep,i,j = (hδ )j ·zi,j
• The user unblinds the partial long-term credential as credlt,i = (h′ , (h′ )xi cyi,i2 (cyi,i1 )−d ) Epoch transition. In MA-ACEW, the user interacts with each credential issuer CIi only once to obtain the long-term credential. Additionally, CIi issues epoch-based credentials credep,i,j . To streamline this process, CIi maintains a list of registered users, identified by their unique tags tg. For each new epoch j + 1, CIi computes and issues fresh epoch-based credentials credep,i,j +1 for all registered users without requiring additional interaction, which eliminates the need for subsequent interactions between users and credential issuers. During the system initialization phase, each credential issuer CIi generates secret keys (lski = (xi , yi ), tski,1 = zi ), where yi is used for signing attributes and zi for updating (signing epoch information for each user). The value Xi = v xi corresponds to CIi ’s initial weight wi,1 . Additionally, all issuers {CIi }i∈[n] compute aggregation keys aki to assist the user. Assuming a Public Key Infrastructure (PKI), users can non-interactively retrieve aki from each CIi , as stated in [29]. Since the weight vector w j is publicly known and the public key vector p k x remains valid across all epochs, no complex operations are required for subsequent updates. When the system transitions from epoch j to epoch j + 1, the weight vector is reset to w j +1 , where each wi,j +1 continues to correspond to the issuer’s long-term public key Xi . This update requires only one term in the public verification key vk to be recomputed: v wj+1 (τ ) . Each credential issuer CIi updates its epoch-specific keys by executing (tski,j +1 , tvki,j +1 ) ← Ψ1 .TKGen(ppΨ1 , j + 1). Additionally, each CIi computes new epoch-based credentials credep,i,j +1 ← Ψ1 .SignEp(tski,j +1 , j + 1, tg) for each registered user. As wi,j is publicly known, this computation can be performed independently of the credential issuers.
Interactive Showing. According to practical scenarios, the verifier needs to define a policy pol to determine whether to accept a user’s obtained credential. Here, the verifier only accepts credentials updated in the current epoch, i.e., the credential issuer CIi must have computed a valid epoch-specific signature for the user under tg. Additionally, the verifier can adjust the acceptance threshold Wacc according to the weight distribution scenario of nodes. The user processes the set of disclosed attributes M and the corresponding partial credentials {credlt,i , credep,i,j +1 }i∈[M] as follows. First, the user aggregates the long-term credentials set and the epoch-specific credential set separately. Then, these two aggregated credentials are combined into a single credential of constant size. Notably, the user can precompute the aggregated long-term credentials. Since epoch-specific credentials are re-issued by credential issuers at the beginning of each epoch, the user only needs to aggregate them when presenting a credential during the current epoch j + 1. It is important to note that only one attribute per lvki can be issued (corresponding to the secret key yi ). However, this can be extended to support multiple attributes by generating a series of lvki , as demonstrated in [58], [63]. We will elaborate on this extension in Section 5.5. Additionally, the user computes the corresponding IPA proofs: πIPA,pk to convince the verifier that ⟨ppk x , b ⟩ = X, and w j +1 , b ⟩ = Wclaim satisπIPA,wt to convince the verifier that ⟨w fies the acceptance threshold W′acc , i.e., Wclaim ≥ W′acc . These IPA proofs are merged into a single proof by taking their random linear combination using the Fiat-Shamir heuristic [35]. Notably, the proof πIPA,pk can be precomputed in the previous epoch. During epoch j + 1, the user only needs to compute the epoch-specific aggregated credentials and the weight proof. However, the pre-computation is only applicable when the total weight of the user’s obtained credentials exceeds the verifier-defined threshold pol. If the total weight is insufficient, the user must obtain additional credentials and re-compute the corresponding proof. Nonetheless, this scenario is uncommon in practice, as system parameters typically remain relatively stable across epochs, and users generally maintain a total credential weight that exceeds the required threshold. Given the IPA proof and the combined credential, the verifier verifies the credential’s validity under epoch j + 1 by checking that: (a) The aggregated credential credagg,j +1 is a valid credential on the disclosed attribute set M, and has been updated to the current epoch j + 1; (b) πb is a correct proof of commitment ub to vector b , confirming that b is a bit vector; (c) πIPA is a valid IPA proof for both the aggregated public key X and that the provided Wclaim satisfies the defined threshold in pol. Theorem 5.1. [U NFORGEABILITY] If the EB-PS signature scheme is unforgeable, the IPA protocol satisfies knowledge soundness, and the ZKPoK is simulation-sound extractable, then the MA-ACEW construction achieves unforgeability.
Theorem 5.2. [A NONYMITY] MA-ACEW achieves anonymity if the DDH assumption holds in G1 and the ZKPoK protocol is zero-knowledge. Theorem 5.3. [B LINDNESS] MA-ACEW achieves blindness if the ElGamal encryption is IND-CPA secure and ZKPoK protocol is zero-knowledge. The complete security proofs can be found in Appendix F.
5.5
Additional Properties
In this subsection, we extend our MA-ACEW scheme to support several advanced properties, namely Multi-Attribute Credential Issuance, Issuer Hiding, and policies supporting the Selective Disclosure of Arbitrary Attributes. We show that these features can be incorporated with minor modifications to our core construction. The full details are deferred to Appendix G.
5.6
Application
In this subsection, we demonstrate the practical utility of our scheme within PoS-based ecosystems, specifically instantiating it for privacy-preserving DAO governance. Consider a DAO voting scenario where a user acts as a delegate, aggregating voting power from multiple stakeholders (who act as credential issuers). Initially, a user holding (aux, tg) interacts with these stakeholders to accumulate the necessary credentials. Here, the public key component Xi directly correlates with the i-th stakeholder CIi ’s voting weight wi,j . To prove possession of sufficient voting power, the user employs a binary participation vector b . This vector ensures that only the stakeholders contributing to the aggregated credential credagg,j are selected, meaning that only those entries where bi = 1 are included in the inner products for the aggrew j , b ⟩. gated key ⟨ppk x , b ⟩ and the total accumulated weight ⟨w Consequently, during the DAO verification phase, the user generates proofs πIPA and πb to attest that the aggregated credential validly reflects the sum of the selected stakeholders’ weights, thereby meeting the governance policy pol. To ensure governance integrity over time, our system implements a dynamic epoch mechanism where credentials require an issuer-assisted refresh for each new governance cycle. Instead of relying on static permissions, a user intending to vote obtains an epoch-based credential credep,i,j from each stakeholder CIi with whom they have previously interacted, in order to locally update their credential to the current state. This on-demand synchronization directly addresses the challenge of authorization freshness within the DAO: it allows the governance contract to strictly verify that a delegate’s voting power is currently active for the specific epoch. Moreover, due to the randomizability of the credentials, the system upholds user unlinkability, ensuring that the validation of a user’s standing does not create a traceable history of their past governance activities.
6
Performance Evaluation
We implement and evaluate our constructions in Golang, providing complete implementations of both EB-PS and MAACEW. All code is available in an open Zenodo repository2 . Our implementation leverages the BLS12-381 pairingbased curve and builds upon the WTS construction from [29]. To enhance computational efficiency, we employ multiexponentiation techniques for group elements in the aggregation process. All performance measurements were conducted on a machine equipped with an Intel Core i7-1260P CPU @2.10 GHz, 16GB RAM running Ubuntu 18.04.
6.1
Implementation Benchmarks
For all benchmarks, we selected parameters to achieve 128bit security. We first evaluated the basic operations: a single exponentiation in the source groups G1 and G2 of the elliptic curve took approximately 110µs and 252µs. For storage requirements, a single compressed element in G1 required 48 bytes, while an element in G2 required 96 bytes. Communication Overhead. We first analyze the communication overhead of EB-PS and MA-ACEW constructions during the signing/issuance phase. U → S/CI U ← S/CI G1 G2 Fp Bytes G1 Bytes EB-PS 4 n n 192 + 128n 3 144 MA-ACEW 4 + 3n n 0 192 + 240n 4 196 Constr.
Table 1: Communication Overhead of Signing/Issuance Table 1 presents the communication costs from the user’s perspective. For auxiliary information aux, EB-PS employs GenAuxTag while MA-ACEW utilizes GenUserTag. Due to the encrypted messages in MA-ACEW, its communication overhead is naturally higher. Notably, Table 1 excludes the zero-knowledge proof costs, which users can selectively generate for attributes being issued. For each issuer, these additional zero-knowledge proofs require 512 bytes for an encrypted message and 256 bytes for tag proofs. Sig./Cred. size PK size G1 G2 Fp Bytes G1 G2 Bytes EB-PS 4 0 0 192 0 3n 288n MA-ACEW 6 5 1 800 1 3n + 7 720 + 288n Constr.
Table 2: Communication Overhead of Verify Phase Table 2 presents the communication overhead for showing signatures or credentials in both EB-PS and MA-ACEW 2 https://doi.org/10.5281/zenodo.17905110
schemes. Due to signature aggregation capabilities, the userside communication costs remain constant in both constructions regardless of the number of attributes. Compared to EB-PS, MA-ACEW requires additional computation for inner product arguments, resulting in higher overhead. For public key size, we observe a linear relationship with the number of attributes since we represent unaggregated keys. For practical storage optimization, verifiers can aggregate these public keys before verification, significantly reducing space requirements. Timing benchmark. We evaluate the computational efficiency of both EB-PS and MA-ACEW by measuring the execution time of each algorithm/phase. For each algorithm, we report both the mean execution time and standard deviation. Our measurements use Go’s built-in benchmarking framework, which adaptively determines iterations for statistical significance. Metric Time (ms) Std Dev (±)
GenAuxTag SignLt SignEp Verify RndSigTag 0.92 0.38
0.34 0.02
0.13 0.01
1.29 0.21
0.45 0.06
Prims(ms): G1 Exp.: 0.11 | G2 Exp.: 0.25 | Pairing: 0.85 Table 3: Performance Evaluation of EB-PS Scheme Table 3 presents the performance metrics of the proposed EB-PS scheme detailed in Section 4.2, including execution time and communication overhead for key operations. Our evaluation focused on critical algorithms within the EB-PS construction. The GenAuxTag algorithm was benchmarked with 128 messages, while SignLt, SignEp, and Verify algorithms were evaluated in a single-signer scenario. Notably, the Verify algorithm demonstrates higher computational complexity due to its bilinear pairing operations. As shown in Table 4, we evaluated MA-ACEW performance across different operational phases, reporting execution times and standard deviations in a network with 64 signers. The Setup phase incurs substantial overhead due to CRS generation with complex cryptographic operations. However, the Initial IKGen phase dominates the computational cost with exceptionally high execution times, as evidenced by our measurements. This overhead stems from necessary CRS preprocessing and encompasses critical procedures: generation of long-term and epoch signing keys for all issuers, verification keys for inner product arguments, and proof generation for users. Our implementation replaces original messages in GenAuxTag with ciphertexts, increasing overhead compared to our EB-PS implementation. Furthermore, the issuance phase introduces additional computational costs due to its blind issuance mechanism, which requires users to generate ZKPoK and issuers to verify these proofs. Fig. 5a presents the computational costs of the AggVerify algorithm in EB-PS, while Fig. 5b illustrates the computational overhead of the Show and CredVerify phases in MA-
Phase Setup Initial IKGen UKGen Issuance Issuance Epoch Update
Time (ms)
Std Dev (±)
46.34 445.84 5.93 2.74 4.55 14.49
10.34 12.17 0.31 0.86 1.52 1.28
Notes 64 issuers 64 issuers 10 messages User side Issuer side 64 issuers
Table 4: Performance Evaluation of MA-ACEW Phases
ACEW. Our evaluation examines performance across varying numbers of signers/credential issuers, ranging from 4 to 128, with each issuer corresponding to a single disclosed attribute in our experimental setup. The Show phase in MA-ACEW includes computation of Inner Product Argument (IPA) proofs. Although both schemes show increasing computational costs with more attributes, our analysis reveals that the IPA computation time grows very slowly. The observed linear growth in MA-ACEW’s execution time primarily stems from the underlying EB-PS operations. Although we tested scenarios with up to 128 issuers, practical applications rarely require this many, as our MA-ACEW design allows the system to operate efficiently with fewer issuers.
(a) EB-PS performance
(b) MA-ACEW performance
Figure 5: Execution time analysis of EB-PS and MA-ACEW
6.2
Smart-Contract Evaluation
We extended our evaluation to include a smart contract implementation of our MA-ACEW scheme, focusing on the issuance and credential verification functionalities. The implementation was developed in Solidity utilizing the BN254 asymmetric pairing curve. We selected BN254 due to its native support in Ethereum and superior efficiency among pairing-friendly curves in blockchain contexts. Operation LT. Iss. Ep. Iss. Ver.
Group Ops.
Gas
Est. Cost (USD)
2G1 Exp + 2P 1G1 Exp 19G1 Exp + 15P
255K 70K 1077K
0.11 0.03 0.47
Table 5: Performance metrics on Ethereum
We present our detailed performance evaluation in Table 5. Our analysis focuses on two critical phases: the Issuance phase and the credential verification phase, corresponding to the credential issuer and verifier operations, respectively. The Issuance phase comprises two distinct procedures: longterm credential issuance and epoch-credential issuance. The former includes computationally intensive proof verification operations, resulting in significantly higher computational costs compared to the more efficient epoch-credential issuance procedure. For the verification phase, we implement a constant-time approach that eliminates the variable complexity associated with multiple pairing operations. Since exponentiation in G2 incurs significant computational overhead, we pre-compute necessary group elements and optimize the protocol to process only signature pairs and inner product arguments. Our implementation leverages the batch verification technique introduced by Das et al. [29], adapting their optimized pairing-based verification framework available in the open-source codebase3 . This approach reduces the overall verification cost by aggregating multiple pairing operations through a randomized linear combination technique, resulting in efficient and optimized pairing checks. Finally, to provide economic context for the tabulated results, USD costs were estimated using Ethereum network parameters from November 7, 2025 (ETH ≈ $3,450, median gas price ≈ 0.128 Gwei), noting that actual costs vary with network congestion.
6.3
Table 6: Theoretical Complexity Comparison with Baseline
3 https://github.com/sourav1547/wts.
Sign Cost (Per Issuer)
Agg. Cost (Total)
Ver. Cost (Total)
Baseline
O(wi )*
O(W)†
O(W)†
O(1)
O(n)‡
O(n)‡
MA-ACEW
* w : weight of the specific signer; i
† W: total weight;
‡ n: number of
issuers.
As expected, our solution is marginally slower than the baseline in this specific setting due to the overhead of additional proofs. However, since our performance is determined by the number of issuers rather than the total weight, we gain efficiency by achieving the same weight with fewer issuers. To demonstrate this efficiency while ensuring a fair comparison (i.e., avoiding the extreme case of a single high-weight issuer), we evaluate scenarios with 128 and 64 issuers. In these more typical configurations, our scheme significantly outperforms the baseline. Table 7: Performance Comparison with Baseline Showing
Scheme
Verification
Time (ms) Speedup Time (ms) Speedup
Comparison with Naive Solution
In this subsection, we evaluate the performance of our proposed MA-ACEW scheme through both theoretical complexity analysis and experimental implementation. We utilize a virtualized Pointcheval-Sanders (PS) signature scheme as the baseline for comparison to demonstrate the efficiency gains of our approach. Theoretical Analysis. As shown in Table 6, the computational complexity of the baseline design depends linearly on the weight parameters. Specifically, the signing cost scales with the individual weight wi of the i-th issuer, while the aggregation and verification costs grow linearly with the total accumulated weight W. In contrast, MA-ACEW decouples computational overhead from weight magnitude, achieving a constant signing cost per issuer and ensuring that aggregation and verification costs scale solely with the number of issuers n, irrespective of the total weight W. Performance Benchmarking. As shown in Table 7, we fix the total accumulated weight at W = 256 for our evaluation. Since the baseline does not support weighted issuers, it necessitates a number of issuers equal to the total weight (i.e., n = 256), thereby fixing its cost to this target. We first compare the worst-case scenario for our scheme, where the weight is fragmented among 256 issuers (i.e., 256 weight-1 issuers).
Scheme
Baseline
16.1
—
31.5
—
Ours (n = 256)
17.3
0.93×
36.3
0.87×
Ours (n = 128)
10.5
1.53×
25.4
1.20×
Ours (n = 64)
7.0
2.30×
16.7
1.89×
Note: n denotes the number of issuers. Speedup is relative to Baseline.
7
Related Work
We focus our analysis on decentralized anonymous credentials, aggregate signatures, and PoS verification mechanisms. Decentralized Anonymous Credentials. Garman et al. [41] introduced an innovative approach to decentralized credential systems without relying on traditional signing authorities. Their scheme leverages a public ledger (blockchain) where users register commitments to their attributes. Users prove possession of credentials by constructing zero-knowledge proofs based on RSA accumulators of ledger entries. However, this solution faces scalability challenges and may not be suitable for credentials that inherently require trusted issuers. To enhance security and reduce centralization in credential issuance, recent schemes have explored threshold issuance, distributing credential issuance authority among a group of entities. Such schemes require collaboration from at least a threshold number of issuers to produce a valid cre-
dential [8, 17, 32, 63]. A notable example is Coconut [63], a threshold-based anonymous credential scheme designed for blockchain environments, built upon threshold PS signatures [58]. Coconut’s security is based on an interactive assumption similar to, but distinct from, the LRSW assumption [55]. Importantly, its security has been formally proven within the Universal Composability (UC) framework [59]. Multi-Authority Anonymous Credentials (MA-ACs), introduced in [46] and further studied in [56], enable the aggregation of credential showings from different issuers. The work in [56] introduces two key cryptographic primitives: tag-based aggregate signatures with randomizable tags and public keys (AtoSa) and Aggregate Mercurial Signatures with Randomizable Tags (ATMS). Notably, their scheme achieves the issuer-hiding property, which is also studied in [11,14,27]. While these distributed credential schemes achieve decentralized issuance, they fundamentally rely on underlying aggregate signature schemes. Aggregate Signatures. Aggregate signatures, introduced by Boneh et al. [13], support aggregation of signatures from different parties on possibly different messages. The key requirement is succinctness of the aggregated signature. As a result of this innovative concept, several variants have been studied and developed [12, 47, 48, 57]. Among these variants, one notable example is the synchronized aggregate signature, first proposed by Gentry and Ramzan [42]. Subsequently, [2] further advanced this idea by proposing a pairing-based scheme without random oracles. Central to our work is the Pointcheval-Sanders (PS) signature scheme [58], which provides a short signature size compared to the Camenisch-Lysyanskaya (CL) signature scheme [22]. Later, recent research has explored various structurepreserving properties in signature schemes. Ghadafi et al. [44] introduced the notion of partially structure-preserving signatures. In fully structure-preserving signature schemes [1], all messages, signatures, and public keys are group elements. Further advancing this line of research, Crites et al. [28] proposed message-indexed structure-preserving signatures. Their construction, inspired by both the PS signature scheme and Ghadafi’s work [43], parameterizes messages with an indexing function, allowing aggregation of different signatures for different messages under different public keys if they share the same index. We now move from theory to practice, exploring applications in the PoS setting, particularly unweighted multisignature schemes and SPV-style proofs. Unweighted Multi-signatures and SPV-style Proofs. To reduce the substantial bandwidth and storage requirements inherent in Proof-of-Stake blockchains, Drijvers et al. [33] proposed Pixel, a pairing-based forward-secure multi-signature scheme that optimizes verification costs. Following this line of work, Wei et al. [67] proposed Pixel+ and Pixel++, two forward-secure multi-signature schemes that optimize verification in PoS blockchains by aggregation of public keys.
Addressing security tightness, [3] introduces a new variant of BLS multi-signatures and demonstrates how PoS protocols that currently use BLS can adopt it for fully compatible opt-in tight security. In a parallel effort to save computational resources, Baldimtsi et al. [4] propose an efficient BLS multi-signature variant for PoS blockchains that replaces per-signature randomization with a one-time public key randomization, saving significant computational resources during aggregation and verification. Complementing signature aggregation schemes, SPV-style proofs also aim to drastically reduce verification costs. Addressing the scalability issues of traditional SPV clients, FlyClient [16] utilizes an optimal probabilistic block sampling protocol and Merkle Mountain Range (MMR) commitments to enable sub-linear light client verification. Pushing efficiency further, Vesely et al. [65] presented Plumo. Instead of downloading full headers, it securely verifies SNARKbased state transition proofs to confirm the latest network state. Furthermore, to address security in cross-chain communication, [26] proposed an accountable light client system designed to secure cross-chain bridges by validating incremental state updates and identifying misbehaving participants. Summary of Related Work. While existing aggregate signature schemes provide elegant primitives for Anonymous Credentials, they do not directly support epoch-based validity. Moreover, previous credential schemes typically treat all issuers equally, ignoring the heterogeneity of issuer authority. In PoS settings, solutions generally rely on unweighted multisignatures or SPV-style proofs. Unweighted multi-signatures are computationally inexpensive but misalign with the security model of PoS, as they rely on a threshold of node counts rather than the accumulated stake weight. Conversely, while recent SNARK-based light clients achieve succinct verification, they introduce significant prover-side computational overhead. Traditional SPV approaches, meanwhile, require verifiers to track a growing chain of headers and validate inclusion proofs. This introduces non-trivial bandwidth overhead and synchronization dependency. Our MA-ACEW addresses these limitations by incorporating temporal validity and flexible issuer weighting tailored for PoS-based ecosystems.
8
Conclusion
In this paper, we introduced the Epoch-Bound PointchevalSanders (EB-PS) signature primitive, which enables temporal binding for signatures. Building on a concrete EB-PS construction, we developed Multi-Authority Anonymous Credentials with Epoch-based Weights (MA-ACEW), the first decentralized anonymous credential system that incorporates weighted authority contributions. Our approach enables efficient credential updates when authority weight distributions change across epochs, addressing a significant limitation in existing systems that treat all authorities uniformly regardless of their relative trustworthiness or significance in the system.
Furthermore, we provided formal security definitions and rigorous proofs for both EB-PS and MA-ACEW constructions. To demonstrate practical viability, we implemented our schemes in Golang and developed smart contract components to evaluate the credential issuance and verification phases. Our results confirm that MA-ACEW achieves the necessary efficiency for deployment in decentralized systems such as Proof-of-Stake networks, where authority trust levels naturally fluctuate over time.
Acknowledgements This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grants 12441101 and 62372324. We thank the anonymous reviewers and our shepherd for their constructive feedback, and Zhiqiang Ma, Gaowei Shi, and Chenyu Zhang for their insightful suggestions.
Ethical Considerations In this section, we conduct a stakeholder analysis and discuss the potential societal impacts of our proposed weighted anonymous credential system. While our work focuses on the formal design and security analysis of a cryptographic protocol, we recognize that the deployment of such privacy-enhancing technologies requires a robust socio-technical context to be used safely. Stakeholder Analysis. We identify four key stakeholder groups within the ecosystem of privacy-preserving proofof-stake and governance systems. First, Users (Credential Holders) are the primary beneficiaries. They utilize weighted credentials to access services or participate in voting without revealing their identities, protecting them from targeting, profiling, or coercion. Their primary interest lies in the robustness of the anonymity guarantee. Second, Service Providers and Verifiers rely on credentials for access control or vote tallying. They benefit from the security derived from stake-backed credentials without the liability of managing user identities, though they face the operational risk of being unable to hold individual users accountable for abuse. Third, Credential Issuers hold the stake and issue credentials. They benefit from the issuer-hiding property and broader adoption driven by enhanced user privacy, but face reputational risk if credentials derived from their stake are misused. Finally, System Operators and the Community are concerned with the overall fairness and legitimacy of the system. While they benefit from increased participation, they could be harmed if the technology facilitates large-scale, untraceable manipulation. Potential Impacts and Misuse Considerations. The core objective of our construction is to enable privacy-preserving authentication. However, the strong privacy guarantees also introduce potential risks. On the positive side, our system em-
powers users to act without fear of surveillance or retaliation, fostering more honest participation in sensitive contexts like voting. By guaranteeing user anonymity and issuer hiding, the system mitigates surveillance-based coercion risks. On the negative side, the primary ethical risk is abuse by malicious actors. Without adequate safeguards, malicious users could exploit anonymity to engage in untraceable, coordinated manipulation or launch credential-based Sybil attacks. If unchecked, this could lead to a tragedy of the commons, eroding accountability and deterring honest participants. Mitigations and Deployment Safeguards. To address the risks associated with real-world application, we emphasize that our cryptographic protocol should not be deployed in isolation. We recommend specific architectural safeguards. Separation of Protocol and Deployment Controls. It is essential to distinguish between the cryptographic security model and deployment-layer controls. Our security model captures the core properties of anonymous credentials, but practical defense against Sybil attacks requires external bounds on per-entity issuance. We treat issuance-rate control as a necessary measure at the deployment layer; effective deployments must impose strict bounds on credential issuance per epoch to prevent abuse. Layered Accountability Mechanisms. Real-world systems must be designed with layered accountability mechanisms. These include rate-limiting and economic costs to make large-scale abuse prohibitively expensive, as well as transparent governance and circuit-breakers. For extreme scenarios, a decentralized process should be established to investigate and, as a last resort, respond to system-wide attacks, ensuring anonymity does not become an absolute shield for actors attempting to destroy the system itself. Cryptographic Extensions. A natural direction for future research is to explore privacy-preserving quotas directly within the cryptographic layer. Techniques such as k-times anonymous credentials (also known as k-show) could be integrated to cryptographically enforce usage limits while maintaining user privacy, thereby bridging the gap between protocol security and operational stability.
Open Science In adherence to the USENIX Security Symposium’s open science policy, we have deposited our implementation in an open Zenodo repository (https://doi.org/10.5281/zenodo. 17905110). Our repository consists of two primary components: (1) the core Golang implementation of the proposed EB-PS and MA-ACEW schemes (including cryptographic logic and ZK-proof constructions) located in maacew/src; and (2) the smart contract implementation for on-chain operations located in maacew/contracts. Detailed instructions on code structure, dependencies, and reproduction steps are provided in the README file within the root directory. This ensures compliance with the conference’s submission guide-
lines and enables transparent verification and reproduction of our results by the research community.
References [1] Masayuki Abe, Georg Fuchsbauer, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. Structurepreserving signatures and commitments to group elements. In Advances in Cryptology–CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 30, pages 209– 236. Springer, 2010. [2] Jae Hyun Ahn, Matthew Green, and Susan Hohenberger. Synchronized aggregate signatures: new definitions, constructions and applications. In Proceedings of the 17th ACM conference on Computer and communications security, pages 473–484, 2010. [3] Renas Bacho and Benedikt Wagner. Tightly secure non-interactive bls multi-signatures. In International Conference on the Theory and Application of Cryptology and Information Security, pages 397–422. Springer, 2024. [4] Foteini Baldimtsi, Konstantinos Kryptos Chalkias, Francois Garillot, Jonas Lindstrøm, Ben Riva, Arnab Roy, Mahdi Sedaghat, Alberto Sonnino, Pun Waiwitlikhit, and Joy Wang. Subset-optimized bls multi-signature with key aggregation. In International Conference on Financial Cryptography and Data Security, pages 188– 205. Springer, 2024. [5] Foteini Baldimtsi and Anna Lysyanskaya. Anonymous credentials light. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013, pages 1087–1098. ACM, 2013. [6] Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, and Anna Lysyanskaya. P-signatures and noninteractive anonymous credentials. In Ran Canetti, editor, Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008, volume 4948 of Lecture Notes in Computer Science, pages 356– 374. Springer, 2008. [7] Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P Ward. Aurora: Transparent succinct arguments for r1cs. In Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part I 38, pages 103–128. Springer, 2019.
[8] Kanchan Bisht, Neel Yogendra Kansagra, Reisha Ali, Mohammed Sayeed Shaik, Maria Francis, and Kotaro Kataoka. Revocable TACO: revocable threshold based anonymous credentials over blockchains. In Proceedings of the 19th ACM Asia Conference on Computer and Communications Security, ASIA CCS 2024, Singapore, July 1-5, 2024, 2024. [9] G. R. Blakley and Catherine Meadows. Security of ramp schemes. In George Robert Blakley and David Chaum, editors, Advances in Cryptology, pages 242–268, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg. [10] Johannes Blömer, Jan Bobolz, Denis Diemert, and Fabian Eidens. Updatable anonymous credentials and applications to incentive systems. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019, pages 1671–1685. ACM, 2019. [11] Jan Bobolz, Fabian Eidens, Stephan Krenn, Sebastian Ramacher, and Kai Samelin. Issuer-hiding attributebased credentials. In Cryptology and Network Security: 20th International Conference, CANS 2021, Vienna, Austria, December 13-15, 2021, Proceedings 20, pages 158– 178. Springer, 2021. [12] Alexandra Boldyreva, Craig Gentry, Adam O’Neill, and Dae Hyun Yum. Ordered multisignatures and identitybased sequential aggregate signatures, with applications to secure routing. In Proceedings of the 14th ACM conference on Computer and communications security, pages 276–285, 2007. [13] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Advances in Cryptology—EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003 Proceedings 22, pages 416–432. Springer, 2003. [14] Daniel Bosk, Davide Frey, Mathieu Gestin, and Guillaume Piolle. Hidden issuer anonymous credential. Proceedings on Privacy Enhancing Technologies, 2022:571– 607, 2022. [15] Ernest F. Brickell, Jan Camenisch, and Liqun Chen. Direct anonymous attestation. In Vijayalakshmi Atluri, Birgit Pfitzmann, and Patrick D. McDaniel, editors, Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004, Washington, DC, USA, October 25-29, 2004, pages 132–145. ACM, 2004.
[16] Benedikt Bünz, Lucianna Kiffer, Loi Luu, and Mahdi Zamani. Flyclient: Super-light clients for cryptocurrencies. In 2020 IEEE Symposium on Security and Privacy (SP), pages 928–946. IEEE, 2020. [17] Jan Camenisch, Manu Drijvers, Anja Lehmann, Gregory Neven, and Patrick Towa. Short threshold dynamic group signatures. In International conference on security and cryptography for networks, pages 401–423. Springer, 2020. [18] Jan Camenisch, Maria Dubovitskaya, Kristiyan Haralambiev, and Markulf Kohlweiss. Composable and modular anonymous credentials: Definitions and practical constructions. In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology - ASIACRYPT 2015 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pages 262–288. Springer, 2015. [19] Jan Camenisch and Els Van Herreweghen. Design and implementation of the idemix anonymous credential system. In Vijayalakshmi Atluri, editor, Proceedings of the 9th ACM Conference on Computer and Communications Security, CCS 2002, Washington, DC, USA, November 18-22, 2002, pages 21–30. ACM, 2002. [20] Jan Camenisch and Anna Lysyanskaya. A signature scheme with efficient protocols. In Stelvio Cimato, Clemente Galdi, and Giuseppe Persiano, editors, Security in Communication Networks, Third International Conference, SCN 2002, Amalfi, Italy, September 11-13, 2002. Revised Papers, volume 2576 of Lecture Notes in Computer Science, pages 268–289. Springer, 2002. [21] Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In Matthew K. Franklin, editor, Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, pages 56–72. Springer, 2004. [22] Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In Annual international cryptology conference, pages 56–72. Springer, 2004. [23] Matteo Campanelli, Anca Nitulescu, Carla Ràfols, Alexandros Zacharakis, and Arantxa Zapico. Linearmap vector commitments and their practical applications. In International Conference on the Theory and Application of Cryptology and Information Security, pages 189–219. Springer, 2022.
[24] David Chaum. Blind signatures for untraceable payments. In Advances in Cryptology: Proceedings of Crypto 82, pages 199–203. Springer, 1983. [25] David Chaum. Security without identification: Transaction systems to make big brother obsolete. Communications of the ACM, 28(10):1030–1044, 1985. [26] Oana Ciobotaru, Fatemeh Shirazi, Alistair Stewart, and Sergey Vasilyev. Accountable light client systems for proof-of-stake blockchains. Cryptology ePrint Archive, 2022. [27] Aisling Connolly, Pascal Lafourcade, and Octavio Perez Kempner. Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes. In IACR International Conference on Public-Key Cryptography, pages 409–438. Springer, 2022. [28] Elizabeth Crites, Markulf Kohlweiss, Bart Preneel, Mahdi Sedaghat, and Daniel Slamanig. Threshold structure-preserving signatures. In International Conference on the Theory and Application of Cryptology and Information Security, pages 348–382. Springer, 2023. [29] Sourav Das, Philippe Camacho, Zhuolun Xiang, Javier Nieto, Benedikt Bünz, and Ling Ren. Threshold signatures from inner product argument: Succinct, weighted, and multi-threshold. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 356–370, 2023. [30] Bernardo David, Peter Gaži, Aggelos Kiayias, and Alexander Russell. Ouroboros praos: An adaptivelysecure, semi-synchronous proof-of-stake blockchain. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 66–98. Springer, 2018. [31] Alex Davidson, Ian Goldberg, Nick Sullivan, George Tankersley, and Filippo Valsorda. Privacy pass: Bypassing internet challenges anonymously. Proc. Priv. Enhancing Technol., 2018(3):164–180, 2018. [32] Jack Doerner, Yashvanth Kondi, Eysa Lee, Abhi Shelat, and LaKyah Tyner. Threshold bbs+ signatures for distributed anonymous credential issuance. In 2023 IEEE Symposium on Security and Privacy (SP), pages 773–789. IEEE, 2023. [33] Manu Drijvers, Sergey Gorbunov, Gregory Neven, and Hoeteck Wee. Pixel: Multi-signatures for consensus. In 29th USENIX Security Symposium (USENIX Security 20), pages 2093–2110, 2020. [34] e Residency Administration. e-residency: The digital identity and business residency. https://e-resident. gov.ee/, 2023.
[35] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques, pages 186–194. Springer, 1986. [36] Decentralized Identity Foundation. Veramo: A javascript framework for verifiable data. https: //github.com/decentralized-identity/veramo, 2024. [37] Hyperledger Foundation. Hyperledger ursa: A shared cryptographic library for decentralized systems. https: //github.com/hyperledger-archives/ursa, 2024. Accessed: 2024-12-29. [38] Georg Fuchsbauer, Christian Hanser, and Daniel Slamanig. Structure-preserving signatures on equivalence classes and constant-size anonymous credentials. Journal of Cryptology, 32:498–546, 2019. [39] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. IACR Cryptol. ePrint Arch., page 953, 2019. [40] Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, and Yinuo Zhang. Cryptography with weights: Mpc, encryption and signatures. In Annual International Cryptology Conference, pages 295–327. Springer, 2023. [41] Christina Garman, Matthew Green, and Ian Miers. Decentralized anonymous credentials. Cryptology ePrint Archive, 2013. [42] Craig Gentry and Zulfikar Ramzan. Identity-based aggregate signatures. In Public Key CryptographyPKC 2006: 9th International Conference on Theory and Practice in Public-Key Cryptography, New York, NY, USA, April 24-26, 2006. Proceedings 9, pages 257– 273. Springer, 2006. [43] Essam Ghadafi. Short structure-preserving signatures. In Cryptographers’ Track at the RSA Conference, pages 305–321. Springer, 2016. [44] Essam Ghadafi. Partially structure-preserving signatures: lower bounds, constructions and more. In International Conference on Applied Cryptography and Network Security, pages 284–312. Springer, 2021. [45] Lucjan Hanzlik and Daniel Slamanig. With a little help from my friends: Constructing practical anonymous credentials. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 2004–2023, 2021.
[46] Chloé Hébant and David Pointcheval. Traceable constant-size multi-authority credentials. Information and Computation, 293:105060, 2023. [47] Susan Hohenberger, Venkata Koppula, and Brent Waters. Universal signature aggregators. In Annual international conference on the theory and applications of cryptographic techniques, pages 3–34. Springer, 2015. [48] Susan Hohenberger, Amit Sahai, and Brent Waters. Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, pages 494–512. Springer, 2013. [49] Ioanna Karantaidou, Omar Renawi, Foteini Baldimtsi, Nikolaos Kamarinakis, Jonathan Katz, and Julian Loss. Blind multisignatures for anonymous tokens with decentralized issuance. In Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie, editors, Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS 2024, Salt Lake City, UT, USA, October 14-18, 2024, pages 1508–1522. ACM, 2024. [50] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Annual international cryptology conference, pages 357–388. Springer, 2017. [51] Hyoseung Kim, Youngkyung Lee, Michel Abdalla, and Jong Hwan Park. Practical dynamic group signature with efficient concurrent joins and batch verifications. Journal of information security and applications, 63:103003, 2021. [52] Ben Kreuter, Tancrède Lepoint, Michele Orrù, and Mariana Raykova. Anonymous tokens with private metadata bit. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part I, volume 12170 of Lecture Notes in Computer Science, pages 308–336. Springer, 2020. [53] Vireshwar Kumar, He Li, Noah Luther, Pranav Asokan, Jung-Min "Jerry" Park, Kaigui Bian, Martin B. H. Weiss, and Taieb Znati. Direct anonymous attestation with efficient verifier-local revocation for subscription system. In Jong Kim, Gail-Joon Ahn, Seungjoo Kim, Yongdae Kim, Javier López, and Taesoo Kim, editors, Proceedings of the 2018 on Asia Conference on Computer and Communications Security, AsiaCCS 2018, Incheon, Republic of Korea, June 04-08, 2018, pages 567–574. ACM, 2018.
[54] Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, and Hovav Shacham. Sequential aggregate signatures from trapdoor permutations. In Advances in CryptologyEUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004. Proceedings 23, pages 74–90. Springer, 2004. [55] Anna Lysyanskaya, Ronald L Rivest, Amit Sahai, and Stefan Wolf. Pseudonym systems. In Selected Areas in Cryptography: 6th Annual International Workshop, SAC’99 Kingston, Ontario, Canada, August 9–10, 1999 Proceedings 6, pages 184–199. Springer, 2000. [56] Omid Mir, Balthazar Bauer, Scott Griffy, Anna Lysyanskaya, and Daniel Slamanig. Aggregate signatures with versatile randomization and issuer-hiding multiauthority anonymous credentials. In Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023, pages 30–44. ACM, 2023. [57] Gregory Neven. Efficient sequential aggregate signed data. In Advances in Cryptology–EUROCRYPT 2008: 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings 27, pages 52–69. Springer, 2008. [58] David Pointcheval and Olivier Sanders. Short randomizable signatures. In Topics in Cryptology-CT-RSA 2016: The Cryptographers’ Track at the RSA Conference 2016, San Francisco, CA, USA, February 29-March 4, 2016, Proceedings, pages 111–126. Springer, 2016. [59] Alfredo Rial and Ania M Piotrowska. Security analysis of coconut, an attribute-based credential scheme with threshold issuance. Cryptology ePrint Archive, 2022. [60] Muhammad Saad, Zhan Qin, Kui Ren, DaeHun Nyang, and David Mohaisen. e-pos: Making proof-of-stake decentralized and fair. IEEE Transactions on Parallel and Distributed Systems, 32(8):1961–1973, 2021. [61] Olivier Sanders. Efficient redactable signature and application to anonymous credentials. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part II, volume 12111 of Lecture Notes in Computer Science, pages 628–656. Springer, 2020. [62] Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979.
[63] Alberto Sonnino, Mustafa Al-Bassam, Shehar Bano, Sarah Meiklejohn, and George Danezis. Coconut: Threshold issuance selective disclosure credentials with applications to distributed ledgers. arXiv preprint arXiv:1802.07344, 2018. [64] Trinsic-ID. Okapi: Collection of tools that support workflows for authentic data and identity management. https://github.com/trinsic-id/okapi, 2024. Accessed: 2024-12-29. [65] Psi Vesely, Kobi Gurkan, Michael Straka, Ariel Gabizon, Philipp Jovanovic, Georgios Konstantopoulos, Asa Oines, Marek Olszewski, and Eran Tromer. Plumo: An ultralight blockchain client. In International Conference on Financial Cryptography and Data Security, pages 597–614. Springer, 2022. [66] Shuai Wang, Wenwen Ding, Juanjuan Li, Yong Yuan, Liwei Ouyang, and Fei-Yue Wang. Decentralized autonomous organizations: Concept, model, and applications. IEEE Transactions on Computational Social Systems, 6(5):870–878, 2019. [67] Jianghong Wei, Guohua Tian, Ding Wang, Fuchun Guo, Willy Susilo, and Xiaofeng Chen. Pixel+ and pixel++: Compact and efficient forward-secure multi-signatures for pos blockchain consensus. In 33rd USENIX Security Symposium (USENIX Security 24), pages 6237–6254, 2024. [68] Stephan Wesemeyer, Christopher J. P. Newton, Helen Treharne, Liqun Chen, Ralf Sasse, and Jorden Whitefield. Formal analysis and implementation of a TPM 2.0based direct anonymous attestation scheme. In HungMin Sun, Shiuh-Pyng Shieh, Guofei Gu, and Giuseppe Ateniese, editors, ASIA CCS ’20: The 15th ACM Asia Conference on Computer and Communications Security, Taipei, Taiwan, October 5-9, 2020, pages 784–798. ACM, 2020.
A
Assumptions
Definition 7 (PS Assumption [58]). Consider an asymmetric pairing setting (p, G1 , G2 , GT , u, v, e) with (v x , v y ) ∈ G22 where x and y are random scalars in Zp . The PS assumption holds if no PPT adversary A with unlimited access to PS oracle OPS (m) can efficiently generate a tuple (h∗ , s∗ , m∗ ) such that: • OPS (m): On input m ∈ Fp , chooses a random h ∈ G1 and outputs (h, hx+my ). • Q is the list of queried messages to the OPS (m) oracle. Definition 8 (Generalized PS Assumption [51]). Consider an asymmetric pairing setting, given (v x , v y ) ∈ G22 , the GPS
assumption is defined with respect to two oracles O0GPS (·) and O1GPS (·), where: • O0GPS (·) outputs a uniformly distributed h ∈ G1 . • O1GPS (m, h) takes input h ∈ G1 , m ∈ Fp and outputs s = hx+m·y . If h ∈ / Q0 ∨ (h, ⋆) ∈ Q1 , it outputs ⊥ . The GPS assumption holds if no PPT adversary A can find a tuple (h∗ , s∗ , m∗ ) such that: h∗ ̸= 1G1 ,
∗
s∗ = (h∗ )x+m ·y ,
and
m∗ ∈ /Q
where Q1 = Q1 ∪ (h, m) is the list of queries made to O1GPS by adversary A.
B B.1
Weighted Threshold Signature(WTS) Formal definition
Definition 9 (WTS). A Weighted Threshold Signature scheme (WTS) consists of the following polynomial-time algorithms: • Setup(1λ ) → pp: On input the security parameter λ, the algorithm outputs the public parameters pp. • KGen(pp, n) → ({ski , pki , aki }i∈[n] , vk): On input the public parameters pp and the total number of signers n, the algorithm outputs the global verification key vk, and for each signer i ∈ [n], a tuple (ski , pki , aki ) consisting of a signing key, public key, and an aggregation key for IPA proof computation. • PSign(ski , m) → σi : On input a signing key ski and a message m, the algorithm outputs a partial signature σi . • PVerify(m, σi , pki ) → {0, 1}: On input a message m, a partial signature σi , and a public key pki , the algorithm outputs 1 if the partial signature is valid, and 0 otherwise. • CombPk({aki }i∈[n] , b , {σi }b[i]=1 , vk) → (πIPA,pk , πb , σ): On input a set of aggregation keys {aki }i∈[n] , a binary vector b indicating participating signers (where bi = 1 if signer i participates, and 0 otherwise), a set of partial signatures {σi }b[i]=1 from participating signers, and the global verification key vk, the algorithm outputs: an IPA proof πIPA,pk for the inner product between the public keys and vector b , a proof πb that b is binary, and the aggregate signature σ. • CombWt(vk, b , w ) → πIPA,wt : On input the global verification key vk, a binary vector b indicating participating signers, and a weight vector w containing the weights of all signers, the algorithm outputs an IPA proof πIPA,wt for the inner product between the participation vector b and the weight vector w . • MergePf(πIPA,pk , πIPA,wt ) → πIPA : On input an IPA proof πIPA,pk for the inner product between the public keys and the participation vector b, and an IPA proof πIPA,wt for the inner product between the participation vector b and the weight vector w , the algorithm combines them into a single merged IPA proof πIPA . • Verify(m, σ, vk, πIPA , Wacc ) → {0, 1}: On input a message m, an aggregate signature σ, the global verification key
vk, a merged IPA proof πIPA , and an acceptance threshold Wacc , the algorithm outputs 1 if the signature is valid and the accumulated weight meets the acceptance threshold Wacc , and 0 otherwise.
B.2
WTS Construction
For comprehensive technical foundations of the polynomial identities, we refer readers to [7, 29]. We now present the complete construction of our weighted threshold signature (WTS) scheme. As mentioned in Section 5.3, we employ asymmetric pairings and separate the signature combination process into distinct phases. The detailed algorithms are as follows: • Setup(1λ ) → pp: On input the security parameter λ, first generates bilinear group parameters BG = (p, G1 , G2 , GT , u, v, e) ← BGGen(1λ ), where p is a prime order, u ∈ G1 and v ∈ G2 are generators, and e : G1 × G2 → GT is a bilinear pairing. Then selects a hash function H : {0, 1}∗ → G1 and derives HFS (·) using domain separation. The algorithm then performs: – Let ω ∈ Fp be a primitive n-th root of unity, and define H = {ω, ω 2 , . . . , ω n } as a multiplicative subgroup of order n and L as a coset of H of size n − 1, where H ∩ L = ∅. – Sample random generators θ ∈ G1 , α ∈ G2 and a random τ ∈ Fp , and generate the following CRS: n
n
u := [u, uτ , . . . , uτ ], v := [v, v τ , . . . , v τ ], α := [α, ατ , . . . , ατ
n−1
]
– Preprocess CRS as follows, where Li,H (τ ) and Li,L (τ ) denote the Lagrange polynomials defined over the multiplicative subgroups H and L respectively: → − v L := [v L1,H (τ ) , . . . , v Ln,H (τ ) ] → − α := [αL1,H (τ ) , . . . , αLn,H (τ ) ] L
→ − β := [v L1,L (τ ) , . . . , v Ln,L (τ ) ]
− – Compute v η using → v L , where η = ∑i∈[n] Lωi (iτ ) . → − − − Output pp = (BG, CRS, → v L, → α L , β , α, θ, v η ). • KGen(pp, n, w ) → ({ski , pki , aki }i∈[n] , vk): The algorithm takes as input the public parameters pp, the total number of signers n and a vector of weights w . The algorithm performs: $
– Sample xi ← Fp for each i ∈ [n] and generate the persigner key pairs (ski , pki ) = (xi , v xi ). For each signer i, compute the aggregation key: aki = (v xi , vixi , αixi , θxi , v ηxi , {βkxi }k∈[n] ) → − − − using → v L, → α L , and β .
– Compute the global verification key: (v, α, β, v x(τ ) , v w(τ ) , v τ , ατ , uzH (τ ) ), where: v
x(τ )
= ∏
vixi , v w(τ ) =
i∈[n]
∏
vk =
– Compute challenge: ξ = HFS (v x(τ ) , v w(τ ) , ub(τ ) , X, Wclaim )
viwi .
– Check if the following equations hold:
i∈[n]
The vanishing polynomial over H is defined as
e(ub(τ ) , v x(τ ) ) = e(uzH (τ ) , v qo (τ ) )
zH (τ ) = ∏ (τ − ω i ) = τ n − 1.
· e(uτ , v ro (τ ) )
i∈[n]
· e(u1/n , v x · v ξ·Wclaim )
• CombPk(bb, {aki }i∈[n] , vk) → (πb , πIPA,pk ): On input a signing set vector b , the aggregation keys {aki }i∈[n] , compute the following:
e(u, αpo (τ ) ) = e(uτ , v ro (τ ) ) · e(u1/n , v ξ·Wclaim · X)
b(τ )
and the proof – Compute commitment to b as ub = u πb = v qb (τ ) that b is binary using the polynomial remainder lemma: b(τ ) · (1 − b(τ )) = qb (τ ) · zH (τ ). – Compute the aggregated public key X and the IPA proof πIPA,pk = {v qx (τ ) , v rx (τ ) , αpx (τ ) , θx }, where: X = v x = ⟨pp k , b⟩. w , {aki }i∈[n] ) → (πIPA,wt , Wclaim ): On input a • CombWt(w set of weight vectors w corresponding to b[i] = 1, and the w , b ⟩ and aggregation keys {aki }i∈[n] , compute Wclaim = ⟨w the IPA proof: πIPA,wt = {v qw (τ ) , v rw (τ ) , αpw (τ ) , θWclaim } • MergePf(πIPA,pk , πIPA,wt , X, Wclaim ) → πIPA : On input the IPA proofs πIPA,pk and πIPA,wt for signing and weight vectors respectively, and aggregated values (X, Wclaim ), compute the merged proof using HFS as follows: – Compute ξ = HFS (v x(τ ) , v w(τ ) , ub(τ ) , X, Wclaim ) – Compute qo (τ ) = qx (τ ) + ξ · qw (τ ) ro (τ ) = rx (τ ) + ξ · rw (τ ) po (τ ) = px (τ ) · τ + (x + ξ · Wclaim ) · n−1 The merged proof is: πIPA = (v qo (τ ) , v ro (τ ) , αpo (τ ) , θx , Wclaim ) • Verify(πIPA , vk) → {0, 1}: On input an IPA proof πIPA and verification key vk, output 1 if all following equations hold:
e(θx , v) = e(θ, X) Here, we omit the signing phase, as in our MA-ACEW constructions, we need to replace the original BLS signature with our proposed EB-PS to satisfy the properties defined in Section 5.2.
C
Correctness of EB-PS
C.1
Formal Definition
We now formalize the basic correctness of EB-PS. The correctness property ensures that honestly generated signatures will always be accepted by the verification algorithm. Formally, ∀i ∈ [ℓ], ∀j ∈ [T] : (lski , lvki ) ← KGen(pp); (tsk , tvk ) ← TKGen(pp, j); i,j i,j = 1. σ ← SignLt(lsk , m , aux, tg); Pr lt,i i i σ ← SignEp(j, tg, tsk , F (ctx, j)); ep,i,j i,j σi,j ← CombSig(j, tg, σlt,i , σep,i,j ); Verify(j, tg, lvki , tvki,j , mi , F (ctx, j), σi,j ) = 1 Aggregation Correctness. We next define the aggregation correctness of EB-PS, which ensures that properly aggregated signatures remain verifiable. Formally:
∀j ∈ [T] :
σagg,lt ← AggSigLt tg, {lvki , mi , σlt,i }ℓi=1 ; (σagg,ep,j , avkep,j ) ← AggSigEp j, tg, Pr = 1. ℓ {tvki,j , σep,i,j }i=1 , F (ctx, j) ; σ ← AggCombine(σ , σ ); agg,j agg,lt agg,ep,j AggVerify(j, tg, avkj , M, σagg,j , F (ctx, j)) = 1
C.2
Proof of correctness
– Check the correctness of the bit vector: e(ub(τ ) · u1−b(τ ) , v) = e(uzH (τ ) , v qb (τ ) )
We now prove the correctness of our EB-PS construction as follows:
Basic Correctness. For basic correctness, we observe that the combined signature takes the form: F (ctx,j )·zi,j σi,j = hγ , (hγ )xi +mi ·yi · hδ
• A queries the oracle Osign on a tuple (j, m, ctx, h) and receives handles to the two polynomials representing the signature components: Pslt = Ph ·(x+my) and Psep,j = Ph · (F (ctx, j) · zj ).
The left-hand side of the verification equation evaluates as:
• A queries the oracle Oupdate on a tuple (j, m, h, ctx) and receives a handle to the polynomial for the new epoch component: Psep,j+1 = Ph · (F (ctx, j + 1) · zj +1 ).
δ F (ctx,j ) i e(hγ , Xi · Ym , Zi,j ) i ) · e((h )
= e(hγ , v xi · (v yi )mi ) · e((hδ )F (ctx,j ) , v zi,j )
• A queries the oracle Ocorrupt on an epoch j and receives the secret polynomial zj .
γ ·(xi +mi ·yi )+δ ·F (ctx,j )·zi,j
= e(h, v)
The right-hand side evaluates as: e(si , v) = e(h, v)γ ·(xi +mi ·yi )+δ·F (ctx,j )·zi,j Since both sides yield the same expression, this establishes the correctness of the scheme. Aggregation Correctness. For aggregatable correctness, we observe that the combined signature takes the form: F (ctx,j )·∑i∈[ℓ] zi,j σagg,j = hγ , (hγ )∑i∈[ℓ] xi +mi ·yi · hδ The left-hand side of the verification equation evaluates as:
Polynomial Representation of the Forgery. The GGM principle dictates that any group element computed by A corresponds to a polynomial that is a linear combination of the polynomials for all elements it already possesses. The adversary’s goal is to output a forged signature pair (s∗lt , s∗ep,j ∗ ). This means A must construct two corresponding polynomials, Ps∗lt and Ps∗ep,j ∗ . Therefore, for A to construct the two components of its forgery, their respective polynomials, Ps∗lt and Ps∗ep,j ∗ , must be expressible as linear combinations of this basis. We use distinct coefficients for each component to reflect that they are constructed independently:
δ F (ctx,j ) i e(hγ , ∏ Xi · Ym , ∏ Zi,j ) i ) · e((h ) i∈[ℓ] γ
= e(h , v
i∈[ℓ]
∑i∈[ℓ] xi
yi mi
· ∏ (v )
δ F (ctx,j )
) · e((h )
qh
,v
∑i∈[ℓ] zi,j
)
i∈[ℓ]
= e(h, v)γ ·∑i∈[ℓ] (xi +mi ·yi )+δ·F (ctx,j ) ∑i∈[ℓ] zi,j
Ps∗lt = αlt + βlt y + ∑ δk Phk k=1
qs +qu
qs
+ ∑ γi Pslt ,i + i=1
∑ ηi Psep ,i + ∑
i=1
cj zj
j ∈Qcorrupt
The right-hand side evaluates as:
(1)
e(s, v) = e(h, v)γ ·∑i∈[ℓ] (xi +mi ·yi )+δ·F (ctx,j )·∑i∈[ℓ] zi,j Since both sides yield the same expression, this establishes the correctness of the scheme.
D
Security Proofs
qh
Ps∗ep,j ∗ = αep + βep y + ∑ δk′ Phk k=1
qs
qs +qu
i=1
i=1
+ ∑ γi′ Pslt ,i +
∑ ηi′ Psep ,i + ∑
c′j zj
j ∈Qcorrupt
(2)
D.1
Proof of Theorem 3.1
Let us assume an adversary A produces a valid forgery (j ∗ , m∗ , h∗ , ctx∗ , s∗ ) after making a total of q queries to the assumption’s oracles (Oh , Osign , Oupdate , Ocorrupt ) and qG queries to the group operation oracles. By the definition of a valid forgery, the target epoch j ∗ has not been corrupted, i.e., j∗ ∈ / Qcorrupt . We now analyze the structure of this forgery in the Generic Group Model (GGM). Setup and Oracle Simulation. In the GGM, we associate group elements with formal polynomials over a set of indeterminates. A is given handles to the public parameters and oracle outputs. The oracles are simulated as follows: • A queries the oracle Oh and receives a group element hk ∈ G1 represented by a new random polynomial rk .
The Verification Constraint. For the output pair (s∗lt , s∗ep,j ∗ ) to be a valid forgery for the tuple (m∗ , ctx∗ , h∗ ) at the uncorrupted target epoch j ∗ , it must satisfy the verification ∗ ∗ ∗ equation: e(s∗lt · s∗ep,j ∗ , v) = e(h∗ , v x · v m y · v F (ctx ,j )zj ∗ ). In the GGM, where group operations correspond to polynomial additions, this verification equation translates into a specific condition on the sum of the corresponding polynomials, Ps∗lt and Ps∗ep,j ∗ . The target polynomial they must sum to is: Ptarget = Ph∗ · (x + m∗ y + F (ctx∗ , j ∗ )zj ∗ ) (3) Thus, the core constraint for a valid forgery is the polynomial identity: Ps∗lt + Ps∗ep,j ∗ = Ph∗ · (x + m∗ y + F (ctx∗ , j ∗ )zj ∗ )
(4)
As argued previously, for the verification to be possible, the handle h∗ must be an explicit output from Oh . Let us assume h∗ was the output of the k ∗ -th distinct hash query. Its polynomial is therefore Ph∗ = rk∗ , where rk∗ is a fresh, random polynomial. By definition of a valid forgery, the target epoch j ∗ is uncorrupted, i.e., j ∗ ∈ / Qcorrupt . Consequently, zj ∗ is an indeterminate unknown to A, and its value is independent of all other polynomials known by A. The Algebraic Contradiction. To prove that no adversary A can produce a valid forgery, we will now substitute the general forms of the adversary’s constructed polynomials into the main verification identity (Eq. (4)) and analyze the resulting algebraic constraints.
As established, this requires the handle polynomial to be of the simple form Ph∗ = rk∗ . We now substitute this constraint, along with the general expressions for the two forged signature components (Eqs. (6) and (7)), into the verification identity. By grouping the coefficients of like terms from the two forged polynomials, we arrive at the central relation for our analysis: qh
(αlt + αep ) + (βlt + βep )y + ∑ (δk + δk′ )Phk k=1
qs
+ ∑ (γi + γi′ )Pslt,i i=1 qs +qu
Polynomial Forms for the Forgery. As established, for a forgery to be verifiable, the adversary must choose a handle h∗ that was an explicit output of the hash oracle Oh . Let us assume h∗ = hk∗ for some k ∗ ∈ {1, . . . , qh }. This constrains its polynomial to the simple, non-composite form: Ph∗ = Phk∗ = rk∗
(5)
where rk∗ is a fresh random polynomial whose value is unknown to A. The two forged signature components, s∗lt and s∗ep,j ∗ , on the other hand, are constructed by A from all available information. Their corresponding polynomials, Ps∗lt and Ps∗ep,j ∗ , can therefore be expressed as two distinct linear combinations of all polynomials known to the adversary. These are precisely the general forms we defined previously, which we restate here for clarity: qh
Ps∗lt = αlt + βlt y + ∑ δk Phk qs +qu
+ ∑ γi Pslt,i + i=1
∑ ηi Psep,i + ∑
i=1
cj z j
j ∈Qcorrupt
(6) qh
Ps∗ep,j ∗ = αep + βep y + ∑ δk′ Phk qs
i=1
(cj + c′j )zj
j ∈Qcorrupt
= rk∗ · (x + m∗ y + F (ctx∗ , j ∗ )zj ∗ ) This equation represents the fundamental constraint that the adversary must satisfy. The left-hand side represents the total polynomial the adversary can construct, while the righthand side represents the target polynomial required for a valid forgery. Analysis of Coefficients. The analysis proceeds by comparing the coefficients of the indeterminates on both sides of our main polynomial identity, Eq. (8). To do this, we must first substitute the definitions of the signature component polynomials issued by the oracles: • Long-term components: Pslt,i = Phi · (x + mi y)
Substituting these into the left-hand side (LHS) of Eq. (8) allows us to group terms by the indeterminates x, y, and the various zj . We then equate the resulting coefficients with those on the right-hand side (RHS), which are determined by the target polynomial rk∗ · (x + m∗ y + F (ctx∗ , j ∗ )zj ∗ ). The main identity is: qh
qs +qu
∑ ηi′ Psep,i + ∑
i=1
∑
(αlt + αep ) + (βlt + βep )y + ∑ (δk + δk′ )Phk
k=1
+ ∑ γi′ Pslt,i +
i=1
+
• Epoch-specific components: Psep ,i = Phi · F (ctxi , j)zj
k=1
qs
(8)
∑ (ηi + ηi′ )Psep,i
+
k=1
c′j zj
qs
+ ∑ (γi + γi′ ) Phi x
j ∈Qcorrupt
i=1 qs +qu
(7) +
The coefficients in these combinations (the α, β, δ, γ, η, c values) are all chosen by the adversary A.
∑ (ηi + ηi′ ) Phi (mi y + Fi zji )
(9)
i=1
+
∑
′
(cj + cj )zj
j ∈Qcorrupt
The Main Polynomial Identity. A valid forgery, consisting of the tuple (m∗ , ctx∗ , h∗ ) and the signature pair (s∗lt , s∗ep,j ∗ ), must satisfy the core verification identity from Eq. (4): Ps∗lt + Ps∗ep,j ∗ = Ph∗ · (x + m∗ y + F (ctx∗ , j ∗ )zj ∗ ).
|
{z
}
LHS: Adversary’s Constructed Polynomial (Sum of Forged Components) ∗ ∗ ∗ ∗ ∗ ∗
= rk x + rk m y + rk F zj | {z } RHS: Target Forgery Polynomial
We now equate the coefficients of each indeterminate on both sides of this identity. 1. Coefficients of the indeterminate x: The indeterminate x is special because it only appears in the long-term signature components, Pslt,i . • LHS coefficient of x: This term arises exclusively from the expansion of ∑(γi +γi′ )Pslt,i = ∑(γi +γi′ )Phi x. The s resulting coefficient of x is thus ∑qi=1 (γi + γi′ )Phi . • RHS coefficient of x: The coefficient is clearly rk∗ . s (γi + γi′ )Phi = Equating these gives the formal identity: ∑qi=1 rk∗ . Since each Phi = ri is a distinct random indeterminate
(and rk∗ is one of them), this equality can only hold if the coefficients match exactly. This forces: • γk∗ + γk′ ∗ = 1 • γi + γi′ = 0 for all i ̸= k ∗ 2. Coefficients of the uncorrupted secret zj ∗ : This is the most critical step, as it involves the secret zj ∗ for the uncorrupted target epoch j ∗ , which is unknown to the adversary. • LHS coefficient of zj ∗ : The term zj ∗ can only arise from the expansion of epoch-specific components ∑(ηi + ηi′ )Psep,i for those queries i that were made in the target epoch (i.e., where ji = j ∗ ). The resulting coefficient is ∑i s.t. ji =j ∗ (ηi + ηi′ )Fi Phi . Note that the term ∑(cj + c′j )zj does not contribute, as by definition of a valid forgery, j ∗ ∈ / Qcorrupt . • RHS coefficient of zj ∗ : F (ctx∗ , j ∗ )rk∗ = F ∗ Phk∗ .
The
coefficient is
′ ∗ (η + η )F P
= F ∗P
Equating these gives: ∑i s.t. ji =j i i hi hk ∗ . i Again, by comparing the coefficients of the indeterminates Phi , we are forced to conclude: • (ηk∗ + ηk′ ∗ )Fk∗ = F ∗ , which requires that the query k ∗ must have been for the target epoch, so jk∗ = j ∗ . • (ηi +ηi′ )Fi = 0 for all other queries i ̸= k ∗ made in epoch j∗. 3. Coefficients of the indeterminate y: • LHS coefficient of y: This comes from two places: the standalone term (βlt + βep ) and the expansion of the epoch-specific components, which contributes ∑(ηi + ηi′ )mi Phi . The total coefficient is (βlt + βep ) + qs +qu (ηi + ηi′ )mi Phi . ∑i=1 • RHS coefficient of y: The coefficient is m∗ rk∗ = m∗ Phk∗ . Equating these and comparing coefficients of the Phi indeterminates (and the constant term) yields:
• (ηk∗ + ηk′ ∗ )mk∗ = m∗ • (ηi + ηi′ )mi = 0 for all i ̸= k ∗ • βlt + βep = 0 4. The Final Contradiction: Let’s assemble our findings. The coefficient analysis has forced the adversary’s choices to satisfy the following conditions simultaneously for some query index k ∗ : 1. The query k ∗ must have been made for the target epoch: jk ∗ = j ∗ . 2. The forged message m∗ and context F ∗ must be related to the query’s message mk∗ and context Fk∗ via a single scaling factor C = (ηk∗ + ηk′ ∗ ). Specifically, m∗ = C · mk∗ and F ∗ = C · Fk∗ . By definition, a forgery requires that the adversary produces a signature on a message-context pair (m∗ , ctx∗ ) for which it has not previously requested a signature. However, from our analysis, if we assume F behaves as a random oracle, then F ∗ = C · Fk∗ implies that either C = 1 and ctx∗ = ctxk∗ , or the adversary has found a non-trivial linear dependency in the outputs of the random oracle, which is impossible except with negligible probability. If we must have C = 1, then the conditions become: • m∗ = m k ∗ • F ∗ = Fk∗ =⇒ F (ctx∗ , j ∗ ) = F (ctxk∗ , jk∗ ). Given j ∗ = jk∗ , this implies ctx∗ = ctxk∗ . This means the forged tuple (m∗ , ctx∗ ) is identical to the tuple (mk∗ , ctxk∗ ), which was the subject of the k ∗ -th signature query. This directly contradicts the condition that the forgery must be for a new, un-queried message-context pair. Therefore, no such set of adversary-chosen coefficients can exist, and the adversary cannot construct a valid forgery. The remaining coefficients must all be zero to satisfy the rest of the main identity, reinforcing that no deviation is possible. Bounding the Probability of Accidental Collisions. The final way for A to win is if two formally distinct polynomials, PA and PB , happen to evaluate to the same value over Fp once the secret variables are instantiated, causing the algebraic constraints to break down. We can bound the probability of such an "accidental collision" using the Schwartz-Zippel lemma. First, we count the total number of distinct polynomials available to A. These come from: • The 2 base polynomials {1, y} derived from the public parameters. The secret polynomial x is never known to A in isolation.
• The polynomials obtained from oracle queries. This pool includes qh hash polynomials {Phk }, qs long-term signature polynomials {Pslt,i }, qs + qu epoch-specific signature polynomials {Psep,i }, and qc corrupted secret key polynomials {zj }. Let q = qh +2qs +qu +qc be the total number of distinct polynomials from oracles. • Up to qG additional polynomials generated by A through its own computations (linear combinations of existing polynomials). By the Schwartz-Zippel lemma, the probability of any single non-trivial polynomial identity PA − PB = 0 holding true is at most dmax /p. We apply a union bound over all possible pairs of distinct polynomials to bound the total probability of any such collision occurring: 2 + q + qG dmax Pr[A wins ] ≤ · 2 p =
D.2
(2 + q + qG )(2 + q + qG − 1) (2 + q + qG )2 < p p (10)
Proof of Theorem 4.1
We now present the formal security analysis of the unforgeability property of EB-PS. Proof. We prove the EUF-eCMA security of our scheme by constructing a reduction algorithm R that uses any adversary A against the scheme to break the STB-GPS assumption. The reduction R interacts with the adversary A on one side, and the challenger C of the STB-GPS security game on the other. The security of our scheme is established using techniques similar to those in the security proofs for multi-message signatures, such as in [58] and [56]. Specifically, our proof follows the chosen-key simulation paradigm, where R uses the challenge from C to generate a simulated key for A, and later extracts a solution to the STB-GPS problem from A’s forgery. Setup. The simulator R receives a challenge from the STBGPS challenger C. This consists of the public parameters pp (containing groups G1 , G2 with generators u, v), a public key PKC = (XC , YC , {ZC,j }Tj=1 ), where XC = v x , YC = v y , ZC,j = v zj , and access to oracles for signing, updating, and corruption. The secrets (x, y, {zj }) are unknown to R. To simulate the environment for the adversary A, R defines a target public key PK∗ under the chosen-key model. First, it $
samples a random value ν ← Fp . It then provides A with pp and the simulated public key PK∗ defined as follows: • The long-term public key is set to lvk where: X∗ ← X C = v x Y∗ ← YC · v ν = v y+ν
∗
= (X∗ , Y∗ ),
• For each epoch j ∈ [1, T ], the epoch public key is set to epk∗j ← ZC,j = v zj . This implicitly defines the adversary’s target secrets as x∗ = x and y ∗ = y + ν, while the epoch secrets remain unchanged, zj∗ = zj . The generator for G1 is set to u. Finally, R simulates two programmable random oracles, H : {0, 1}∗ → G1 and F : {0, 1}∗ → Fp . R maintains lists LH and LF of queryresponse pairs to ensure consistency. The oracle F will be used as the pivot for the Forking Lemma. Queries. The simulator R responds to the adversary A’s queries as follows. Signing Queries. When the adversary A requests a signature on a message m ∈ Fp for an epoch j (with aux, ctx), the simulator R must produce a valid signature σ ∗ under the target public key PK∗ . R proceeds as follows: 1. Randomness Generation. R generates two fresh ran$
dom exponents, γ, δ ← Fp . It also obtains h from the random oracle on input aux. 2. Challenger Query. R queries the challenger’s signing oracle Osign with (m, h, γ, δ, ctx, j). The challenger C, using its secrets (x, y, zj ), computes and returns the two signature components: slt ← (hγ )x+ym sep,j ← (hδ )zj ·F (ctx,j ) 3. Signature Transformation. R receives slt and sep,j from the challenger. To make the signature valid under the target key PK∗ , R must adjust the long-term component. The epoch-specific component requires no change since zj∗ = zj . The simulator computes the final signature components for the adversary, denoted with a star: • The long-term part s∗lt is computed by applying a corrective term using the secret offset ν: s∗lt ← slt · (hγ )νm • The epoch-specific part remains unchanged: s∗ep,j ← sep,j 4. Return Signature. R assembles the final signature σ ∗ = (hγ , hδ , s∗lt , s∗ep ) and returns it to A. Correctness of the Simulation. The signature σ ∗ is valid under PK∗ = (X∗ , Y∗ , {Z∗j }) because the components correctly align with the implicitly defined secrets (x∗ , y ∗ , zj∗ ).
For the long-term part, the verifier checks against x∗ = x and y ∗ = y + ν: ∗
∗
(hγ )x +y m = (hγ )x+(y+ν )m = (hγ )x+ym · (hγ )νm = slt · (hγ )νm = s∗lt For the epoch-specific part, the check is against z ∗ = z , which j
j
is trivially correct: ∗
(hδ )zj ·F (ctx,j ) = (hδ )zj ·F (ctx,j ) = sep,j = s∗ep,j Thus, the signature σ ∗ is a perfect simulation from the adversary’s perspective. Update Queries. The adversary A provides a previously obtained signature tuple (j, m, h, ctx, h′ , h′′ ) to request the epoch component for j + 1. The simulator R must respond using the challenger’s oracle, as it does not know the epoch secret zj +1 . 1. Forwarding the Query. R takes the request from A, which includes the randomized base h′′ (where h′′ = hδ for some δ chosen by the challenger during the initial signing). R forwards the entire valid request to the challenger’s update oracle, Oupdate . 2. Challenger Interaction. The challenger C uses the provided h′′ and its own secret zj +1 to compute and return the next epoch component: sep,j +1 ← (h′′ )F (ctx,j +1)·zj+1 3. Return to Adversary. R receives sep,j +1 and returns it directly to A as s∗ep,j +1 . No transformation is needed. The crucial point is that the returned value is already consistent with the randomized base h′′ that the adversary possesses. Correctness of the Simulation. The returned component s∗ep,j +1 is perfectly simulated. It is valid under the target key PK∗ because the epoch secrets are identical (zj∗+1 = zj +1 ), and the component correctly corresponds to the randomized base h′′ = hδ . The verification check is: e(s∗ep,j +1 , v) = e((hδ )F (ctx,j +1)·zj+1 , v) = e(hδ , v F (ctx,j +1)·zj+1 ) ∗
= e(h′′ , v F (ctx,j +1)·zj+1 ) This is exactly the equation the adversary would use to verify the component, thus the simulation is flawless. Corrupt Queries. The simulator R’s response depends on which secret A requests. • Corruption of the Target Long-Term Key. If A asks for the secret key (x∗ , y ∗ ) for PK∗ , R must abort.
• Corruption of an Epoch Secret (zj∗ ). If A requests the secret for epoch j, R forwards this query to the challenger’s oracle Ocorrupt (j). The challenger returns its secret zj . Since the simulation defines zj∗ = zj , R passes this value directly to A. This is a perfect simulation. Output. Eventually, the adversary A outputs a valid, nontrivial forgery tuple (j ∗ , m∗ , h∗ , h′∗ , h′′∗ , ctx∗ , s∗lt , s∗ep,j ∗ ). Forgery Extraction via the Forking Lemma. The simulator R’s goal is to leverage this forgery to break the underlying STB-GPS assumption. The correct approach is to apply the Forking Lemma by programming the random oracle, which we assume is the function F (·, ·). 1. Identifying the Forking Point. The adversary A, in order to compute the epoch-specific signature component s∗ep,j ∗ , must query the random oracle for the value c = F (ctx∗ , j ∗ ). The simulator R, which controls the oracle, can therefore choose the output of this query. 2. Applying the Forking Lemma. R executes the following steps: 1. When A makes the crucial query for F (ctx∗ , j ∗ ), R records the state of A and provides a randomly chosen value c1 ∈ Fp as the oracle’s output. 2. With non-negligible probability, A continues and produces a valid forgery: (j ∗ , m∗ , h′∗ , h′′∗ , ctx∗ , s∗lt , s∗ep,1 ). The epoch signature component satisfies s∗ep,1 = (h′′∗ )zj ∗ ·c1 . 3. R rewinds A to the recorded state just before the oracle query. It then provides a different, randomly chosen value c2 ∈ Fp (c2 ̸= c1 ) as the output for the same query F (stx∗ , j ∗ ). 4. Since the rest of A’s random tape is unchanged, with a significant probability, it will follow a similar execution path and produce a second valid forgery: (j ∗ , m∗ , h′∗ , h′′∗ , ctx∗ , s∗lt , s∗ep,2 ). Note that the long-term component s∗lt and the randomized bases h′∗ , h′′∗ will be the same, as they were determined by A before the forking point. The new epoch signature component satisfies s∗ep,2 = (h′′∗ )zj ∗ ·c2 . 3. Extracting the Secret and Constructing the Final Forgery. The simulator R now possesses two distinct, valid epoch signature components and the corresponding oracle outputs it chose: s∗ep,1 = (h′′∗ )zj ∗ ·c1 s∗ep,2 = (h′′∗ )zj ∗ ·c2 Let the unknown value be K = (h′′∗ )zj ∗ . The equations become: s∗ep,1 = K c1 s∗ep,2 = K c2
Since the simulator knows the distinct exponents c1 and c2 , it can easily solve for K. For instance, from the first equation s∗ep,1 = K c1 , R can compute the modular inverse of c1 in Fp and find K directly: −1
K ← (s∗ep,1 )c1
The simulator has thus successfully computed K = (h′′∗ )zj ∗ , which is the core of the epoch-specific secret for the uncorrupted epoch j ∗ . The simulator has thus successfully computed K = (h′′∗ )zj ∗ , which is the core of the epoch-specific secret for the un-corrupted epoch j ∗ . Conclusion. With the extracted value K = (h′′∗ )zj ∗ , the simulator R can now construct a valid solution to present to the STB-GPS challenger. The challenger expects a solution for the tuple (m∗ , j ∗ , ctx∗ ) that consists of secret components corresponding to its own public key PKC . R constructs this solution as follows. First, R must construct the long-term component for the challenger’s key (x, y). The component s∗lt provided by the adversary is valid for the simulated key (x∗ , y ∗ ), where y ∗ = y + ∗ ∗ ∗ ν. Specifically, s∗lt = (h′∗ )x+(y+ν )m = (h′∗ )x+ym · (h′∗ )νm . To obtain the component valid for the challenger’s key, R performs a reverse transformation: ∗
slt,final ← s∗lt · (h′∗ )−νm ∗
This yields (h′∗ )x+ym , which is the correct long-term secret component relative to the base h′∗ that solves the first part of the STB-GPS challenge. Second, let cchal = F (ctx∗ , j ∗ ) be the value that the challenger’s random oracle would output. R uses the extracted value K to compute the final epoch component: c sep,final ← K cchal = (h′′∗ )zj ∗ chal = (h′′∗ )zj ∗ ·cchal This is the correct epoch secret component relative to the base h′′∗ . By presenting a valid forgery tuple (j ∗ , m∗ , h∗ , h′∗ , h′′∗ , ctx∗ , slt,final , sep,final ) containing these correctly formed components to the challenger, R breaks the STB-GPS assumption.
E
Entities and Oracles
The challenger C maintains several lists to track the game state: • HU, CU : honest and corrupted users, respectively. • HCI, CCI: honest and corrupted credential issuers, respectively. • Luk : a list of users’ keys. • Lcred : credential records, where each entry contains (cred, attr, uid) representing the issued credential, its attributes, and the user’s identifier. An entry may be ⊥ if the corresponding credential has not yet been issued.
• OHCI (i): For a given identifier i, this oracle creates a new honest credential issuer. It first checks whether i exists in HCI ∪ CCI, outputting ⊥ if true. Otherwise, it generates issuer keys through KGen(pp, i) and TKGen(pp, i), registers the complete key set (i, lski , lvki , tski , tvki ) to HCI, and outputs (lvki , tvki ). • OCCI (i): This oracle corrupts issuer i, subject to (lvk′ , tvk′j ) remaining uncorrupted. For non-existent issuers (i ∈ / HCI ∪ CCI), it creates a new entry in CCI. For honest issuers (i ∈ HCI), it transfers i to CCI and exposes (lski , tski,j ). • OUser (id, S): This oracle initializes a new user with identity id and a set S = (mi , lvki )i∈[ℓ] , where mi denotes the attribute to be signed. For non-existent users (id ∈ / HU ∪ CU), it creates a fresh entry via (usk, uvk, aux) ← UKGen, registers the user in HU, stores the key information in Luk , and returns uvk. Otherwise, outputs ⊥. • OCU (id): This oracle corrupts user id. For unregistered users (id ∈ / HU), it creates a new entry in CU. For honest users (id ∈ HU), it transfers id to CU and exposes usk along with tuples (id, mi , credi ) from Lcred [id]. • OObtIss (id, i, mi ): This is an honest issuing oracle accepts a user identity id, an issuer identity i, and attribute mi as input. It first verifies that id ∈ HU and i ∈ HCI, returning ⊥ if either check fails. Upon successful verification, it retrieves the user’s secret key usk from Luk [id] and the issuer’s secret key lski from HCI. The oracle then executes the issuing protocol between the user and issuer for the specified attributes mi , where: [CredObtain(id, aux, mi ) ↔ CredIssue(j, lski , tski,j )] → (credlt,i , credep,i,j )
Add the entry (id, mi , credlt,i , credep,i,j ) to Lcred . • OObtain (id, i, mi ): This is an honest obtaining oracle with malicious issuer. The oracle accepts a user identity id, an issuer identity i, and an attribute mi as input. It first verifies that id ∈ HU and i ∈ CCI, returning ⊥ if either check fails. Upon successful verification, it retrieves the user’s secret key usk from Luk [id]. The oracle then executes the obtaining protocol between the honest user and the malicious issuer for the specified attributes mi . The user side of the protocol is simulated honestly, while the adversary controls the issuer’s actions, where: ⟨CredObtain(id, aux, mi ) ↔ A⟩ → (credlt,i , credep,i,j ) If credlt,i = ⊥ or credep,i,j = ⊥, return ⊥. Otherwise, append (id, mi , credlt,i , credep,i,j ) to Lcred . • OIssue (id, i, mi ): This oracle executes the credential obtaining protocol between a malicious user and an honest issuer. It accepts a user identity id, an issuer identity i, and an attribute mi as input. The oracle first verifies that id ∈ HU and i ∈ CCI, returning ⊥ if either check fails. Upon successful verification, it retrieves the issuer’s secret key lsk from HCI. The oracle then executes the obtaining protocol between the honest user and the malicious issuer for the
specified attribute mi . The user side of the protocol is simulated honestly using usk, while the adversary controls the issuer’s actions. ⟨A ↔ CredIssue(j, lsk, tskj )⟩ → (credlt,i , credep,i,j ) Add the entry (id, mi , credlt,i , credep,i,j ) to Lcred . • OAnch-b (id0 , id1 , M): This oracle takes as inputs the identities of two honest users who have the same user attribute set D. If (id0 , id1 ) ∈ / HU ∨ Mid0 ̸= Mid1 , return ⊥. The oracle parses Lcred [id0 ] = (id0 , {m0,i , cred0,lt,i , cred0,ep,j }i∈[ℓ] ), Lcred [id1 ] = (id1 , {m1,i , cred1,lt,i , cred1,ep,j }i∈[ℓ] ). The oracle then computes credagg,j,b (definition of aggregation process). Finally, the oracle runs the interactive protocol ⟨CredShow(uskb , pol, {lvki , tvki,j , mb,i }i∈[ℓ] , credagg,j,b , M) ↔ A⟩ , where b ∈ {0, 1}, and outputs the result b′ . • OBlch-b (id, {m0,i }i∈[ℓ] , {m1,i }i∈[ℓ] ): This oracle takes as inputs two different sets of attributes {m0,i }i∈[ℓ] , {m1,i }i∈[ℓ] for the honest user identity id. If id ∈ / HU, return ⊥. The oracle runs the interactive protocol: ⟨CredObtain(id, aux, mi ) ↔ CredIssue(j, lski , tski,j )⟩ → (credlt,i , credep,i,j ) Then computes credagg,j,b (definition of aggregation process), and outputs b′ . • OUpdEp (stj ): This oracle facilitates the transition from epoch j to epoch j + 1. It accepts the current system state stj as input and executes the following procedure: For each issuer i ∈ [n], it generates new epoch-specific key pairs (tski,j +1 , tvki,j +1 ) ← TKGen. Subsequently, the oracle updates the epoch-specific keys in both HCI and CCI, replacing (tski,j , tvki,j ) with (tski,j +1 , tvki,j +1 ). If any operation within this process fails, the oracle returns ⊥. • OObtIssEp (id, i, j + 1): This is an honest issuing oracle accepts a user identity id, an issuer identity i, and an epoch index j as input. It first verifies that i ∈ HCI and Lcred [id] ̸= ⊥, returning ⊥ if either check fails. Upon successful verification, it retrieves the issuer’s epoch-specific secret key tski,j +1 from HCI. The oracle then executes an epoch-specified credential for update, where: CredIssueEp(tskj , id) → credep,i,j +1 Update the entry (id, mi , credlt,i , credep,i,j ) in Lcred to (id, mi , credlt,i , credep,i,j +1 ). • OIssEp (id, i, j): This is an malicious issuing oracle accepts a user identity id, an issuer index i, and an epoch index j as input. It first verifies that i ∈ CCI and Lcred [id] ̸= ⊥, returning ⊥ if either check fails. Upon successful verification, it retrieves the issuer’s epoch-specific secret key tski,j +1 from CCI. The oracle then executes an epoch-specified credential for update, where: CredIssueEp(tskj , id) → credep,i,j +1
Update the entry (id, mi , credlt,i , credep,i,j ) in Lcred to (id, mi , credlt,i , credep,i,j +1 ). • OCredShow (k, j, pol, M): This oracle takes as input an issuance index k, an epoch index j, a policy pol, and an attributes-subset M. It first parses Lcred [k] to obtain (id, mk , credlt,k , credep,k,j ). If id ∈ / HU, it returns ⊥. Otherwise, it executes the credential showing protocol CredShow between the honest user (with identity id) and the adversary A, where: CredShow(tg, {mi , lvki , tvki,j }i∈[ℓ] , credagg,j , M, π) ↔ A
F
Security Analysis of MA-ACEW
Building on the security model described previously, we provide formal proofs for the three security properties of MAACEW: unforgeability, anonymity, and blindness.
F.1
Proof of Theorem 5.1
Proof. Intuitively, an adversary A could attempt to break the unforgeability of MA-ACEW by forging an EB-PS signature on the challenge public key, which would allow verification without possessing the required attributes. We prove that if there exists an adversary A that wins the unforgeability game (Fig. 1) with non-negligible probability ϵ, then we can construct a reduction R that breaks the unforgeability of the underlying EB-PS scheme. The reduction proceeds as follows: Setup. R interacts with a challenger C in the unforgeability game of EB-PS while simultaneously simulating the MAACEW unforgeability game for adversary A. Initially, R receives from C the values (lvk, tvk1 ), where lvk = (X = v x , Y = v y ) and tvk1 = Z1 = z1 represents the initial time epoch, along with the public parameters pp of the bilinear group BG. R then constructs the challenge key as vk′ = (X, Y, Z1 ) and forwards (pp, vk′ ) to A. All oracle queries are handled as in the real game, with the following exception: instead of using the challenge signing key sk′ , R forwards relevant signing queries to the signing oracle provided by the EB-PS unforgeability game: OUser (id): On input a user identity id, R first checks if id ∈ HU or id ∈ CU. If so, return ⊥. Otherwise, R generates a fresh user key pair (usk, uvk) ← UKGen and creates the auxiliary information aux using commitments and ElGamal paris. R then adds the tuple (id, (usk, uvk, aux)) to both HU and Luk respectively, and returns uvk. OObtlss (i, id, mi ): On input issuer index i, user identity id, and attribute mi , if id ∈ / HU or i ∈ / HCI ∪ {vk′ }, return ⊥. Otherwise, if vki ̸= vk′ , R retrieves (usk, uvk, aux) from Luk and (lsk, tsk1 ) from HCI, then computes σlt,i ← SignLt(lsk, uvk, aux, mi ) and σep,i,1 ← SignEp(tsk1 , uvk, aux). If lvk′i = vk′ , R forwards the
query to the signing oracle of EB-PS, obtaining σlt,i′ ← OSignLt (m′i , aux, uvk), σep,i′ ,1 ← OSignEp (uvk, aux), and adds (id, mi , credi ) to Lcred , where credi = (σlt,i , σep,i,1 , uvk).
DDH assumption and the zero-knowledge property of the proof system. The former ensures that a credential tuple (σ, tg) can be perfectly randomized as (σ ′ = ((h′ )r , sr ), tgr ),
OIssue (i, id, mi ): On input issuer index i, user identity id, and attribute mi , if id ∈ / CU or i ∈ / HCI ∪ {vk′ }, return ⊥. Other′ wise, if lvki ̸= vk , compute σlt,i ← SignLt(lsk, uvk, aux, mi ) and σep,i,1 ← SignEp(tsk1 , uvk, aux). Else, ask the queries σlt,i′ ← OSignLt (m′i , aux, uvk) and σep,i′ ,1 ← OSignEp (uvk, aux) of EB-PS, add the entry (id, mi , credi ) to Lcred , where credi = (σlt,i , σep,i,1 , uvk).
where r ← F∗p , statistically obfuscating all information about the original signature-tag pair. Here, tg serves as a pseudonym during interactions. The latter guarantees that the proof πtg leaks no information about the witness. In the anonymity experiment, the witnesses used in computing πtg are valid for both b ∈ {0, 1}, and the signature-tag pairs undergo proper randomization. Consequently, the adversary’s view comprises solely of random elements that are identically distributed, independent of b. This implies that no probabilistic polynomial-time (PPT) adversary can distinguish between the two cases with non-negligible advantage. We formalize this intuition through a sequence of games. Let S denote the event that the adversary correctly guesses bit b, with Si representing this event in Gamei . The proof evolves through the following key transformations: Game0 : This is the anonymity game as given in Fig. 2. Game1 : We change the way we generate proofs in the original anonymity game. Instead of using real proofs, we use simulated proofs for all NIZK(tg) in CredObtain and CredShow respectively. Game2 : We change the way we run queries in the experiment. Let qu be the number of OUser queries. At the beginning of Game2 , we pick k ← [qu ] to guess when the challenge user (who owns the ib -th credential) is registered. Modify oracles as follows:
OObtlssEp (id, i, stj +1 ): On input a user identity id, an issuer index i, and the new epoch state statej +1 , if id ∈ / HU or i∈ / HCI ∪ vk′i , return ⊥. Otherwise, if tvki ̸= tvk′i , retrieve (usk, uvk, aux) from Luk and tski,j +1 from HCI, then compute σep,i,j +1 ← SignEp(tski,j +1 , uvk, aux). If tvki = tvk′i , query the epoch-specific signing oracle to obtain σep,i′ ,j +1 ← OSignEp (uvk, aux). Finally, securely erase the previous epoch signature σep,i,j and update the credential to Lcred , reset credi = (σlt,i , σep,i,j +1 , uvk). OIssEp (id, i, stj +1 ): On input a user identity id, an issuer index i, and the new epoch state stj +1 , if id ∈ / CU or i ∈ / HCI ∪ {vk′ }, return ⊥. Otherwise, if tvki ̸= tvk′ , compute σep,i,j +1 ← SignEp(tski,j +1 , uvk, aux). If tvki = tvk′ , query the epoch-specific signing oracle to obtain σep,i′ ,j +1 ← OSignEp (uvk, aux). Finally, securely erase the previous epoch signature σep,i,j and update the credential to Lcred , reset credi = (σlt,i , σep,i,j +1 , uvk). Upon receiving a valid showing proof (avk, cred∗ , M, tg∗ ) with its associated proofs (πb , πIPA , πtg∗ ), the reduction R leverages the knowledge soundness of the underlying proof systems to extract the necessary witnesses. Specifically, from the successful verification of πIPA , whose knowledge soundness is proven in [29], R extracts a bit vector b satisfying w j ′ , b ⟩ ≥ Wacc . Similarly, as πtg∗ is a Zero⟨ppk x , b ⟩ = X and ⟨w Knowledge Proof of Knowledge, R extracts the exponents (γ ∗ , δ ∗ ) from it. By the unforgeability definition, no credentials held by corrupt users can be valid for the attribute set M. Formally, for all credentials credi,id on mi,id and uvk with id ∈ CCU, we have S M ̸⊆ i∈[ℓ] mid,i . Consequently, at least one key in vki ∈ avk must be the challenge key, with its corresponding attribute in mi ∈ M. R then retrieves all (lski , tski ) ∈ HCI ∪ CCI corresponding to (lvki , tvki ) ∈ CI′ for i ∈ [ℓ], and constructs ask = {lski , tski }i∈[ℓ] . This process yields a valid forgery (avk, (usk∗ , tg∗ ), M, ask, σ ∗ ) against our signature scheme, thereby breaking the unforgeability of EB-PS and concluding our proof.
F.2
Proof of Theorem 5.2
Proof. The anonymity of our scheme stems from two key properties: the unlinkability of EB-PS signatures due to the
$
• OUser (id, S): As in Game1 , but if this is the k-th call then, setting id∗ ← id. • OCU (id): If id ∈ CU, it returns ⊥ (as in the previous games). If id = id∗ then the experiment stops and out$
puts a random bit b′ ← {0, 1}. Otherwise, if id ∈ HU, it returns user usk and credentials and moves id from HU to CU . • OAnch-b (id0 , id1 , M): If id∗ is not in the credential list Lcred [idb ], the oracle game terminates and outputs the guess b′ . Game3 : We modify the scheme by altering the sampling method for the tag tg. Instead of deriving it from the credential, we randomly generate tg. Game4 : We no longer use the stored credential (signature) and tag (idb , mb , credb ) from the list Lcred [idb ] to perform RndSigTag. Instead, we directly generate new random signatures. Game5 : When the challenge oracle OAnch-b is called, it no longer generates the credential pair based on the identity idb . Instead, it constructs a randomized credential pair (credsim , tgsim ) independent of the bit b. All other components of the experiment remain unchanged from Game4 .
Game0 → Game1 : By perfect zero-knowledge of NIZK, we have that: Pr[S1 ] = Pr[S0 ] Game1 → Game2 : There exists at least one anonymity query with input (id0 , id1 , M) where id0 , id1 ∈ HU. When id∗ = idb , which occurs with probability q1u , the game continues without abortion. Moreover, idb must remain uncorrupted prior to this query (idb ∈ HU), and any subsequent corruption attempts on id∗ return ⊥. Therefore, combining both cases yields: When id∗ is selected independently of the challenge bit idb (which occurs with probability 1 − q1u ), S2 maintains at least probability 12 . In the case where id∗ = idb (occurring with probability q1u ), the view of A is identical to Game1 , and thus the success probability is exactly Pr[S1 ]. Combining these cases yields, we have: 1 1 1 Pr[S2 ] ≥ (1 − ) + · Pr[S1 ] 2 qu qu Game2 → Game3 : The difference between these two games is that we use freshly generated tag tgfresh,b , which are indirectly guaranteed by the DDH assumption. The oracles are simulated as in Game2 , except for the following oracle: OUser (id, S): As in Game1 , but if this is the k-th call then, setting id∗ ← id, it sets usk[id] ← ⊥ and uvk ← tgfresh . OAnch-b (id0 , id1 , M): This oracle works as in Game2 , except that for id∗ = Lcred [idb ], the game generates a random tag tgfresh,b instead of using the stored one. The game selects b and sends (tgb , credb , π) to A, then receives b′ from A. Let ϵDDH denote the advantage of solving the DDH problem and qA be the number of queries to the OAnch-b oracle. Apart from the adversary’s advantage in solving the DDH problem, their success probability might also increase if certain bad events cause the simulation to fail. The total probability of such events is bounded by (1 + 2qA )/p, where p is the order of the underlying finite field Fp from which random elements are chosen. The 1 term corresponds to a one-time failure probability during the initial setup, while the 2qA term accounts for potential failures across the qA oracle queries, where each query involves two random choices that could break the simulation. Thus we have: | Pr[S2 ] − Pr[S3 ]| ≤ ϵDDH (λ) + (1 + 2qA )
1 p
Game3 → Game4 : Credentials obtained from RndSigTag are identically distributed for all valid tuples (M, tg∗ , vk, cred∗ ). We thus have: Pr[S3 ] = Pr[S4 ] Game4 → Game5 : The only modification is in the generation of the challenge credential. In Game5 , the credential, which was honestly generated for identity idb Game4 , is now produced by a simulation algorithm, rendering its distribution independent of the bit b. The computational indistinguishability
between Game4 and Game5 is based on the DDH assumption. It follows that for any adversary A, | Pr[S4 ] − Pr[S5 ]| ≤ ϵDDH (λ) Analysis of Game5 : In this final game, the challenge credential pair (credsim , tgsim ) is generated independently of the challenge bit b. Therefore, the adversary’s entire view is statistically independent of b. This implies the adversary has no advantage over a random guess. Thus, Pr[S5 ] = 12 . Conclusion: We can now bound the adversary’s advantage in the original game, AdvA (λ) = | Pr[S0 ] − 1/2|. By combining the (in)equalities from the game sequence, we have: -b AdvANO (λ) = | Pr[S0 ] − 1/2| A
= | Pr[S1 ] − 1/2| 1 1 1 = qu Pr[S2 ] − 1− − 2 qu 2 ≤ qu | Pr[S2 ] − Pr[S3 ]| + | Pr[S3 ] − Pr[S4 ]| ! + | Pr[S4 ] − Pr[S5 ]| + negl(λ) 1 + 2qA ≤ qu ϵDDH (λ) + + 0 + ϵDDH (λ) + negl(λ) p ≤ 2qu · ϵDDH (λ) + negl(λ) The preceding analysis follows a standard game-hopping argument. For a more rigorous and detailed treatment of the probability bounds in such proofs, we refer the reader to [38]. Since ϵDDH (λ) is a negligible function in the security parameter λ, and qu is polynomial, the adversary’s total advantage is negligible. This completes the proof.
F.3
Proof of Theorem 5.3
Proof. The blindness of our scheme stems from two key properties: the IND-CPA of ElGamal encryption and the zeroknowledge property of the proof system. We formalize the process with the following sequence of games: Game0 : This is the blindness game as given in Fig. 3. Game1 : We modify the behavior of the challenge oracle OBlch-b . Instead of generating real proofs, we simulate proofs. All other computations remain unchanged. Game2 : In this game, we further alter the challenge oracle OBlch-b . Instead of encrypting the actual attributes {mb,i }i∈[ℓ] , it now encrypts freshly sampled random messages {ri }i∈[ℓ] from the message space. Game0 → Game1 : The only difference between Game0 and Game1 is the use of simulated proofs instead of real ones in the challenge oracle. Because the NIZK system provides perfect zero-knowledge, the distribution of real proofs is identical to the distribution of simulated proofs. Therefore, the
adversary’s view in Game1 is statistically identical to its view in Game0 . Thus, we have: Pr[S0 ] = Pr[S1 ] Game1 → Game2 : The transition from Game1 to Game2 is based on the IND-CPA security of the encryption scheme. In Game1 , the oracle encrypts a real message {mb,i }, while in Game2 , it is modified to encrypt a random message ri (sampled from the message space) instead. The IND-CPA property ensures that these two games are computationally indistinguishable. Therefore, the difference in the adversary’s success probabilities is bounded by the advantage of the encryption scheme: -CPA | Pr[S1 ] − Pr[S2 ]| ≤ ϵIND (λ) Enc Analysis of Game2 : In this game, the output of the challenge oracle OBlch-b (both the ciphertext and the simulated proofs) is computed based on a random message that is completely independent of the challenge bit b. Consequently, the adversary’s entire view contains no information about b. Thus, Pr[S2 ] = 12 . Conclusion: By combining the above steps, we can bound the adversary’s advantage in the original experiment: -b AdvBLI A (λ) = | Pr[S0 ] − 1/2|
= | Pr[S1 ] − 1/2| ≤ | Pr[S1 ] − Pr[S2 ]| + | Pr[S2 ] − 1/2| -CPA ≤ ϵIND (λ) + |1/2 − 1/2| Enc -CPA = ϵIND (λ) Enc
Since we assume the encryption scheme is IND-CPA secure, -CPA (λ) is negligible for any probabilistic the advantage ϵIND Enc polynomial-time adversary. We conclude that the adversary’s advantage in the blindness game is also negligible. This completes the proof.
First, the user generates a single ElGamal key pair (esk, evk) = (d, ζ = ud ). For each attribute mj where j ∈ [1, t], the user samples random values kj , oj ∈ Fp and computes: • An ElGamal encryption of the attribute: cj = Enc((h′ )mj , evk) = (ukj , ζ kj · (h′ )mj ). o
• A Pedersen commitment to the attribute: cmj = umj h1j . The user then generates a single, comprehensive proof πCIi that attests to the well-formedness of all encrypted attributes for issuer CIi : πCIi = ZKPOK{(d, m1 , . . . , mt , o1 , . . . , ot , k1 , . . . , kt ) : ζ = ud ∧ o
∀j ∈ [1, t] : cmj = umj h1j ∧ ∀j ∈ [1, t] : cj = (ukj , ζ kj · (h′ )mj )} The issuing phase between the user and issuer CIi is updated for the vector of attributes: • The user transmits the relevant parts of (tg, aux, πCIi , πtg ) to the credential issuer CIi . Here, aux now contains the set of all ciphertexts {cj }j ∈[1,t] and commitments {cmj }j ∈[1,t] intended for this issuer. • The issuer CIi parses aux and verifies the proofs. Upon suc˜ lt,i = (σ̃1 , σ̃2 ), cess, it computes the blinded credential cred where: t
σ̃1 = (h′ )xi ∏ (cj,2 )yj,i j =1
t
σ̃2 = ∏ (cj,1 )yj,i j =1
˜ lt,i to the user. The issuer then sends cred
G G.1
Additional Properties Multi-Attribute Credential Issuance For a Single Issuer
We can note that in MA-ACEW, the secret key of issuer CIi consists of (xi , yi , zi,j ). Currently, only yi is used for signing attributes, due to the underlying structure of the signature scheme. However, this can be easily extended to a multi-message setting by expanding the issuer’s secret keys to (xi , y1,i , . . . , yt,i , zi,j ), corresponding to the verification keys (Xi , Y1,i , . . . , Yt,i , Zi,j ). With this extension, credential issuer CIi can issue credentials for the attribute vector m ⃗ = (m1 , . . . , mt ). The process is adapted as follows:
˜ lt,i = (σ̃1 , σ̃2 ) • The user receives the blinded credential cred and unblinds it to construct the final credential credlt,i = (σ1 , σ2 ). The first component is set as σ1 = h′ , and the second component is computed by removing the blinding factor: σ2 = σ̃1 · (σ̃2 )−d The final long-term credential credlt,i from issuer CIi for the message vector m ⃗ is correctly constructed as: t credlt,i = (σ1 , σ2 ) = h′ , (h′ )xi +∑j=1 mj yj,i This approach has been previously done in works such as [58] and [63].
G.2
Issuer Hiding
Issuer Hiding refers to the ability of a user to show a credential to a verifier without revealing which specific issuer has issued which credential. Instead, they only demonstrate whether a defined policy on the acceptance set of issuers is satisfied. In traditional schemes, this process may expose the credential issuer’s public key, which could leak information about the user’s privacy. For instance, if a user’s credential is issued by a specific authority (e.g., a local government), revealing this information may expose the user’s location. The issuer-hiding feature [27, 56] , works roughly as follows: Each verifier generates a policy defining a set of acceptable issuers, identified by their verification keys. This policy is represented as a collection of Structure-Preserving Signatures on Equivalence Classes (SPSEQ) [38] on the verification keys of the EB-PS. To accommodate the property, we need to consider incorporate the SPSEQ scheme. In the Gen-Policies phase, the verifier runs (vsk, vvk) ← SPSEQ.KGen(pp). Additionally, the verifier uses vsk to generate σSPS,i ← SPSEQ.Sign(vsk, lvki ) for i ∈ I, where I is the set of acceptable issuer’s public keys. The policy is set as pol = (Wacc , j, {lvki , σSPS,i }i∈I ). In the showing phase, the user selects a disclosed set M, where |M| ≤ |I|, to form a credential cred. The user then applies RndSigTag to randomize cred and tg simultaneously using randomness r. The same r is used to randomize σSPS,i ′ and lvki for i ∈ M, resulting in lvk′i , σSPS,i which remain valid signatures, but prevent the verifier from learning the original issuer. More details on this process can be found in [56]. Remark. We note that if the participant set is small or the weight space is limited, the aggregated weight Wclaim may correspond to a unique combination of issuers, potentially revealing their identities. However, we can effectively prevent this leakage by: • Padding with zero-weight issuers. The issuer universe can be expanded by appending dummy issuers with weight 0. During aggregation, users may randomly include some of these dummy issuers in proofs. Since a verifier cannot distinguish real and dummy issuers, the anonymity set grows from n to n + k, the number of consistent subsets grows combinatorially in k (≈ 2k ), which greatly complicates inference of the exact issuer set. For instance, with n = 50 active issuers and k = 100 zero-weight fillers, even when Wclaim equals the sum of genuine weights, the verifier cannot tell which subset among the n + k participants contributed. • Range Proof Disclosure. The system can disclose only that Wclaim ≥ Wacc or Wclaim ∈ [Wacc − ∆, Wacc + ∆] instead of the exact Wclaim . This disclosure can be realized using zero-knowledge range-proof techniques, requiring only minor modifications.
G.3
Selective Disclosure of Arbitrary Attributes
Recall that for clarity of presentation in Section 5.1 and Section 5.4, we assumed that all attributes are disclosed to the verifier in the Show protocol. We now detail how our MAACEW scheme supports the more general policy of selective disclosure of arbitrary attributes. This is achieved with minor modifications to the Gen-Policies and Show protocols. Concretely, the interaction is extended as follows. First, in the Show protocol, the verifier specifies a disclosure policy. This policy defines: • A set of attribute indices D that the user is required to disclose. • A predicate Φ that must be satisfied by the attributes corresponding to the hidden indices in H = U \ D, where U is the universe of all attribute indices. Correspondingly, the user, holding the full attribute message set M, partitions it based on the verifier’s policy into two disjoint subsets: • The set of disclosed messages, MD = {mi ∈ M | i ∈ D}. • The set of hidden messages, MH = {mi ∈ M | i ∈ H}. The user then reveals the messages in MD to the verifier, while simultaneously proving in zero-knowledge that their hidden messages in MH satisfy the predicate Φ. Accordingly, the Gen-Policies protocol is updated to output a policy pol defined as the tuple: pol = (j + 1, Wacc , D, Φ) where D is the set of disclosed attribute indices and Φ is the predicate that the hidden attributes (indexed by H = U \ D) must satisfy. We now detail how a user, holding their attribute set M, satisfies the requirements specified by a policy pol. To support selective disclosure, we adapt the baseline verification protocol. Recall that the original AggVerify algorithm validates a signature σagg,j = (h′ , s) on attributes M = {mi }ℓi=1 by checking: ! ! ℓ
ℓ
i=1
i=1
δ F (ctx,j ) i e h′ , ∏ (Xi · Ym , ∏ Zi,j i ) · e (h )
= e(s, v)
(11) We now partition M into a disclosed subset MD (indexed by D) and a hidden subset MH (indexed by H). Instead of revealing attributes in MH , the user computes a commitment C to them using a random blinding factor r ∈ Fp : m C = Com(MH ) = v r · ∏ Xk · Yk k (12) k∈H
The prover then derives a modified signature component s′ that allows the verifier to check the credential’s validity using
only the disclosed attributes MD and the commitment C. The new verification equation is: ! ! e h′ ,
∏ (Xi · Ymi i ) · C
i∈D
!
ℓ δ F (ctx,j )
· e (h )
?
= e(s′ , v)
, ∏ Zi,j
(13)
i=1
To determine the correct form of s′ , we substitute Eq. (12) into the left-hand side of Eq. (13): !!
∏ (Xi · Ymi i )
LHSnew = e h′ ,
· e(h′ , v r )
i∈D∪H
!
ℓ δ F (ctx,j )
· e (h )
, ∏ Zi,j i=1
′
ℓ
= e h ,∏
! i (Xi · Ym i )
ℓ δ F (ctx,j )
· e (h )
i=1
, ∏ Zi,j i=1
{z
|
!
Original LHS from Eq. (11)
}
· e((h′ )r , v) = e(s, v) · e((h′ )r , v) = e(s · (h′ )r , v) This derivation shows that the equality holds if the prover sets s′ = s · (h′ )r . The Show protocol thus requires the prover to convince the verifier of two things: that the modified signature is valid, and that the committed attributes satisfy some policy. To achieve the latter, the prover generates a comprehensive NIZK proof, πNIZK . This proof must simultaneously establish the correctness of a commitment to the hidden attributes MH and the satisfaction of a predicate Φ over these same attributes. Specifically, πNIZK demonstrates knowledge of the hidden attributes MH and the randomness r such that: 1. The commitment is correctly formed: C = v r · mk ∏k∈H Xk · Yk . 2. The attributes MH satisfy the predicate Φ. Crucially, to support arbitrary predicates, our design handles the second part by integrating a general-purpose ZK system (e.g., the efficient zk-SNARK PLONK [39]) in a black-box fashion. The proof for Φ(MH ) is generated, and πNIZK then proves that the witness used for the SNARK is the same set of attributes MH committed to in C. This design choice makes the underlying proof system for predicates a modular component, orthogonal to our core protocol, allowing it to be selected based on application-specific requirements. In summary, the prover sends the tuple (MD , C, (h′ , s′ ), πNIZK ). The verifier accepts if and only if the signature check in Eq. (13) passes and the proof πNIZK is valid.
While these additional properties provide enhanced functionalities, they also introduce increased computational costs. Therefore, practitioners can adjust the implementation of these features according to their specific practical scenarios and performance requirements.