Dynamic Group Signatures with Verifier-Local Revocation

Dynamic Group Signatures with Verifier-Local Revocation Callum London, Daniel Gardham, Constantin C˘ at˘ alin Dr˘ agan Surrey Centre for Cyber Security, University of Surrey, Guildford, United Kingdom {c.london, daniel.gardham, c.dragan}@surrey.ac.uk Abstract—Group Signatures are fundamental cryptographic primitives that allow users to sign a message on behalf of a predefined set of users, curated by the group manager. The security properties ensure that members of the group can sign anonymously and without fear of being framed. In dynamic group signatures, the group manager has finer-grained control over group updates while ensuring membership privacy (i.e., hiding when users join and leave). The only known scheme that achieves standard security properties and membership privacy has been proposed by Backes et al. CCS 2019. However, they rely on an inefficient revocation mechanism that re-issues credentials to all active members during every group update, and users have to rely on a secure and private channel to join the group. In this paper, we introduce a dynamic group signature that supports verifier local revocation, while achieving strong security properties, including membership privacy for users joining over a public channel. Moreover, when our scheme is paired with structure-preserving signatures over equivalence class it enjoys a smaller signature size compared to Backes et al. Finally, as a stand-alone contribution we extend the primitive Asynchronous Remote Key Generation (Frymann et al. CCS 2020) with trapdoors and introduce new security properties to capture this new functionality, which is fundamental to the design of our revocation mechanism. Index Terms—dynamic group signatures, membership privacy, verifier-local revocation 1. Introduction Group signatures, introduced by Chaum and Van Heyst [1], allow a group manager to delegate signing capabilities to a set of group members (i.e., signers). They are often used in commercial settings where employees sign on behalf of the company without needing to bear public responsibility, e.g., anonymous electronic cash payment [2], [3]. This is ensured by unforgeability [4], [5] where only members of that group can produce valid signatures, anonymity [5], [6], [7] such that the signature does not reveal the identity of the signer, and by traceability [5], [6], [7] where the group manager can prove that a signature was produced by a specific user. A specific example of group signatures in an organisational setting is DocuSign’s Signing Groups feature [8], but has seen uses in other domains such as vehicle-to-vehicle communication [9], [10]. Unforgeability is often enhanced to a stronger notion called non-frameability [5], [6] where honest signers cannot be framed to have produced a signature even if all other signers and group manager being corrupted. When attackers have access to leaked signer keys, then anonymity is modeled as full anonymity [4], [11], while limiting the adversary by hiding traced signatures gives the weakened definition of selfless anonymity [12], [13]. Any scheme that satisfies full-anonymity also satisfies anonymity. Full traceability [4], [11] models colluding signers and in [4] it has been shown to imply traceability and non-frameability. Depending on how groups membership is established, we have static [1], [4], [12], [14], [11]—fixed and set at setup, and dynamic [6], [7]—users can join and leave the group. Partial dynamic [5], [13] group signatures are a special case of dynamic, where the role of group manager is divided into 2 entities - one for managing membership (e.g., join and leave) and another for tracing signatures. To strengthen privacy of dynamic group signatures Backes et al. [7] have formalised membership privacy to model an adversary’s ability to identify when users join or leave the group. In the context of (partial) dynamic group signatures the joining phase can be done over public channel [15], [16], [13] or over secure and private channel [5], [7]. To enable appropriate removal of users from groups, dynamic group signatures rely on well-established revocation techniques, e.g., revocation lists (i.e., RL - public revocation list [6] and VLR - verified-local revocation [12], [14], [13]), and secret credentials [7]. Schemes based on secret credentials incorporate a huge overhead as it relies on re-issuing credentials to all signers (except those revoked), Schemes based on RL rely on the signer having up-todate revocation lists and showing that their signing key has not been revoked (e.g., using zero-knowledge proofs), while for VLR the verifier must have up-to-date information and check some anonymised signer token is not in the revocation list. Using epochs that limit frequency of reissuing credentials or size of revocation list can help mitigate some of the overhead complexity. Backes et al. [7] have shown how to design generic group signatures that satisfy membership privacy, anonymity, traceability and non-frameability. However, their design requires a private channel to perform the join and relies on inefficient secret credential revocation methods. Open problem: can generic dynamic group signatures be designed while ensuring: (1) a more efficient revocation mechanism, (2) a join phase over public channels, and (3) maintaining the same security guarantees: anonymity, traceability, non-frameability and membership privacy? We note that such a primitive would find uses in, for example, Direct Anonymous Attestation (which is a type of group signature) used within Trusted Platform Modules (TPMs). Kumar et al. [17] propose a DAA-based subscription service that uses the local revocation mechanism of the verifier to shift computational overhead away from the lowcompute TPM and to the verification server. Membership privacy would enhance the privacy guarantees in such context by preventing the identification of users as they join or leave the subscription service. Another example is for the use in privacy-enhancing crowd sensing [18] which involves individuals using mobile devices (such as smartphones or wearables) to collectively gather and share data to analyze or predict processes of common interest. Again, a verifier-local revocation mechanism is used to reduce computational burden on smart devices and onto the verifying data-collection server. Strong dynamic privacy properties prevent a user from being associated with its contributed data, and on the other hand, the tracing ability of the group manager can be used to identify those maliciously contributing false data, which is known problem in crowd sensing at scale [19]. 1.1. Contributions In this paper, we answer the open problem in the affirmative and present DGS-VLR—a generic dynamic group signature that supports verifier local revocation, and offers an efficient group membership update procedure. We achieve this using a novel two-step approach that uses unlinkable ‘intermediate’ keys that can be revoked without compromising the membership privacy of the group member. We give a generic construction based on Asynchronous Remote Key Generation [20], Signatures with Flexible Public Keys [11], Digital signatures [21], and a Non-interactive Zero-Knowledge Proof (NIZK) which we instantiate with a Structure-Preserving Signature over Equivalence Classes (SPS-EQ) [22]. This is comparable with the state-of-the-art by Backes et al. [7] as we achieve the same strong security properties (anonymity, traceability, non-frameability and membership privacy) while reducing the complexity of the group update procedure to be linear in the number of additions/revocations, instead of linear in total group members. Moreover, we provide group-based instantiations of the building blocks that allows our construction to achieve smaller signature sizes (cf. Table 1and Table 2), In particular, our signature has size: 11G1+ 5G2+ 512bits. An additional property of our scheme is that it allows users to join groups over public channels without interactive communication with the group manager. Furthermore, to enable our construction, we extend Asynchronous Remote Key Generation with trapdoors that allow linking of keys under restricted conditions. This novel functionality is fundamental to the design of our efficient revocation mechanism and could be of independent interest in other privacy-preserving primitives. 1.2. Related Work We compare our scheme with other known and state-ofthe-art group signatures in Table 1. We focus on the Type of scheme (i.e., Dynamic, partial Dynamic or Static), if they satisfy Membership Privacy (i.e., Yes, No), over what type of channel the Join procedure is performed (i.e., private, public, or non-available), the method and cost of Revocation (e.g., RL - public revocation list, VLR - verified-local revocation, and secret credential), the standard Security properties (e.g., anonymity, traceability, non-frameability), and the Size of the Signature. The cost of revocation for ruser revocations (i.e., calling rtimes the Revoke algorithm) for secret credentials is large as it need to re-issue credentials to all nactive members during each revocation - O(r·n). Schemes based on revocation lists (i.e., RL and VLR) need to only compute information for the revoked signer - O(r). However, VLR may not be preferred over RL as the verifier needs to maintain an upto-date revocation list, typically of size O(r). Bellare et. al. [4] introduced a static group signature that satisfy stronger notions of anonymity and traceability (i.e., full-anonymity and full-traceability) that imply existing definitions of anonymity, traceability, unforgeability and non-frameability. This has been extended in [5] to partial dynamic group signatures where two different entities have roles for joining and tracing, while only satisfying anonymity, traceability and non-frameability. Both [4] and [5] do not consider any mechanism for revocation. Additionally, they do not provide any instantiation for their primitives (i.e., what type of one-time signature they use) as such it’s not possible to estimate the size of the signature. Boneh and Shacham [12] introduced a static group signature with a verification mechanism called verifier-local revocation (VLR) where the verifier assumes responsibility for checking revocation. However, their scheme only satisfies a weaker notion of anonymity, called selfless anonymity, where the adversary doesn’t have access to the signer’s key. This has been extended to full-anonymity in Ishida et al. [14] via the Sign-then-Encrypt paradigm. Both [12] and [14] have an implicit traceability due to the group manager generating signing keys and revocation tokens for users during joining phase. The signature size for [12] is small, while for [14] it can’t be estimated (e.g., they rely on a complex NIZK and do not show how to instantiate it). Bootle et. al. [6] introduces a unified model for dynamic group signatures and their security properties (i.e., full anonymity, anonymity, selfless anonymity, full traceability, traceability, and non-frameability). Our scheme DGS-VLR relies on the same definitions for anonymity, traceability and non-frameability. Additionally, Bootle et. al. show that the schemes proposed by Libert et al. [15], Libert et al. [23] and Nakanishi et al. [16] satisfy their new security models and are anonymous, traceable and non-frameable. The only significant difference between [15] and [23] is a drastic Table 1. COMPARISON OF GROUP SIGNATURE WHERE “-” MEANS NON-AVAILABLE, VLR = VERIFIER LOCAL REVOCATION, RL = REVOCATION LIST, FA=FULL ANONYMITY,SA=SELFLESS ANONYMITY,A=ANONYMITY,T=TRACEABLE,NF=NON-FRAMEABLE,U=UNFORGEABLE,FT = FULL TRACEABILITY. WE USE rAS THE NUMBER OF REVOKED USERS AND nTHE SIZE OF THE GROUP. Scheme Type Membership Join Revocation Security Signature Size Privacy Type Cost Bellare et. al. [4] Static No - - - fA, fT, NF - Bellare et. al. [5] partial Dynamic No private - - A, T, NF - Boneh et al. [12] Static No - VLR O(r)sA, T, U 2G1+ 5Zq Ishida et al. [14] Static No - VLR O(r)fA, T, U - Libert et al [15] (SD) partial Dynamic No public RL O(r)A, T, NF 180G1 Nakanishi et al [16] Dynamic No public RL O(r)A, T, NF 10G1+ 3G2+ 30Zq Bichsel et. al. [13] Dynamic No public VLR O(r)sA, T, NF 4G1+ 5Zq Backes et. al. [11] Static No - - - fA, fT, NF 20G1+ 5G2 Backes et. al. [7] Dynamic Yes private secret credential O(r·n)A, T, NF 28G1+ 15G2+ 512bits This Work w/ NIZK Dynamic Yes public VLR O(r)A, T, NF (4n+ 21)G1+ 19G2+ 512bits This Work w/ SPS-EQ Dynamic Yes public VLR O(r)A, T, NF 11G1+ 5G2+ 512bits reduction in the size of the public key. All three schemes [15], [23], [16] use revocation lists with [16] producing a smaller signature size compared to [15], [23]. An alternative approach to partial-dynamic group signatures is proposed by Bichsel et. al. [13] relies on rerandomisable signatures. They show their scheme is nonframeable, traceable, and selfless-anonymous. This has been extended by Backes et. al. [11] that used Signatures with Flexible Public Keys (FPK) to obtain static group signatures with smaller signature size while ensuring full-anonymity and full-traceability. Another extension by Backes et. al. [7] focused on introducing membership privacy for when users join/leave the group (cf. Table 1) and ensuring anonymity, traceability and non-frameability. However, revocation requires re-issuing credentials to all group users, for each member that is revoked, i.e. has complexity O(r·n). In this work, we achieve strong security properties: anonymity, traceability, non-frameability and membership privacy, whilst also supporting new more efficient revocation methods whose complexity is only linear in the number of revoked users, i.e. O(r). 2. Preliminaries In this section we define the relevant cryptographic building block that we used in our construction our DGS-VLR scheme: Asynchronous Remote Key Generation [20], Signatures with Flexible Public Keys [11], and Non-interactive Zero-Knowledge [24]. 2.1. Asynchronous Remote Key Generation An Asynchronous Remote Key Generation (ARKG) protocol [20] allows a party to create a public key on behalf of another, without exchanging any private information. The issuing party uses an existing long-term public key pk belonging to the receiver to derive a new public key pk′. In a one-round communication over a public channel the issuer sends some credentials cred, from which the reciever is able to derive a corresponding secret key sk′, using knowledge of their secret key sk. There are two security properties, pk-unlinkability that ensures that pk and pk′cannot be linked, and sk-security which ensures that only a party with knowledge of sk can derive a valid sk′. There are 4 flavours of this property that captures an adversary’s abilities: in this paper we make use of variant malicious strong key secrecy. ARKG has already seen uses in privacy-preserving delegatable cryptography by enabling proxy signatures with unlinkable warrants for use in the WebAuthn ecosystem [25], whilst the original work focused on discrete-log key pairs, there have been extensions to pairings [26] and even for lattices [27], [28], [29]. We introduce a variant of the ARKG scheme where pk and pk′are linked under specific conditions, i.e., using a secret token τgenerated as an additional output by the DerivePK algorithm. We introduce a new algorithm ChkLink to link two public keys and define a new security property, linking soundness, over this new algorithm. Definition 1 (Asynchronous Remote Key Generation [20]). An ARKG scheme is a tuple (Setup,KeyGen, DerivePK,DeriveSK,ChkKeys,ChkLink)defined as: pp ←$Setup(λ)takes as input the security parameter λ and outputs a set of public parameters pp. The public parameters are implicit input to all other algorithms (sk,pk)←$KeyGen() on input pp samples a private-public key pair (sk,pk). (pk′,cred, τ)←DerivePK(pk,aux)produces a new public key pk′, along with credentials cred and a link τ, from pk with some (potentially empty) auxiliary input aux. For simplicity, we abuse notation and use DerivePK(pk)when no aux is provided. sk′←DeriveSK(sk,cred)computes deterministically sk together with the information provided by cred to derive a new private key sk′corresponding to pk′. It may fail, in which case it outputs ⊥instead. {0,1} ← ChkKeys(sk′,pk′)checks whether the given pair (sk′,pk′)forms a valid private-public key pair, outputting 1if so and 0otherwise. {0,1} ← ChkLink(pk,pk′,cred, τ)decides whether the given link τproves that pk′and cred were derived from pk, outputting 1if so and 0otherwise. Correctness ensures with overwhelming probability a valid new key pair is generated and they can be linked using the token τ, if the protocol steps were followed. More precisely, 1−negl(λ)≤PrChkKeys(sk′,pk′)=1and 1−negl(λ)≤ PrChkLink(pk,pk′,cred, τ)=1given pp ←$Setup(λ) (sk,pk)←$KeyGen() (pk′,cred, τ)←DerivePK(pk) sk′←DeriveSK(sk,cred). The security properties pk-unlinkability and sk-security are adapted from the original work [20] (with considerations of the improved definitions of follow up works [29], [28]) to support the additional output τand algorithm ChkLink. We highlight that this does not change the intuition and goals, as the adversary does not have access to τin either experiment. Intuitively, for pk-unlinkability the adversary cannot distinguish between a fresh key generation process and a key derived using ARKG, while for sk-secrecy the adversary can’t compute the secret key matching the derived public key. The experiments are presented in the full version of this paper. We have the following advantages negligible in λfor an efficient adversary A: Advpku A,ARKG(λ) = PrhExppku A,ARKG = 1i−1 2and Advsks A,ARKG(λ) = PrhExpsks A,ARKG = 1i In accordance with the adapted syntax definition, we introduce an additional property, namely the soundness of a proof of linking. This captures the probability that a derived key pk′is created from pk with link τ, implies that the ChkLink algorithm succeeds. Definition 2 (Linking Soundness).ARKG satisfies linking soundness if for any PPT adversary Athe following advantage is negligible in λ: Advl-sound A,ARKG(λ) = Pr          pp ←$Setup(λ) (sk,pk)←$KeyGen() (pk′,cred, τ)← A(pk) b←ChkLink(pk,pk′,cred, τ) sk′←DeriveSK(sk,cred) b′←ChkKeys(sk′,pk′) return b∧ ¬b′          2.2. Signatures with Flexible Public Keys Signatures with Flexible Public Keys (SFPK) [11] are reminiscent of standard digital signatures but allow a signer to change their public key while still being able to sign. This is achieved by changing keys within an equivalence class, and importantly, signatures verify against all keys in the equivalence class. An initial key pair (sk,pk)may be generated with a trapdoor τthat can be used to check whether another key pk′lies in the same class denoted pk′∈[pk]. Definition 3 (Signatures with Flexible Public Keys [11]). An SFPK scheme is a tuple (Setup,KeyGen,TrapGen, ChgPK,ChgSK,Sign,Verify,ChkRep)consisting of the following algorithms. pp ←$Setup(λ)takes as input the security parameter λand outputs a set of public parameters pp. These are an implicit input for all other algorithms. (sk,pk)←$KeyGen() samples a private-public key pair. (pk′, τ)←TrapGen(pk)produces a public key pk′with trapdoor τ, associated with the equivalence class [pk]1. pk′←ChgPK(pk, r)returns an equivalent public key pk′∈[pk], for a public key pk and salt r. sk′←ChgSK(sk, r)takes a secret key sk and salt r, returning an updated secret key sk′. σ←Sign(sk, m)uses the key sk to produce a signature σ on the input message m. {0,1} ← Verify(pk, m, σ)outputs 1if (m, σ)forms a valid message-signature pair against pk and 0otherwise. {0,1} ← ChkRep(τ, pk)outputs 1if pk lies in the equivalence class associated with τ, and 0otherwise. Correctness of SFPK ensures the following properties hold 1) Algorithms KeyGen and TrapGen produce the same distribution over key-pairs. 2) With overwhelming probability the following two verification holds: 1←Verify(pk, m, Sign(sk, m)) and 1←Verify(pk′, m, Sign(sk′, m)), given valid key-pairs (sk,pk)←$KeyGen(λ)and pk′← ChgPK(pk, r); sk′←ChgSK(sk, r). 3) With overwhelming probability the algorithm ChkRep(τ, pk′)returns 1 iff pk′∈[pk]for any (pk′, τ)←$TrapGen(λ). The security of SFPK [11] is based on class-hiding and unforgeability. For class-hiding an adversary cannot distinguish between public keys generated from different equivalence classes, allowing the key-change function to “hide” the class containing the original key. The unforgeability of SFPK captures an adversary’s capability to create forgeries in the context of key-adaption. That is, the adversary needs to create a new public key pk∗∈[pk]and a forgery for that key. The formal experiments are presented in the full version of this paper. We have the following advantages negligible in λfor an efficient adversary A: Advch A,SFPK(λ) = PrhExpch A,SFPK = 1i−1 2and Advsuf-cma A,SFPK(λ) = PrhExpsuf-cma A,SFPK = 1i 2.3. Digital Signatures Digital signatures (DS) [21] are standard cryptographic primitives defined by three algorithms (KeyGen,Sign,Verify). They satisfy correctness where with overwhelming probability we have 1←Verify(pk, m, Sign(sk, m)) for (sk,pk)←$KeyGen(λ). Their security property ensures that they are resistant to existential forgeries under adversarially chosen messages. 1. This is a slight modification of [11] and we expand on this in Section 6. 2.4. Non-Interactive Zero-Knowledge Proofs For a given relation R, a language is defined as LR:= {x:∃w(x, w)∈R}. A zero-knowledge proof system allows a prover to prove knowledge of a witness wto the relation R, without leaking any information about it. Formally, it is defined below. Definition 4 (Non-Interactive Zero-Knowledge Proof System [24]).ANIZK proof system for a relation Ris a tuple of algorithms (Setup,Prove,Verify,SimSetup,Sim)defined as follows. ρ←$Setup(λ)takes as input the security parameter λand outputs a common reference string ρ. π←Prove(ρ, x, w)takes a common reference string ρ, statement xand witness w, returning a proof π. {0,1} ← Verify(ρ, x, π)outputs 1if πis a valid proof with respect to the common reference string ρand statement x, and 0otherwise. (ρ′, τ)←SimSetup(λ)takes as input the security parameter λand outputs a common reference string ρ′and a trapdoor τ. π′←Sim(ρ′, τ)takes a common reference string ρ′, statement xand returns a simulated proof π′. ANIZK proof system is correct if for any ρ←$Setup(λ) and (x, w)∈Rit follows that with overwhelming probability we have 1←Verify(ρ, x, Prove(ρ, x, w)). Soundness. ANIZK proof system is sound if the following advantage is negligible in the security parameter λ. Advsound A,NIZK(λ) = Pr   ρ←NIZK.Setup(λ) (x, π)←$A(ρ) return NIZK.Verify(ρ, x, π) ∧x /∈LR    Non-interactive Zero Knowledge. A NIZK proof system has the zero-knowledge property if the following advantage is negligible in the security parameter λ. The advantage Advzk A,NIZK(λ)is defined as:  Prρ←NIZK.Setup(λ); return ANIZK.Prove(ρ,·,·)(ρ) −Prh(ρ′, τ)←SimSetup(λ); return ASim(ρ′,τ,·)(ρ′)i 3. Syntax & Security Properties for DGS-VLR In this section we give the syntax and properties of Dynamic Group Signatures with Verifier-Local Revocation. It is modeled based on the definition of Fully Dynamic Group Signatures [6] but with the requirement that the joining phase can be carried out on a public channel. Furthermore, the model [6] separates out the group manager and tracing authorities; however we consider the case that both aspects are managed by the group manager, a consequence of implementing verifier-local revocation. We adopt standard security properties, namely anonymity, traceability, non-frameability (inspired by [6]), and Membership Privacy (inspired by [7]), with minor adaptations to account for the new functionality of the group manager to revoke users from the scheme. Definition 5 (Dynamic Group Signatures with Verifier Local Revocation). A Dynamic Group Signature with Verifier Local Revocation DGS-VLR consists of the following algorithms: pp ←$Setup(λ)takes as input the security parameter λ and outputs a set of public parameters pp. As part of the public parameters we also initialise an empty data structure REG that maps user identities with their long term public keys. The parameter pp is an implicit input to every other algorithm. (gpk,gmsk,info)←$GKeyGen() generates a group public key gpk and a group manager secret key gmsk. It also initializes the public group information info. (uskid,upkid)←RegUser(id),executed by the user, it samples a private-public key pair (uskid,upkid)given the user identity id. The registry REG is updated only if nothing is previously stored for this used, e.g., if REG[id] = ⊥then REG[id]←upkid. (gmsk,info)←AddUser(gmsk,info, id)executed by the group manager, this algorithm adds a registered user id to the group, and updates the group manager secret key gmsk and public group information info. info ←Revoke(gmsk,info, id)revokes a group member id, updating the public group information info accordingly. Σ←Sign(info,uskid, m)run by user id, it uses the public group information info, the user’s secret key uskid and a message mto produce a signature Σon m. {0,1} ← Verify(gpk,info, m, Σ) checks whether (m, Σ) forms a valid message-signature pair against the group public key and information (gpk,info)and a list of revocation tokens RL. For ease, we include RL in info. It outputs a bit b∈ {0,1}with 1indicating acceptance and 0rejection. (id, π)←Open(gpk,gmsk,info, m, Σ) outputs the identity id of a user along with a proof πtracing the signature (m, Σ) to this user. In the case that Open fails to trace, it outputs (⊥,⊥). {0,1} ← Judge(gpk,info, id, π, m, σ)uses the group public key and information gpk,info to validate a proof of authorship πfor some message-signature pair (m, σ) attributing it to a user id. It outputs a bit b∈ {0,1} with 1indicating acceptance and 0rejection. Remark 1. The separation of the join/issue protocol into the RegUser and AddUser algorithms allows the possibility for the same user to be added to the group multiple times under a single registry. In particular this behaviour is useful for reinstating a revoked user without having to allocate them a new id, i.e. temporary revocation. Alternatively, enforcing AddUser to ignore existing or revoked group members recovers existing models [6], [7]. 3.1. Correctness and Security Properties We now state the formal definitions of correctness and the security properties. Notation. The experiments make use of the following additional lists. •HU: A list of honest registered users, populated by the registration oracle HonestU. For any id ∈HU we have a stored public key REG[id]=⊥. The adversary can additionally create users outside of this (id′/∈HU) and populate REG[id′]directly with some public key. •BU: A list of corrupt users, whose keys have been compromised by the adversary calling RevealU. We have that for any id ∈BU implies id ∈HU. •AM: A list of active group members who are able to sign successfully. An active group member becomes inactive if revoked by RevokeU. Note id ∈AM implies REG[id]=⊥, but does not imply id ∈HU. •Qsig: list of queries (id, m)made as input to SignU. •OBL: A list of message-signature pairs that the adversary has been challenged on. The adversary is prohibited from running the Open algorithm (via the oracle OpenSig) to identify the user that issued that signature. •Chl ={id0, id1}: Stores a pair of challenge users chosen by the adversary in the anonymity, join, and leave experiments. Oracles. We introduce the following oracles that are used in the security experiments. •upkid ←HonestU(id)simulates RegUser(id)to create a private-public key pair (uskid,upkid), and updates HU ←HU ∪ {id}. Note that the registry is also updated REG[id]←upkid. •uskid ←RevealU(id)returns the signing key of an user with the given an identity that is not part of the challenge id ∈HU \Chl. We also update BU ← BU ∪ {id}. Note all id ∈BU implies id ∈HU. •CorruptU(id, pk)updates REG[id]←pk only if REG[id] = ⊥. This simulates the registration of a public key of a corrupted user (i.e, under the control of the adversary). Note REG[id] = ⊥implies id /∈ HU, but REG[id]=⊥does not imply id ∈HU. •info ←IssueU(id)simulates AddUser on the identity id, making them an active group member. This adds a new entry to info associated with the corresponding user even if they were already an active member. The list of active group members is updated AM ←AM ∪ {id}. •info ←ActivateU(id)simulates AddUser only for id /∈AM. Otherwise, it returns previously stored info. The list of active group members is updated AM ←AM ∪ {id}as for IssueU. •info ←RevokeU(id)simulates Revoke to revoke user id from the group, and updates AM ←AM \ {id}. The user can later be added back to the group by using IssueU(id)or ActivateU(id). •σ←SignU(info, id, m)simulates Sign with uskid and returns the signature σfor any id ∈HU \Chl. We also update Qsig ←Qsig ∪ {(id, m)}. •id ←OpenSig(m, σ)simulates Open and returns the identity id without a proof, except if (m, σ)is in the opening ban list OBL. •σ←Challb,anon(info, m)runs Sign with uskidb for the challenge bit b∈ {0,1}and challenge user identities Chl ={id0, id1}. It returns the signature σonly if both users have been honestly generated and are active members Chl ⊆HU and Chl ⊆AM; otherwise it returns ⊥. Notice that for the anonymity experiment the adversary can corrupt the usersand have access to their signing keys, e.g., Chl ⊆BU. The opening ban list is updated OBL ←OBL ∪ {(m, σ)}. •σ←Challb,join(info, m)simulates Sign with uskidbfor the challenge bit b∈ {0,1}and challenge user identities Chl ={id0, id1}. Returns the signature σonly if both users haven’t been corrupted Chl ⊆HU and Chl ∩BU =∅. The following list is updated OBL ←OBL ∪ {(m, σ)}. •Challb,leave(info, m)simulates Sign with uskidbfor the challenge bit b∈ {0,1}and challenge user identities Chl ={id0, id1}. Returns the signature σ, unless either user is corrupt or has been used to query the signing oracle. Correctness. This ensures that if the protocol steps are followed, for any message m, with overwhelming probability we have: 1) A valid group signature is created by a user if and only if they are an active group member, and 2) An honest judge will accept the proof regarding the identity of the signer, given an opening of a valid signature. Formally, using the experiment in Figure 1we have 1−negl(λ)≤PrExpcorr A,DGS-VLR = 1. Anonymity. A DGS-VLR scheme is anonymous if an adversary cannot determine the identity of a user idb∈ {id0, id1} given polynomially many challenge message-signature pairs (m, Σ) under the signing key uskidb. This is the case even if the adversary has access to all group members’ signing keys and an opening oracle (restricted on the challenge pairs). Definition 6 (Anonymity).A dynamic group signature with verifier local revocation scheme is anonymous if the following advantage is negligible in λ, where Expanon A,DGS-VLR is defined in Figure 1. Advanon A,DGS-VLR(λ) = PrExpanon A,DGS-VLR = 1−1 2 Remark 2. Our anonymity experiment uses two challenges oracles to capture the notion of swapping the order in which the identities id0and id1are input to the challenge oracle (so the oracle effectively signs for 1−binstead of b). While the experiment is typically defined using a single oracle with malleable input for challenge identities in the literature (e.g. [6], [7]), using distinct oracles leads to both an equivalent security definition and a more direct proof argument for our construction. Traceability. A dynamic group signature scheme is traceable if an adversary cannot create a valid message-signature Expcorr A,DGS-VLR(1λ) 1:pp ←$Setup(1λ) 2: (gpk,gmsk,info)←$GKeyGen(pp) 3:HU, AM ← ∅ 4: (m, id)←$A(pp,gpk,gmsk,info)O1 5:if id /∈HU ∨id =⊥then return 1 6: Σ ←Sign(info,uskid, m) 7:b1←Verify(gpk,info, m, Σ) 8:if id /∈AM then return ¬b1 9: (id′, τ)←Open(gpk,gmsk,info, m, Σ) 10 :b2←Judge(gpk,info, id, τ, m, Σ) 11 :return b1∧b2∧(id =id′) Expanon A,DGS-VLR(1λ)with A= (A0,A1) 1:pp ←$Setup(1λ) 2: (gpk,gmsk,info)←$GKeyGen(pp) 3:HU, BU, AM, Qsig, OBL, Chl ← ∅ 4: (st, id0, id1)←$A0(pp,REG,gpk,info)O3,O4 5:Chl ← {id0, id1} 6:b←${0,1} 7:b′←$A1(st)O3,O4,O5 8:return b′=b Expjoin A,DGS-VLR(1λ)with A= (A0,A1) 1:pp ←$Setup(1λ) 2: (gpk,gmsk,info)←$GKeyGen(pp) 3:HU, BU, AM, Qsig, OBL, Chl ← ∅ 4: (st, id0, id1)← A0(pp,gpk,info)O3,O4 5:Chl ← {id0, id1};b←${0,1} 6:if Chl ⊂HU \BU then 7: (gmsk,info)←AddUser(gmsk,info, idb) 8:b′← A1(st)O3,O4,Challb,join 9:return b′=b Expframe A,DGS-VLR(1λ)with A= (A0,A1) 1:pp ←$Setup(1λ) 2: (st,gpk,gmsk,info)← A0(pp) 3:if gpk =⊥ ∨ gmsk =⊥ ∨ info =⊥ 4:then return 0 5:HU, BU, Qsig ← ∅ 6: (info, m, Σ, id, τ)← A1(st)O2 7:b←0 8:if id ∈HU \BU ∧(id, m)/∈Qsig 9:∧Verify(gpk,info, m, Σ) then 10 :b←Judge(gpk,info, id, τ, m, Σ) 11 :return b Exptrace A,DGS-VLR(1λ) 1:pp ←$Setup(1λ) 2: (gpk,gmsk,info)←$GKeyGen(pp) 3: (info′, m, Σ) ←$A(pp,gpk,info)O3,O4 4:b←0 5:if Verify(gpk,info′, m, Σ) then 6: (id, τ)←Open(gpk,gmsk,info, m, Σ) 7:b← ¬Judge(gpk,info, id, τ, m, Σ) 8:return b Expleave A,DGS-VLR(1λ)with A= (A0,A1) 1:pp ←$Setup(1λ) 2: (gpk,gmsk,info)←$GKeyGen(pp) 3:HU, BU, AM, Qsig, OBL, Chl ← ∅ 4: (st, id0, id1)← A0(pp,gpk,info)O3 5:Chl ← {id0, id1};b←${0,1} 6:if Chl ⊂ AM then Chl ←(⊥,⊥) 7:if ∀id ∈Chl. id ∈HU \BU ∧(id, ·)/∈Qsig 8:then info ←Revoke(gmsk,info, idb) 9:b′← A1(st)O3,O4,Chall1−b,leave 10 :return b′=b Figure 1. Group signature security games with oracles O1 = {HonestU, IssueU, RevokeU},O2 = {HonestU, CorruptU, RevealU, SignU}, O3 = {HonestU, CorruptU, RevealU, ActivateU, RevokeU, SignU, OpenSig},O4 = {IssueU}, and O5 = {Challb,anon, Chall1−b,anon}. pair (m, Σ) that does not open to a valid identity id and proof πfor an existing group member. Note that our definition slightly departs from existing work (e.g. [6], [7]) as we do not separate the role of tracing authority and group manager. Definition 7 (Traceability).A dynamic group signature scheme is traceable if the following advantage is negligible in λ, where Exptrace A,DGS-VLR is defined in Figure 1. Advtrace A,DGS-VLR(λ) = PrExptrace A,DGS-VLR = 1 Non-Frameability. A dynamic group signature scheme is non-frameable if an adversary cannot create a valid messagesignature pair (m, Σ) that opens to an identity id of an honest user for which the adversary does not know the user secret key, even if the adversary can corrupt the group manager. Definition 8 (Non-Frameability).A dynamic group signature scheme is non-frameable if the following advantage is negligible in λ, where Expframe A,DGS-VLR is defined in Figure 1. Advframe A,DGS-VLR(λ) = PrhExpframe A,DGS-VLR = 1i Membership Privacy. Introduced by Backes et al. [7], membership privacy captures strong privacy properties for dynamic group signatures. Intuitively, it ensures privacy as groups members are added and revoked. We adopt these notions for our scheme, and say a DGS-VLR provides membership privacy if it provides both join and leave privacy. •The scheme provides join privacy if an adversary cannot distinguish which of two chosen honest users id0, id1has been issued (regardless of whether each user is already active). •The scheme provides leave privacy if an adversary cannot distinguish which of two chosen active honest users id0, id1has been revoked. In both games the adversary cannot request signatures on either user after the challenge is given, instead they may receive signatures anonymously via a challenge oracle for the activated user idbin the join game and the non-revoked user id1−bin the leave game. In particular, the adversary cannot use the opening oracle on these signatures. Definition 9 (Join Privacy).A dynamic group signature with VLR provides join-privacy if the following advantage is negligible in λ, where Expjoin A,DGS-VLR is defined in Figure 1. Advjoin A,DGS-VLR(λ) = PrhExpjoin A,DGS-VLR = 1i−1 2 Definition 10 (Leave Privacy).A dynamic group signature with VLR provides leave-privacy if the following advantage is negligible in λ, for Expleave A,DGS-VLR defined in Figure 1. Advleave A,DGS-VLR(λ) = PrhExpleave A,DGS-VLR = 1i−1 2 Remark 3. The consequences of our modeling choices as discussed in Remark 1must be carefully considered for the membership privacy experiments. For the join game, no problems arise as the change in info is the same regardless of whether idbhas been issued previously before the challenge is declared. However, for the leave game when the challenge is declared and idbis revoked, all group information linked to idbis impacted simultaneously. The adversary may link the amount of affected information to the number of times idbwas issued before the challenge was declared. Thus the experiment must limit each identity to only one issuing in the first phase. This purpose is fulfilled by the ActivateU oracle, while the IssueU oracle is prohibited for A0in the leave game. Furthermore, the leave game requires that both challenge users are active members, however since one of them is revoked before the guess phase, the Challb,leave oracle will not be able to check this condition directly. This is addressed by setting both challenge users to (⊥,⊥)if the check fails before revocation. Then, the oracle will reject considering these users dishonest. 4. Generic Construction of DGS-VLR In this section we detail our construction for DGS-VLR, and illustrate all our algorithms in Figure 2. The group manager executes Setup to generate the public parameters by running the setup algorithms for an asynchronous remote key generation ARKG and a signature with flexible public keys SFPK. It instantiates a group by creating keys for a digital signature DS, as well as initialising both a list of group members pkl and a revocation list RL as empty. These are output as a group information info. The process for building the group can be summerised by the following six steps. •Users register to be considered for the group. •Group manager selects group members from the list of users in the registry. •Group manager creates group signing keys for each group member via ARKG’s DerivePK algorithm. •Users identify their group signing keys using the group information (i.e. via public channels). •Users re-randomise their obtained signing key and use it to create a signature via SFPK. •Group manager may revoke a user by publishing a SFPK trapdoor that identifies all possible randomisations of their signing key. A user id registers by first generating an ARKG key pair (usk,upk)and declaring ownership of the public key upk via the registry REG[id]←upk. The user is added to the group by the group manager by executing the AddUser algorithm. This algorithm runs our modified ARKG.DerivePK algorithm on upk to create a new user key pk (and corresponding derivation information cred,τcred). The pk-unlinkability property of ARKG ensures that these two keys cannot be linked, even with knowledge of cred. The keys can however be linked with knowledge of τcred, which is stored by the group manager so that they may later open signatures to id. Furthermore, the algorithm creates an additional token τpk by executing SFPK.TrapGen. This is stored by the group manager to enable linking in the case that the user is later revoked, by running the revoke algorithm, which appends τpk to the revoke list RL. This is published, and is authenticated with a digital signature σinfo, over pkl and RL, which verifies against the group managers key gpk. To create a group signature, a user runs the Sign algorithm, which takes as input the group information info, its long-term user key usk and the message m. It begins by parsing pkl and identifying which pk,cred correspond to its key usk. It does this by checking the MACs stored in cred. Once found, it runs ARKG.DeriveSK to derive sk that corresponds to the derived public key pk. It is important to notice that the derived key space to which pk belongs is carefully chosen to coincide with the key space for the SFPK scheme, thus it can randomise this key using SFPK.ChgPK, to create a key pk′along with a corresponding key sk′using SFPK.ChgSK. The message mis signed with SFPK.Sign using the key sk′. The class-hiding property of SFPK ensures that the randomised key pk′cannot be linked to pk without knowledge of τpk, and since the keys are randomised for every new signature, it implies that signatures also cannot be linked. Finally, the user creates a zero-knowledge proof Πthat the key pk′indeed is the randomisation of a valid key, i.e. a pk that is in pkl. More precisely, the relation for Setup(λ) 1:gp ←ARKG.Setup(λ) 2:crs ←SFPK.CRSGen(gp) 3:REG ← ∅ 4:pp ← {gp, crs, REG} 5:return (pp) GKeyGen() 1: (gpk, ik)←DS.KeyGen(pp) 2:pkl, RL, okl ← ∅ 3:gmsk ←(ik, okl) 4:info ←(pkl, RL,⊥) 5:return (gpk,gmsk,info) RegUser(id) 1:upk,usk ← ⊥ 2:if REG[id] = ⊥then 3: (upk,usk)←$ARKG.KeyGen(pp) 4:REG[id]←upk 5:return (upk,usk) Verify(gpk, info, m, Σ) 1:parse info = (pkl, RL, σinfo) 2:parse Σ = (σ, pk′,Π) 3:for τpk ∈RL do 4:if SFPK.ChkRep(τpk,pk′)then 5:return 0 6:M:= m||pk′ 7:return SFPK.Verify(pk′, M, σ) 8:∧DS.Verify(gpk,(pkl, RL), σinfo) 9:∧NIZK.Verify((pk′, pkl),Π) AddUser(gmsk,info, id) 1:parse info = (pkl, RL, σinfo) 2:parse gmsk = (ik, okl) 3:upk ←REG[id] 4: ( ˆ pk,cred, τcred)←$ARKG.DerivePK(upk) 5: (pk, τpk)←$SFPK.TrapGen(ˆ pk) 6:pkl ←pkl ∪ {(pk,ˆ pk,cred)} 7:okl ←okl ∪ {(id, τpk, τcred)} 8:σinfo ←DS.Sign(ik, (pkl, RL)) 9:info ←(pkl, RL, σinfo) 10 :gmsk ←(ik, okl) 11 :return (gmsk,info) Sign(info,usk, m) 1:parse info = (pkl, RL, σinfo) 2:pk,sk ← ⊥ 3:if DS.Verify(gpk,(pkl, RL), σinfo)then 4:for (ˆ pk,cred)∈pkl do 5:sk ←ARKG.DeriveSK(usk,cred) 6:for τpk ∈RL do 7:if SFPK.ChkRep(τpk,ˆ pk)then 8:sk ← ⊥ 9:if sk =⊥then pk ←ˆ pk break 10 :if sk =⊥then return (⊥,⊥,⊥) 11 :r←$Z∗ p;pk′←SFPK.ChgPK(pk, r) 12 :sk′←SFPK.ChgSK(sk, r) 13 : Π ←NIZK.Prove((pk′, pkl),pk) 14 :M:= m||pk′;σ←SFPK.Sign(sk′, M) 15 :return Σ = (σ, pk′,Π) Revoke(gmsk,info, id) 1:parse info = (pkl, RL, σinfo) 2:parse gmsk = (ik, okl) 3:for (id′, τpk,·)∈okl do 4:if id =id′then RL ←RL ∪ {τpk} 5:σinfo ←DS.Sign(ik, (pkl, RL)) 6:info ←(pkl, RL, σinfo) 7:return info Open(gmsk,gpk,info, m, Σ) 1:parse gmsk = (ik, okl) 2:parse Σ = (σ, pk′,Π) 3:if Verify(gpk,info, m, Σ) then 4:for (id, τpk, τcred)∈okl do 5:if SFPK.ChkRep(τpk,pk′)then 6:return (id, (τpk, τcred)) 7:return (⊥,⊥) Judge(gpk,info, id, τ, m, Σ) 1:parse τ= (τpk, τcred) 2:parse Σ = (σ, pk′,Π) 3:if ¬Verify(gpk,info, m, Σ) 4:then return 0 5:upk ←REG[id] 6:for (pk,ˆ pk,cred)∈pkl do 7:ainp ←(upk,ˆ pk,cred, τcred) 8:b1←ARKG.ChkLink(ainp) 9:b2←SFPK.ChkRep(τpk,pk) 10 :b3←SFPK.ChkRep(τpk,pk′) 11 :if (b1∧b2∧b3)then 12 :return 1 13 :return 0 Figure 2. All algorithms for the group signature DGS-VLR. the proof Πis given by: R:=(pk′, pkl),(pk); ∃r s.t. ChgPK(pk, r) = pk′ ∧pk ∈pkl} The group signature Σis a tuple consisting of the SFPK signature σ, the verification key pk′and the proof Π. Verification is a public process which takes as input a candidate signature Σ, a message mand group information info. The verifier parses revocation tokens τpk from the revocation list RL, and for each one, runs SFPK.ChkRep against the verification key pk′that comprises part of Σ. If the algorithm returns 1, then a users trapdoor has been added to RL and is thus revoked, and verification fails. Else, the SFPK signature σis verified against pk′on m, and the validity of the proof Πis verified. If all stages are successful, then the algorithm outputs 1, else it returns 0. To trace a signature, the group manager runs the Open algorithm by checking for which SFPK trapdoor τpk matches the verification key pk′. It then outputs the corresponding identity id. This step can be publicly checked in the Judge algorithm, by verifying a signature, and then checking that the group manager’s provided τcred links a user’s longterm key upk to some intermediate key pk in info. Then it checks that the SFPK trapdoor τpk is a valid trapdoor for pk by running SFPK.ChkRep, and finally checks that the ephemeral verification key pk′belongs to the same equivalence class by once more running SFPK.ChkRep. As observed in Remark 1, it is possible to issue multiple public keys to the same group member, while each token τpk only revokes the individual key class [pk]. This provides the ability to reinstate a previously revoked user by issuing them a new public key. 5. Security Analysis In this section we prove that our construction of DGSVLR (Figure 2), is correct and satisfies Anonymity, Trace- CRSGen(pp) 1:parse pp = (gp, fp) 2:and gp = (G1,G2, g1, g2, q) 3:y, z ←$Z∗ q 4:h←gz 1 5:Y←(gy 1, gy 2, h) 6:return Y TrapGen(X) 1:parse X= (X1, X2) 2:a, b ←$Z∗ q 3: (A, B)←(ga 1, gb 1) 4:pk ←(X1, A, B) 5:τ←(X2, a, b) 6:return (pk, τ) ChkRep(τ, pk) 1:parse pk = (pk1,pk2,pk3) 2:parse τ= (τ1, a, b) 3:τ2←ga 2;τ3←gb 2 4:return 5: 3 ^ i=1 3 ^ j=1 e(pki, τj)? =e(pkj, τi) Sign(Y, sk =x, pk, m) 1:parse Y= (Y1, Y2, h) 2:r, u ←$Z∗ q 3:v←H(m|gr 1|gr 2|pk) 4:M←gv 1·hu 5:R←Yx 1·(H(M))r 6:σ←(R, gr 1, gr 2, u) 7:return σ Verify(Y, pk, m, σ) 1:parse Y= (Y1, Y2, h) 2:parse pk = (X1, A, B) 3:parse σ= (σ1, σ2, σ3, u) 4:v←H(m|σ2|σ3|pk) 5:M←gv 1·hu 6:return e(σ2, g2) = e(g1, σ3)∧ 7:e(σ1, g2) = e(X1, Y2)·e(H(M), σ3) ChgPK(pk, r) 1:parse pk = (X1, A, B) 2:pk′←(Xr 1, Ar, Br) 3:return pk′ ChgSK(sk =x, r) 1:sk′←x·r 2:return sk′ Figure 4. SFPK algorithms adapted for pre-generated key pairs (sk,pk)=(x, X), where His a collision-resistant hash function with image G1. Table 2. COMPARISON AGAINST EXISTING DYNAMIC GROUP SIGNATURES. WE USE pk TO DENOTE THE USE OF THE USER PUBLIC KEY,usk FOR THEIR SECRET KEY,ΣFOR THE SIZE OF THE SIGNATURE AND RL FOR THE REVOCATION LIST,WHERE rIS THE NUMBER OF ENTRIES IN THE LIST.REVOKE SHOWS ASYMPTOTIC RUNTIME FOR REVOKING rOUT OF nGROUP MEMBERS.ZKPROOF SIZE1COMPUTED USING [24]. Scheme pk usk ΣRL Revoke Backes et al. [7]2G13G128G1+ 15G2+ 512bits N/A O(n) DGS-VLR w/ NIZK 3G11Z∗ q(4n+ 21)G1+ 19G2+ 512bits r(1G2+ 2Z∗ q)O(1) DGS-VLR w/ SPS-EQ 3G11Z∗ q11G1+ 5G2+ 512bits r(1G2+ 2Z∗ q)O(1) Compared to Backes et al. [7], we achieve the smaller signature size despite use of the same underlying use of the SFPK scheme. This is due to the fact that our VLR approach means we can reduce the complexity of the relation for the proof that comprises part of the signature. However, our main advantage comes from the fact we have dropped the notion of epochs to manage revocation and joining within the scheme. In particular, to process a group update, our scheme publishes the group information info which has size 512(n+1)bits+3nG1+(3n+r)G2+2rZ∗ q, where nis the number of group members and ris the number of revoked users. As mentioned previously, this update is the same for all users and can be published globally. This compares to Backes et al. where each group member needs to regenerate its signing key, where user-specific computation consists of generating ciphertexts which dominate this phase. The size of the update is 10G1+ 14G2+ 512bits2+ 2G3per group member. Additionally, to perform revocation (i.e., calling Revoke) is more efficient for VLR schemes O(1) compared to schemes on secret credentials O(n)for ngroup members. 2. The original paper does not specify which digital signature the authors instantiate their scheme with, so we use ECDSA for fair comparison. 3. This term is derived from the author’s use of the ElGamel encryption scheme, for which the underlying group can be independently chosen of G1and G2, so we do not specify further. 7. Conclusion In this paper we have proposed a Dynamic Group Signature scheme with a Verifier-Local Revocation – the first dynamic group signature scheme with membership privacy to benefit from the efficiency improvements for using a VLR approach. We were able to achieve this by adapting Asynchronous Remote Key Generation to also support a linking trapdoor, for which we defined a new security property Linking Soundness. When combined with a trapdoor from Signatures with Flexible Public Keys to form an extended two-stage tracing process, this allowed the latter trapdoor to serve as the revocation token in our generic construction without compromising membership privacy. We have instantiated our generic scheme with pairing-based building blocks to give a DGS-VLR that is competitive with the state-of-the-art from an efficiency point of view, but with improved functionality. By adopting a VLR approach, our scheme avoids reissuing keys during group updates and thus enables more efficient joining and leaving. Finally, when instantiated with SPS-EQ our signatures each consist of 11G1+ 5G2+ 512bits, which is smaller than all other dynamic schemes to date (cf. Table 2). Future Work. Whilst we have demonstrated favourable asymptotic performance, a concrete implementation would provide better metrics for real world use. Furthermore, postquantum security guarantees would be an additional highly desirable property. This could be achieved through a lattice- based implementation; in fact, lattice-based constructions have already been proposed for ARKG [27], [28], [29]. However, these implementations do not support the necessary trapdoor for Linking Soundness. Additionally, SPS-EQ from lattices is also an open problem, both of which would be required to extend our results to achieve PQ security. Acknowledgments C. C. Dr˘ agan is partially supported by TrustVote – EPSRC grant EP/Y020529/1, AP4L - EPSRC grant EP/W032473/1, CONNECT - Horizon Europe Guarantee 10043730 and EU Horizon grants 101069688, REWIRE - Horizon Europe Guarantee 10043743 and EU Horizon grants 101070627. References [1] D. Chaum and E. van Heyst, “Group Signatures,” in Proceedings of EUROCRYPT 1991, vol. 547 of LNCS, pp. 257–265, Springer, 1991. [2] A. Lysyanskaya and Z. Ramzan, “Group blind digital signatures: A scalable solution to electronic cash,” in Financial Cryptography, Second International Conference, FC’98, Anguilla, British West Indies, February 23-25, 1998, Proceedings, vol. 1465 of LNCS, pp. 184–197, Springer, 1998. [3] S. Canard and J. Traoré, “On fair e-cash systems based on group signature schemes,” in Information Security and Privacy, 8th Australasian Conference, ACISP 2003, Wollongong, Australia, July 9-11, 2003, Proceedings, vol. 2727 of LNCS, pp. 237–248, Springer, 2003. [4] M. Bellare, D. Micciancio, and B. Warinschi, “Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions,” in Proceedings of EUROCRYPT 2003, vol. 2656 of LNCS, pp. 614–629, Springer, 2003. [5] M. Bellare, H. Shi, and C. Zhang, “Foundations of Group Signatures: The Case of Dynamic Groups,” in Proceedings of CT-RSA 2005, vol. 3376 of LNCS, pp. 136–153, Springer, 2005. [6] J. Bootle, A. Cerulli, P. Chaidos, E. Ghadafi, and J. Groth, “Foundations of Fully Dynamic Group Signatures,” in Proceedings of ACNS 2016, vol. 9696 of LNCS, pp. 117–136, Springer, 2016. [7] M. Backes, L. Hanzlik, and J. Schneider-Bensch, “Membership Privacy for Fully Dynamic Group Signatures,” in Proceedings of the CCS 2019, pp. 2181–2198, ACM, 2019. [8] “Docusign group signing.” https://support.docusign.com/ s/document-item?language=en_US&rsc_301&bundleId= gav1643676262430&topicId=zgn1578456447934.html. Accessed on 17th April 2025. [9] B. Brecht, D. Therriault, A. Weimerskirch, W. Whyte, V. Kumar, T. Hehn, and R. Goudy, “A security credential management system for v2x communications,” IEEE Transactions on Intelligent Transportation Systems, vol. PP, 02 2018. [10] J. Petit, F. Schaub, M. Feiri, and F. Kargl, “Pseudonym schemes in vehicular networks: A survey,” Commun. Surveys Tuts., vol. 17, p. 228–255, Jan. 2015. [11] M. Backes, L. Hanzlik, K. Kluczniak, and J. Schneider, “Signatures with Flexible Public Key: Introducing Equivalence Classes for Public Keys,” in Proceedings of Part II of ASIACRYPT 2018, vol. 11273 of LNCS, pp. 405–434, Springer, 2018. [12] D. Boneh and H. Shacham, “Group signatures with verifier-local revocation,” in Proceedings of CCS 2004, pp. 168–177, ACM, 2004. [13] P. Bichsel, J. Camenisch, G. Neven, N. P. Smart, and B. Warinschi, “Get Shorty via Group Signatures without Encryption,” in Proceedings of SCN 2010, vol. 6280 of LNCS, pp. 381–398, Springer, 2010. [14] A. Ishida, Y. Sakai, K. Emura, G. Hanaoka, and K. Tanaka, “Fully Anonymous Group Signature with Verifier-Local Revocation,” in Proceedings of SCN 2018, vol. 11035 of LNCS, pp. 23–42, Springer, 2018. [15] B. Libert, T. Peters, and M. Yung, “Scalable group signatures with revocation,” in Proceedings of EUROCRYPT 2012, vol. 7237 of LNCS, pp. 609–627, Springer, 2012. [16] T. Nakanishi, H. Fujii, Y. Hira, and N. Funabiki, “Revocable Group Signature Schemes with Constant Costs for Signing and Verifying,” in Proceedings of PKC 2009, vol. 5443 of LNCS, pp. 463–480, Springer, 2009. [17] V. Kumar, H. Li, N. Luther, P. Asokan, J.-M. J. Park, K. Bian, M. B. H. Weiss, and T. Znati, “Direct anonymous attestation with efficient verifier-local revocation for subscription system,” in Proceedings of the 2018 on Asia Conference on Computer and Communications Security, ASIACCS ’18, p. 567–574, Association for Computing Machinery, 2018. [18] Y. NAKAZAWA and T. NAKANISHI, “A strongly unlinkable group signature scheme with matching-based verifier-local revocation for privacy-enhancing crowdsensing,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E106.A, no. 12, pp. 1531–1543, 2023. [19] K. Banti, F. Katsimpoura, M. Louta, and G. T. Karetsos, “Data quality in mobile crowd sensing systems: Challenges and perspectives,” in 2018 9th International Conference on Information, Intelligence, Systems and Applications (IISA), pp. 1–8, 2018. [20] N. Frymann, D. Gardham, F. Kiefer, E. Lundberg, M. Manulis, and D. Nilsson, “Asynchronous Remote Key Generation: An Analysis of Yubico’s Proposal for W3C WebAuthn,” in Proceedings of CCS 2020, pp. 939–954, ACM, 2020. [21] J. Katz, Digital Signatures. Springer, 2010. [22] G. Fuchsbauer and R. Gay, “Weakly secure equivalence-class signatures from standard assumptions,” in Public-Key Cryptography – PKC 2018, pp. 153–183, Springer International Publishing, 2018. [23] B. Libert, T. Peters, and M. Yung, “Group Signatures with Almostfor-Free Revocation,” in Proceedings of CRYPTO 2012, vol. 7417 of LNCS, pp. 571–589, Springer, 2012. [24] C. Ràfols, “Stretching groth-sahai: Nizk proofs of partial satisfiability,” in Theory of Cryptography, pp. 247–276, Springer Berlin Heidelberg, 2015. [25] N. Frymann, D. Gardham, and M. Manulis, “Unlinkable Delegation of WebAuthn Credentials,” in Proceedings of PART III of ESORICS 2022, vol. 13556 of LNCS, pp. 125–144, Springer, 2022. [26] N. Frymann, D. Gardham, M. Manulis, and H. Nartz, “Generalised Asynchronous Remote Key Generation for Pairing-Based Cryptosystems,” in Proceedings of Part I of ACNS 2023, vol. 13905 of LNCS, pp. 394–421, Springer, 2023. [27] N. Frymann, D. Gardham, and M. Manulis, “Asynchronous Remote Key Generation for Post-Quantum Cryptosystems from Lattices,” in Proceedings of IEEE EuroS&P 2023, pp. 928–941, IEEE, 2023. [28] D. Stebila and S. Wilson, “Quantum-safe account recovery for webauthn,” in Proceedings of the 19th ACM Asia Conference on Computer and Communications Security, ASIA CCS 2024, Singapore, July 1-5, 2024, ACM, 2024. [29] J. Brendel, S. Clermont, and M. Fischlin, “Post-quantum asynchronous remote key generation for fido2,” in ASIACRYPT 2024, Springer-Verlag, 2024. [30] D. Johnson, A. Menezes, and S. A. Vanstone, “The Elliptic Curve Digital Signature Algorithm (ECDSA),” Int. J. Inf. Sec., vol. 1, no. 1, pp. 36–63, 2001. [31] National Institute of Standards and Technology (NIST), “SHA-3 standard: Permutation-based hash and extendable-output functions,” 2015. [32] H. Krawczyk, M. Bellare, and R. Canetti, “Rfc2104: Hmac: Keyedhashing for message authentication,” 1997. [33] J. Groth and A. Sahai, “Efficient non-interactive proof systems for bilinear groups,” in Advances in Cryptology – EUROCRYPT 2008, pp. 415–432, Springer Berlin Heidelberg, 2008. Appendix A. Building Blocks Here we recall additional building blocks and their security properties. The security experiments for SFPK are given in Figure 5. Note that the inclusion of σ∗in line 5of the euf-cma experiment transforms it into the suf-cma (strong euf-cma) experiment. The security experiments for ARKG are given in Figure 6. The presented definitions have been modified to capture the trapdoor τas an additional output from algorithm DerivePK. Expch A,SFPK(1λ) 1:pp ←$Setup(λ) 2: (sk0,pk0)←$KeyGen() 3: (sk1,pk1)←$KeyGen() 4:b←${0,1};r←$Z∗ q 5:pk′←ChgPK(pkb, r) 6:sk′←ChgSK(skb, r) 7:inp ←((sk0,pk0),(sk1,pk1),pk′) 8:b′←$AOchSign1,OchSign2(pp,inp) 9:return b=b′ OchSign1(m) σ←$Sign(sk′, m) return σ OchSign2(m, r′) sk′′ ←ChgSK(sk′, r′) σ←$Sign(sk′′, m) return σ Expeuf-cma A,SFPK(1λ) 1:pp ←$Setup(λ) 2:Qsig ← ∅ 3: (sk,pk, τ)←$TrapGen() 4: (pk∗, m∗, σ∗)←$AOunfSign1,OunfSign2(pk, τ) 5:return (m∗, σ∗)/∈Qsig 6:∧ChkRep(τ, pk∗) = 1 7:∧Verify(pk∗, m∗, σ∗) = 1 OunfSign1(m) 1:σ←$Sign(sk, m) 2:Qsig ←Qsig ∪ {(m, σ)} 3:return σ OunfSign2(m, r) 1:sk′←ChgSK(sk, r) 2:σ←$Sign(sk′, m) 3:Qsig ←Qsig ∪ {(m, σ)} 4:return σ Figure 5. Experiments for SFPK class-hiding and (strong) unforgeability. Exppku A,ARKG(1λ) 1:pp ←$Setup(λ) 2: (sk,pk)←$KeyGen() 3:b←${0,1} 4:b′← AOpku (pk) 5:return b′=b Opku() 1: (pk0,cred, τ)←$DerivePK(pk) 2:sk0←DeriveSK(sk,cred) 3: (sk1,pk1)←$KeyGen() 4:return (skb,pkb,cred) Expsks A,ARKG(1λ) 1:pp ←$Setup(λ) 2:Qpk′, Qsk′← ∅ 3: (sk,pk)←$KeyGen(pp) 4: (sk∗,pk∗,cred∗)← AOdpk,Odsk (pk) 5:sk′←DeriveSK(sk,cred∗) 6:return ChkKeys(pp,sk∗,pk∗) 7:∧ChkKeys(pp,sk′,pk∗) 8:∧cred∗/∈Qsk′ Odpk(pk,aux) 1: (pk′,cred, τ)←DerivePK(pk,aux) 2:Qpk′←Qpk′∪ {(pk′,cred)} 3:return (Qpk′,pk′,cred, τ) Odsk(sk,cred) 1:sk′←DeriveSK(sk,cred) 2:Qsk′←Qsk′∪ {cred} 3:return (Qsk′,sk′) Figure 6. Experiments for ARKG pk-unlinkability and sk-secrecy.