Sponsored Group Signature and its Application to Privacy-preserving Guest Access in Smart Environments

Sponsored Group Signature and its Application to Privacy-preserving Guest Access in Smart Environments Sepideh Avizheh, Reihaneh Safavi-Naini, Shiwei Sun

arXiv:2606.25248v1 [cs.CR] 24 Jun 2026

University of Calgary, Alberta, Canada Abstract—Group signatures are privacy preserving signature schemes in which a group member can anonymously sign messages on behalf of the group, while providing accountability, by allowing the signature of a misbehaving group member be “opened” and the identity of the signer be revealed. In group signature members are admitted to the group by a (trusted) group manager. We motivate the need for a flexible mechanism in applications, such as privacy preserving access in smart environments, and propose a two-level member-join group signature that we call SPonsored Group Signature (SPGS) where group members of level 1 can “sponsor” new members, in level 2, to join the group. This relaxation of user join comes with additional accountability mechanisms: we require that the signature of a sponsored member can be opened to the identity of the sponsor (that is sponsor is responsible for the sponsored member), and while all signatures are anonymous, for the sponsored members, the signatures are linkable. This allows a sponsor to efficiently identify an undesirable sponsored member. We formalize SPGS scheme, define its security using a game-based approach, and give a generic construction of SPGS that uses a (dynamic) group signature scheme, a commitment scheme, and a knowledge-sound non-interactive zero knowledge proof of knowledge, and prove its security. We also give an instantiation of our construction. To show applicability of SPGS in practice, we consider the problem of providing guest access in a smart building, and introduce Anonymous Guest Access Token (AGAT) that allows a temporary guest to anonymously access (a subset of) the building resources. We show how SPGS can be used (together with an IND-CPA secure public key encryption scheme) to give a direct construction for AGAT, and show the efficiency of our guest access protocol when it is instantiated with existing schemes. Index Terms—Group signatures, Anonymous guest access token, Secure guest access, smart buildings

. I. I NTRODUCTION Group signatures were proposed by Chaum and van Heyst [1] as privacy preserving signature schemes that enable a group member to anonymously sign messages on behalf of the group, while providing accountability by allowing the signature of a misbehaving group member to be “opened” and the identity of the signer be revealed. The accountable privacy that is offered by group signatures has found many real-life applications in practice including corporate communication and remote attestation. In a basic group signature, a Group Manager (GM) sets up the parameters and the public key, gpk, of the system. A new group member interact with the group manager to obtain their

own private signing key gsk that is used to sign messages. The signatures of enrolled members can be verified using gpk. Fully dynamic group signatures allow users to join at anytime during the lifetime of the system (they allow user revocation also). Group signatures provide accountable signer anonymity in the sense that signatures of two group members with gsk1 and gsk2 , are indistinguishable, but the GM (or a separate opening authority) can open a signature and reveal the identity of the signer. Two additional properties of anonymous signatures are exculpability and framing resistance that aim to strengthen security of group signatures: exculpability protects users during the join phase and ensures that the GM cannot cheat users and give them a malformed credentials, and framing resistance protects them during the signing phase, ensuring that the GM, or others, cannot produce signatures that implicates them. An important property that seems to weaken the anonymity of group signatures, although it is useful in many real-life scenarios, is linkablity that maintains user anonymity while links together the signatures of a user. Linkability, is a very useful property in applications where users’ accesses to the system must be monitored, and their mis-behavior detected. Linkability can be used to anonymously profile users and ensures that users follow access policies of the system while maintaining their anonymity. Signature opening in a linkable group signature [2] effectively reveals the identity of the signer in all linked signatures. User join in group signatures needs interaction of the GM with the user and this necessitates the GM to be always online and available. Ring signatures are anonymous group signatures that remove the need for the GM: a signer can choose a group of users (using public information of users) and sign a message as a member of the group, providing unconditional (1 out n) anonymity, with no possibility of “opening” the signer of a message. This level of anonymity for signers is essential in applications such as whistle-blowing but it is limiting in accountable anonymous communication. Liu et al [3] argued the need for linkability and ad hoc group formation, that is removing trusted group manager and supporting some level of accountability, and introduced Linkable Spontaneous Anonymous Group (LSAG) signatures. LSAG is considered as an extension of ring signature, where a user can form an spontaneous group of n− 1 users and sign

as one of the n users, while signatures of a user are linkable. LSAGs, however, provide (1 out n) anonymity without possibility of opening, and has signature length that is proportional to n. In comparison, group signatures provide indistinguishability of the signers of any two signed messages (see Definition A.1), and can be constructed with constant length, but the join and open operations require a trusted GM. A. Our work We propose an extension of a group signature that provides flexible user join in the sense that enrolled users in the system can sponsor new users, hence allowing new users to join the system without interacting with the group manager, while maintaining accountability. Although relaxing the group join to be partially handled by the members could be a useful property, it raises questions about security of the system and accountability of the members that join by other members. We show that linkablity can be used to provide the required accountability for this type of group membership. Our motivating scenario (that is further discussed in Section V) is providing privacy preserving guest access in smart buildings/homes. To provide privacy preserving access for registered entities (aka, hosts/residents) of the building, a group signature can be used where each host is a group member and uses their individual private key to anonymously authenticate themselves to the system and access the building’s shared resources (e.g. printer). Our goal is to enable the host to provide privacy preserving temporary access to the building’s resources to a guest, where privacy preserving refers to anonymity of guests and hiding the host’s identity. Ideally, we would like a guest who is “approved” by a host to be able to access the building resources without being linked to any particular host. This scenario models many real-life settings including work environments that support visitors with temporary guest access such as universities, research labs and corporations. Solutions that use exiting cryptographic primitives (examples are given in Section V) result in costly and privacy invasive solutions. In particular, using existing group signatures require a GM that is always online, and that the need for the host interaction with the GM adds an additional complexity if guest’s privacy is required. Sponsored group signature. Our approach is to construct a novel hierarchical two-level1 group signature called Sponsored Group Signature (SPGS) where users are in two distinct levels: the first (higher) level members, called sponsors, Sp are enrolled in the system by interaction with the GM. Members of the second (lower) level, called sponsored members, Sm, consist of members who are enrolled in the system by the sponsors and without interaction with the GM. The group public key, gpk, remains the same (as the group public key of sponsors) and the sponsored members do not need to interact with the group manager to get a new group public key. Intuitively, this structure solves the guest access problem as it allows a host (sponsor) to enroll a guest (sponsored member) 1 Our approach can be generalized to multi-level signature systems,

in the system. SPGS systems, however, must ensure that the relaxation of join protocol to enroll sponsored members does not adversely affect security of the sponsor (original group member) signatures. In particular, a sponsor (is not assumed trusted –see security model of sponsored group signatures in Section IV), cannot abuse their user join capability, while anonymity and privacy of (honest) sponsored members are maintained. Accountable flexible join. We achieve the goal of providing secure flexible join by requiring linkable anonymity for sponsored members, and opening of a sponsored-member’s signature to the corresponding sponsor. This combination allows anonymous profiling of sponsored members who are not vetted by the group manager, and ensures accountability of sponsors in using their additional new enrollment capability. Algorithms. SPGS consists of a tuple of {Setup, Joinattr , Signattr , V erif y attr , Openattr } algorithms where attr ∈ {Sp, Sm}, defining two sets of algorithms for the two levels of users, Sp and Sm. In both levels, the private key of a member (sponsor or sponsored) is known to the member only, preventing framing of the user. In Section IV, we define the SPGS algorithms and their security properties using a game-based approach, following the framework of Bootle et al. [4] where adversary’s access to the system is defined by a set of oracles. Definition IV.1 quantifies security properties of SPGS that are formalized in Fig. 2. In Appendix A we also use the framework to define security of a group signature that we use in our proofs inline with commonly used definitions in [4]. SPGS construction. We propose a generic construction in the standard model which uses a partially dynamic group signature, a commitment scheme, and a knowledge-sound noninteractive zero knowledge proof of knowledge (NIZK) as building blocks (see Section IV-A). Our SPGS construction is an extension of a group signature, GS, that is, the level 1 (sponsors) algorithms are the corresponding algorithms of the group signature. The level 2 (sponsored members) algorithms, consists of a group signature GS and a Fiat-Shamir based NIZK. When the sponsors join, they interact with the GM, at the end of which they get a group private and public key corresponding to the GS scheme. When the sponsoredmembers join, they interact with the sponsor, choose a random key and use the commitment to the random key as their public keys. At the end of join phase, a sponsored-member gets a sponsor signature (which is a group signature) on their public key. The sponsored-member, when signs a message m will generate a NIZK that, in the simplest form, shows that it knows the corresponding private key while considering the message to be signed as part of the public parameters of the NIZK. The NIZK proof and the sponsored-member signature can vary depending on the application context that SPGS is used; for example one can use a homomorphic commitment scheme to generate their public keys that allows the sponsoredmember to re-randomize their keys and derive many keys (that can be used to register with different service providers). In this case, the NIZK proof additionally shows that the re-

randomization has been done correctly. We prove the security of our construction and show it achieves the required security properties. Additionally, we provide a concrete and efficient instantiation of the SPGS. SPGS and its applications. We give an application of SPGS to the construction of k-times Anonymous Guest Access Token (k-AGAT) in a smart building that allows the guests use the building’s resources. This has been one of the main motivation of proposing a new type of group signature. kAGAT allows the host to determine its policy preferences such as expiry time when it issues a guest token. Also, it allows the verifier to bound the number of guest tokens per each host to k tokens. This is achieved since in k-AGAT the issued tokens by a host are linkable. Also, the tokens presented by the same guest are linkable and the guest’s behavior can be traced. In case of misbehavior, the presented guest tokens can be opened to the identity of the host who issued the token. We define k-AGAT and its security requirements that are correctness, unforgeability, anonymity, and traceability in Section V. We also give a k-AGAT construction and show it satisfies the k-AGAT security and privacy requirements. In our k-AGAT construction, SPGS is used together with an IND-CPA secure public key encryption scheme, which allows the host act as the sponsor and signs the token content including the public key of the guest. The sponsored-member will transform the token using the sponsored-member signature of SPGS and present it to the verifier. We show how k-AGAT can be used by a guest to access building shared resources. Implementation. We implement cryptographic components of the host, guest and IM for setup and guest access phase. Our implementation results are compared with a non-private solution that only uses a regular signature scheme rater than the group signature to issue guest tokens, show that the overhead our scheme proposes is tolerable while allowing privacy of hosts and guests. This confirms the feasibility and efficiency of our scheme. Paper organization. Section II gives the related work. Section III gives the cryptographic primitives and preliminaries. Section IV defines SPGS formally and give its security properties, Section IV-A describes our SPGS generic construction and its security analysis. Section V provides the application of SPGS in constructing AGAT and secure guest accesses, and Section VI concludes the paper.

Related works can be broadly grouped into the following categories. Group signatures with delegation/hierarchies. Group signature is a widely studied privacy preserving signature scheme [1]. Partially and fully dynamic group signatures allow new users to join the group and/or existing group members to be revoked. User join and revoke, however, are through a single group manager. Delegatable Anonymous Credentials (DAC) [15]–[19] allow users to anonymously obtain credentials (signing rights) from authorities and delegate them to other users (also) prove possession of credentials). Important properties of DAC are unlinkability of users interactions with the system, support for multiple levels of delegation and preserving anonymity of delegators. The main differences with SPGS are that in DACs, all participants use the same cryptographic mechanisms and all delegated credentials are unlinkable. In SPGS, however, the algorithms that are associated to the sponsors and sponsored-members, including signing and verification algorithms, are different and and signatures of a sponsored-member are linkable. In DACs [15], [17], [19], addition of a new member, however, is through a single trusted group manager while in SPGS, it is decentralized. Linkable Ring Signatures (LRS) [3], [20]–[22], provide anonymity with linkability for signatures and spontaneity for group membership (no group secret or group manager). In an LRS scheme, a user can spontaneously form an ad-hoc group and sign messages anonymously as a member of that group. Linkability in LRS is for signatures of all users while in SPGS it is for sponsored members. Other related schemes are accountable tracing signatures [23] where the authority must prove it only opened specific users’ signatures and did not abuse its power, and Bifurcated Anonymous Signatures (BiAS) [24] a user to determine conditions for tracing through a predicate and Traceable Signature [25] that refines the type of tracing. These signatures, however, do not support decentralized member addition. Proxy Signatures [26] allow delegation of signing rights to proxies that can be further delegated. Finally an important property of SPGS is non-frameability and key independence that ensures private keys are only known to the users. This property guarantees that colluding parties cannot forge signatures that frame group members.

II. R ELATED WORK

In this section, we give the definition and notations used for the necessary cryptographic primitives (please see Appendix for the extended preliminaries covering the cryptographic primitives used in our application). Notation. We use out ← A(in) to show that the algorithm A is applied on the input in to generate output out. We use A : ops to Show party A performs operations ops.

Group signatures were introduced by Chaum and Heyst [1], allowing users to anonymously signing on behalf of the group, and have found many extensions including [3]–[14]. SPGS is a privacy preserving (two-level) hierarchical group signature with two types of members (sponsor and sponsored), each belonging to one level of the hierarchy, that provides full anonymity for sponsors (level 1) and linkable anonymity for sponsored members (level 2), that supports decentralized user join through sponsorship by members of the first level of the hierarchy (sponsors), and user accountability by providing “signature opening” functionality by a trusted group manager.

III. P RELIMINARIES

A. Cryptographic primitives Digital signature (DS) consists of three algorithms: (i) DS.KeyGen(1λ ), which receives the security parameter λ and outputs the private and public key pair (Sk, P k).

(ii) DS.Sign(Sk, m) which receives the private key sk and a message m, and outputs a signature σ. (ii) DS.V erif y(σ, m, P k) which takes the signature σ, the message m and the public key P k and outputs 1 if the signature is verified and 0 otherwise. We consider the standard notion of existential unforgeability under chosen message attack EU F -CM A. Group signatures allow a member of a group (which is manged by the group manager M) to generate a signature anonymously such that a verifier can verify the validity of the signature knowing only the public parameters of the system. The manager is responsible for the correct functioning of the group, and can reveal the identity of the signer. We consider a partially dynamic group signature GS that allows new members to join. GS is composed of the following algorithms: (i) GS.Setup(1λ , setpp) = (pp, msk), is run by M and it takes the security parameter λ and set up parameters SP , and outputs the public parameters pp and the manager’s secret key msk. (ii) GS.Join(idu , paramM ) is an interactive algorithm that is run between a M and the user idu who desire to join the group (we assume all interactions takes place over a secure channel similar to [5]). (iii) GS.Sign(m, paramu ) = σ, this algorithm is run by the member idu with its private parameters paramu , and outputs a valid anonymous signature σ. (iv) GS.V erif y(m, σ, pp) = 0/1, is run by the verifier and takes as input the message m, the signature σ, and the public parameters of the system pp, and outputs 1 if the signature is valid, or 0 otherwise. (v) GS.Open(msk, σ) = idu , is run by M to reveal the identity of the signer of σ. We consider that GS ensures the following security requirements: correctness, anonymity, non-frameability, and traceability. For the security requirements we follow the definitions provided by Bootle et al. [4] and adapt them to a simpler setting were the group manager M act as both issuing authority and opening authority, and is assumed to be partially corrupted (i.e., its private state can be leaked). Also, we do not consider the Judge algorithm since M follows the protocol correctly and traces the signatures if needed. Please see Appendix A for the security requirements and definitions. Public key encryption consists of the following algorithms: (i) E.KeyGen(1λ ) takes the security parameter as input and outputs the private/public key pair (Sk, P k). (ii) E.Enc(P k, m) takes the public key P k and message m and outputs the ciphertext C. (iii) E.Dec(Sk, C) takes the private key Sk and ciphertext C as input and outputs the message m. We consider an IND-CPA secure encryption scheme. Commitment consists of the following algorithms. (i) C.Setup(1λ ) receives the security parameter and outputs the commitment public parameters cpar, (ii) C.Com(x) receives the input x and outputs the opening information d and the commitment com, (iii) C.Open(com, x, d) takes the commitment com, and the opening x and d as input and outputs 1 if x and d are correct openings for com, and outputs 0 otherwise. A commitment scheme ensures hiding and binding properties. In our concrete construction, we consider a homomorphic commitment scheme which includes the additional

algorithm HCom which allows to change the committed value by knowing the commitment com on x. In another words, C.HCom(com, x′ ) outputs a commitment com′ on x + x′ . Non-interactive zero knowledge arguments of knowledge (NIZK) consists of the following algorithms: (i) N IZK.Setup(R) which takes the relationship R (which implicitly defines the security parameter λ) and outputs the common reference string crs. (ii) N IZK.P rove(crs, ρ, x, w) which takes the common reference string crs, the common input ρ, the statement x that is being proven about ρ, and the witness w as input and outputs the proof π. (iii) N IZK.V erif y(crs, π, ρ, x) receives the common reference string crs, the proof π, the common input ρ, and the statement being proven as input and outputs 1 if the proof is verified and 0 otherwise. We consider a NIZK that ensures perfect completeness, computational zero-knowledge, and computational knowledge-soundness properties (see Appendix A for definitions). We consider sigma protocol for a relation R that is a 3-move public coin protocol between a prover and a verifier both of which know the common input ρ and the statement x, and the prover knows the witness w such that R(w, x) = 1. The prover sends the first message which is a commitment to a random value, and the verifier sends back a random challenge as the second message, and the the third message will be the prover’s response on the first two messages and the witness w. Sigma protocols ensure zero knowledge (with honest verifiers) and knowledge soundness considering that there is an extractor who can extract a witness from the protocol transcripts if the protocol is run twice with the same first message and different challenges. The fiat-Shamir transform can be applied on any public coin protocol including a sigma protocol to obtain a non-interactive version of that. This transformation preserves the knowledge soundness property when it is analyzed in random oracle model. We use sigma protocols in our concrete constructions. IV. S PONSORED GROUP SIGNATURE (SPGS) SPonsored Group Signature (SP GS) is a hierarchical group signature with two levels, supporting decentralized user join for members of the second level (sponsored members): a sponsored-member joins (spontaneously) by a sponsor without the need to interact with the group manager. SPGS offers full anonymity for sponsors and linkable anonymity for sponsored members. All signatures in SPGS can be opened to the sponsor’s identity, in the case of sponsored-members misbehavior. We define SPGS with only user’s join, and leave the extension of the scheme to provide efficient revocation for future work. Entities. We consider the following entities: group manager, sponsors (level 1 (L1) members), sponsored-members (level 2 (L2) members), and verifiers. 1) Group manager (M) is a trusted entity that sets up the group and its parameters, and generates the group public key gpk ∈ pp. To provide accountability, we enable the group manager to open the signatures (one can design

a system such that this task is performed by a second authority). Although we assume the group manager is trusted, in our security evaluation, we allow the group manager’s private state be leaked to the adversary. 2) Sponsor (Sp) is a L1 member in the group that is added to the group by M), and obtains their private key gsk ∈ paramsp through interaction with M. A sponsor has the ability to add L2 members to the group and provide them with the system’s public parameters pp. 3) Sponsored-member (Sm) is a L2 member of the group that is added to the group by an sponsor Sp, and receives their private key sk ∈ paramSm , through interaction with the sponsor. Trust relationship between Sp and Sm is delicate: they do trust each other in performing the cryptographic operations correctly, and Sp is willing to take the responsibility (hence called sponsor) for Sm’s actions in the group in the sense that an Sm’s misuse of its signing capability can be traced to Sp. 4) Verifiers (V ) can verify signatures of Sps and Sms using the group public key and public parameters. Definition. SP GS is defined by a parameterized tuple of algorithms {Setup, Joinattr , Signattr , V erif y attr , Openattr } where the parameter attr ∈ {Sp, Sm} specifies the associated type (level) of the member. The relationship between entities in terms of enabling group membership can be summarized as M → Sp → Sm, denoting M enrolling Sp, and Sp enrolling Sm. Setup(1λ , setpp) = (pp, msk), is run by M and it takes the security parameter λ and set up parameters setpp, and outputs the public parameters pp and the manager’s secret key msk. attr • Join (idattr , param) is an interactive algorithm that is run either between a M and the user idSp who wants to join as a sponsor if attr = Sp, or it is run between the sponsor and the user idSm who wants to join as a sponsored-member if attr = Sm. It takes the private parameters param of the enrolling entity belongs to {M, Sp}, and outputs private parameters paramattr to the joining entity idattr and out to the enrolling entity belongs to {M, Sp} (we assume all interactions takes place over a secure channel similar to [5]). out shows the termination, whether the algorithm succeeds ⊤ or fails ⊥. attr • Sign (m, paramattr ) = σ, this algorithm is run by the sponsor or sponsored-member depending on attr ∈ {Sp, Sm}, with its private parameters paramattr , and outputs a valid anonymous signature σ. attr • V erif y (m, σ, pp) = 0/1, is run by the verifier and takes as input the attribute attr ∈ {Sp, Sm}, the message m, the signature σ, and the public parameters pp, and outputs 1 if the signature is valid, or 0 otherwise. attr • Open (msk, σ) = idSp , is run by M, it takes a sponsor or sponsored-member signature σ, where attr ∈ {Sp, Sm}, and reveals the identity of the sponsor of σ. •

Security requirements. SP GS satisfies the following se-

curity requirements: correctness, non-frameability, sponsor anonymity, sponsor traceability, sponsored-member privacy and sponsored-member linkability. Our definitional framework is based on the framework of Bootle et al. group signatures [4] and is provided for the case of partially dynamic groups (group with join) and allows the group manager to be partially corrupted and its state leak. For sponsored-member linkability, our definition is inspired by the signer linkability notion defined in [3]. Correctness ensures that if an honest member joins as a sponsor or sponsored-member and generates a signature, their signature will be verified. In our setting where the members can join at any time, these two conditions should hold for all honest members under any schedule under which the members join the group. Therefore, to formalize correctness we consider an adversary who can control users’ joining process and chooses the messages and the identity of the signers (both sponsor and sponsored-members). We require that for any messages and identities that the adversary chooses, the signatures generated can be verified correctly. • Non-frameability captures unforgeability in a strong sense and ensures the following: the collusion of all members except one honest group member P , that has access to the private state of the group manager, cannot generate a valid signature that, (i) if P is of type sponsor (i.e.,attr = Sp), be opened to P , and (ii) if P is of type sponsored-member (i.e.,attr = Sm), and is added to the group through a correct execution of JoinSm by a sponsor P ′ , be opened to P ′ . We allow the adversary to have oracle access to the member signing algorithm. • Sponsor anonymity states that no one (including other sponsors and the verifier) can distinguish the sponsor who has generated a given signature from idSp0 and idSp1 better than a random guess even if they have seen the output of the Open algorithm for some signatures. M is considered trusted for anonymity as M can always open the signatures and learn the identity of the sponsors. This definition is aligned with the signer anonymity definition of group signatures and captures sponsor signatures unlinkability as well. • Sponsor traceability protects the group manager by ensuring that any valid sponsor or sponsored-member signature will be opened to the identity of a sponsor. This is achieved even if the group manager’s private state is leaked (i.e., M is considered partially corrupted). • Sponsored-member privacy is defined similar to sponsor anonymity in the sense that no one can distinguish the sponsored-member who has generated a given signature from idSm0 and idSm1 better than a random guess. However, for sponsored-member privacy, we exclude unlinkability from the definition by restricting the oracle access of the adversary to the signing oracle, that is, the adversary cannot issue queries to the SignHU (Sm, ·, ·) oracle for the challenged sponsored-members. •

•

Sponsored-member linkability requires that the signatures of a sponsored-member be linkable. Our definition adapts the signer linkability definition in [3] to SPGS. We give more details on this adaptation in Lemma A.1.

Oracles. To formally define the security requirements, we use the following oracles (given in Figure 1). AddHU(attr, idattr ): This oracle allows the adversary to add honest users through honest execution of Joinattr (to add sponsors or sponsored-members attr ∈ {Sp, Sm}) without learning their private parameters. • CorrU(idattr ) allows the adversary to corrupt the users (i.e., sponsors and sponsored-members) and learn both their communication transcript when they run Joinattr algorithm honestly and their private parameters (including signing keys). Thus, this oracle allows full exposure of all communication and keys, and can be run only immediately after AddHU (attr, idattr ). • AddCU(attr, idattr ): This oracle allows the adversary to add corrupted users (sponsors or sponsored-members attr ∈ {Sp, Sm}) to the group. The adversary can deviate from the Joinattr protocol and send arbitrary messages to the honest enrolling entity e ∈ {M, Sp} and see its output oute . • AChalb (pp, m, idSp0 , idSp1 ): This is a left-right oracle for defining sponsor anonymity. It takes as input the group public parameters pp, a message m, and two honest sponsors idSp0 and idSp1 , and returns a sponsor signature on the message m using the private parameters of paramSpb for b ← {0, 1}. The adversary can call this oracle once. • PChalb (pp, m, idSp , idSm0 , idSm1 ): This is a leftright oracle for defining sponsored-member privacy. It takes as input the group public parameters pp, a message m, the identity of an honest sponsor idSp , and two honest sponsored-members idSm0 and idSm1 , runs JoinSm internally to obtain their private parameters, and returns a sponsored-member signature on the message m using the private parameters of paramSmb for b ← {0, 1}. The adversary can call this oracle once. • LChalb (Sm, pp, m0 , m1 , set0 , set1 ): This is a leftright oracle for defining sponsored-member linkability which is defined fpr Sm. It takes as input the group public parameters pp, two messages m0 and m1 , and two sets set0 : {idSm0 , idsm0 } and set1 : {idSm0 , idsm1 } and returns two group signatures σ0 and σ1 on message m0 and m1 respectively using the private parameters of the entities in setb , for b ← {0, 1}. The adversary can call this oracle once. • SignHU(attr, m, paramattr ) This oracle is used by the adversary to obtain signatures for an honest user whose private parameters are not known by the adversary. It returns a signature σ on the message m using the Signattr algorithm with the private parameters of idattr , where attr ∈ {Sp, Sm}. • Open(attr, msk, m, σ, pp) returns the identity of the

•

sponsor idSp who has generated or sponsored the signature σ. The oracle cannot be called on a signature obtained from the AChalb , LChalb , and P Chalb oracles. • CorrM() returns the private parameters of the manager M. Definition IV.1. For a security parameter λ ∈ N and a PPT adversary A, we say that SP GS provides: 1) Correctness if there exists a negligible function ν1 Corr Corr such that AdvSP GS,A (λ) = P r[ExpSP GS,A (λ) = 1] ≥ 1 − ν1 (λ) 2) Non-frameability if there exists a negligible N on−F rame function ν2 such that AdvSP (λ) = GS,A on−F rame P r[ExpN (λ) = 1] ≤ ν (λ) 2 SP GS,A 3) Sponsor anonymity if there exists a negligible function SpAnon SpAnon−b ν3 such that AdvSP GS,A (λ) = P r[ExpSP GS,A (λ) = 1 1] ≤ 2 + ν3 (λ) 4) Sponsor traceability if there exists a negligible function SpT race SpT race ν4 such that AdvSP GS,A (λ) = P r[ExpSP GS,A (λ) = 1] ≤ ν4 (λ) 5) Sponsored-member privacy if there exists a SmP riv negligible function ν3 such that AdvSP GS,A (λ) = SmP riv−b 1 P r[ExpSP GS,A (λ) = 1] ≤ 2 + ν5 (λ) 6) Sponsored-member linkability if there exists a SmLink negligible function ν5 such that AdvSP GS,A (λ) = SmLink−b P r[ExpSP GS,A (λ) = 1] ≥ 1 − ν6 (λ) on−F rame ExpN , ExpSpAnon where ExpCorr SP GS,A , SP GS,A SP GS,A , SpT race SmP riv SmLink ExpSP GS,A , ExpSP GS,A , ExpSP GS,A are defined in Figure 2.

Linkability of the sponsored-member signature. Our definition of linkability follows from the signer linkability notion defined in [3] but revises the definition to an equivalent one, as outlined below. Consider a PPT algorithm F which takes two signatures and outputs 1 if the two signatures are linked (signed by the same user) and 0 otherwise. Liu et al. [3] definition of linkability requires that the two following probability statements hold: (i) The probability that F outputs 0 when the two signatures are generated by the same entity is negligible, i.e., P r[F (m0 , m1 , σ0 , σ1 ) = 0 : idSm0 = idSm1 ] ≤ ν(λ), and (ii) the probability that F outputs 1 when the two signatures are generated by two distinct users is negligible, i.e., P r[F (m0 , m1 , σ0 , σ1 ) = 1 : idSm0 ̸= idSm1 ] ≤ ν(λ), for any idSm0 , idSm1 and any messages m0 and m1 , and any σ0 ← Sign(Sm, m0 , paramSmi ), σ1 ← Sign(Sm, m1 , paramSmi ) and i ∈ {idSm0 , idSm1 }. We define sponsored-member linkability using the random variable ExpSmLink−b SP GS,A , and the advantage of the PPT algorithm A. The adversary A will choose a pair of identities, idSm0 and idSm1 , and must decide if a pair of received signatures are signed by

AddHU(attr, idattr ) • If N > Nmax Return ⊥ • Update H ∪ {idattr } and N = N + 1 attr • paramattr ← Join (idattr , param) • Let the Join transcript is stored in trscJoinattr • Store QHU = QHU ∪ (idattr , trscJoinattr , paramattr , oute ) • Return pp CorrU(idattr ) • If idattr ∈ / H Return ⊥ • Update C ∪ {idattr } and H = H\{idattr } • Retrieve (idattr , trscJoinattr , paramattr , oute ) from QHU • Return trscJoinidattr , paramattr , and oute AddCU(attr, idattr ) • If idattr ∈ H Return ⊥ • Update C ∪ idattr attr • paramattr ← Join (idattr , param) • Return paramattr and oute AChalb (pp, m, idSp0 , idSp1 ) / H Return ⊥ • If idSp0 , idSp1 ∈ Sp • σb ← Sign (m, paramSpb ) Sp • If V erif y (m, σb , pp) = 0 Return ⊥ • Update QAChal ∪ (Sp, m, σb ) • Return σb

SignHU(attr, m, paramattr ) • If paramattr =⊥ Return ⊥ attr • σ ← Sign (m, paramattr ) • Update QSign ∪ (attr, m, σ) • Return σ Open(attr, msk, m, σ, pp) • If (attr, m, σ) ∈ QSign ∪QAChal ∪QLChal ∪QP Chal Return ⊥ attr • If V erif y (m, σ, pp) = 0 Return ⊥ • Return Open(msk, σ) CorrM() • Return paramM PChalb (pp, m, idSp , idSm0 , idSm1 ) • If idSp ∈ / H ∨ idSm0 , idsm1 ∈ QJoin Return ⊥ Sm • ∀i ∈ {0, 1} run paramSmi ← Join (idSmi , paramSp ) ′ Sm • σb ← Sign (m, paramSmb ) Sm • If V erif y (m, σb′ , pp) = 0 Return ⊥ ′ • Update QP Chal ∪ (Sm, m, σb ) ′ • Return σb LChalb (Sm, pp, m0 , m1 , set0 , set1 ) • Parse set0 : {idsm0 , idsm0 } and set1 : {idsm0 , idsm1 } / H Return ⊥ • If idSm0 , idSm1 ∈ Sm • ∀i ∈ {0, 1} run σi ← Sign (mi , paramsetb,i ) Sm • ∀i ∈ {0, 1} if V erif y (mi , σi , pp) = 0 Return ⊥ • Update QLChal ∪ (Sm, m0 , σ0 ) ∪ (Sm, m1 , σ1 ) • Return σ0 , σ1

Fig. 1. Oracles used in experiments

idSm0 , or two entities (idSm0 and idSm1 ) by outputting 1 or 0, to show whether the two signatures are from the same identity or not. We show that this is equivalent to the definition in [3] in Lemma A.1 in Appendix A. A. Our construction In the following, we give a generic construction using a (partially) dynamic group signature scheme denoted by GS consisting of (GS.Setup, GS.Join, GS.Sign, GS.V erif y, GS.Open) algorithms, a commitment scheme denoted by C consisting of (C.Setup, C.Commit, C.Open) algorithms, and a knowledge-sound non-interactive zero knowledge proof of knowledge denoted by N IZK consisting of (N IZK.Setup, N IZK.P rove, N IZK.V erif y) algorithms (see Section III and Appendix A and A for their definitions and security requirements). To join, Sp interacts with M and calls GS.Join to get the group private and public key. The signature of Sp is a group signature which will be generated by running GS.Sign. To enroll Sm to the system, Sm will generate a pair of private and public keys and will receive the signature of Sp on its public key. The public key of Sm is generated by running the commitment C.Commit on a random vbalue chosen by Sm, which is used as its private key. Sm’s signature on message m is obtained by generating a NIZK proof with the private key as the witness and the message m as part of the public parameters. The signature of Sm consists of the obtained sponsor signature σ on its public key P kSm , the public key, P kSm , and the NIZK proof π. (P kSm , π) can be seen as

a signature of knowledge (SOK) (see Appendix A for SOK definition). Below we give the details of the scheme. Setup(1λ , setpp) → (pp, msk), is run by M, it takes the security parameter λ, and setup parameters setpp (including the relation R for NIZK), and perform the followings: – runs (pp′ , msk) = GS.Setup(1λ , setpp) – runs crs = N IZK.Setup(R) – runs cpar = C.Setup(1λ ) – outputs the public parameters pp = (pp′ , cpar, crs) and the manager’s secret key msk. Sp • Join (idSp , paramM ) → paramSp is run between a manager M and the user idSp who desire to join the group and act as a sponsor. Round (1) Sp sends its identity idSp to the manager M. – M runs paramSp = GS.Join(idSp ). Round (2) M sends paramSp to Sp. – M outputs ⊤. Sm • Join (idSm , paramSp ) → paramSm , this interactive algorithm is run between the sponsor idSp and the sponsored-member idSm . Round (1) Sp sends the commitment parameters cpar to Sm. – Sm generates a private key, denoted by skSm , and computes (P kSm , r) = C.Com(skSm ). Round (2) Sm sends its public key P kSm to Sp. – Sp sets m = P kSm , and runs σ = GS.Sign(m, paramSp ). •

ExpCorr SP GS,A (pp, msk) ← Setup(λ, setpp), N = 0 (m, idSp , m′ , idSm ) ← AAddHU,CorrU,AddCU,CorrM (pp) If idSp ∈ / H ∨ idSm ∈ / H Return 0 σ ← SignSp (m, paramSp ) σ ′ ← SignSm (m′ , paramSm ) If V erif y Sp (m, σ, pp) = 0 Return 0 If V erif y Sm (m′ , σ ′ , pp) = 0 Return 0 Return 1 on−F rame ExpN SP GS,A (pp, msk) ← Setup(λ, setpp), N = 0, QSign = ∅ (attr, idSp , idSm ⊥, m, σattr ) ← AAddHU,CorrM,SignHU (pp) If attr = Sp ∧ idSp ∈ / H Return 0 If attr = Sm ∧ idSm ∈ / H Return 0 If V erif y attr (m, σattr , pp) = 0 Return 0 If (attr, m, σattr ) ∈ QSign Return 0 ? Return Openattr (msk, σattr ) = idSp

ExpSpAnon−b SP GS,A (pp, msk) ← Setup(λ, setpp), N = 0, QAChal = ∅ b′ ← AAddHU,CorrU,AddCU,Open,AChalb (pp) If b′ ̸= b Return 0 Return 1 race ExpSpT SP GS,A (pp, msk) ← Setup(λ, setpp), N = 0 (attr, m, σattr ) ← AAddHU,CorrU,AddCU,Open,CorrM (pp) If V erif y attr (m, σattr , pp) = 0 Return 0 ? Return Openattr (msk, σattr ) =⊥ riv−b ExpSmP SP GS,A (pp, msk) ← Setup(λ, setpp), N = 0, QP Chal = ∅ b′ ← AAddHU,CorrU,AddCU,Open,P Chalb (pp) If b′ ̸= b Return 0 Return 1

ExpSmLink−b SP GS,A (pp, msk) ← Setup(λ, setpp), N = 0, QLChal = ∅ b′ ← AAddHU,CorrU,AddCU,Open,LChalb (pp) If b′ ̸= b Return 0 Return 1 Fig. 2. Security games of SP GS

Round (3) Sp sends the private parameters paramSm = (pp, σ, P kSm ) to Sm. – Sp outputs ⊤. Sp • Sign (m, paramSp ) → σ, this algorithm runs by the sponsor idSp . It takes m and paramSp as input, and – computes σ = GS.Sign(m, paramSp ) – outputs the sponsor signature σ. Sm • Sign (m, paramSm ) → σ ′ , is run by the sponsoredmember idSm . This algorithm – parses paramSm = (pp, σ, P kSm ) – generates a zero-knowledge proof as π = N IZK.P rove(crs, ρ, x, w) where ρ = (m, P kSm ), w = (skSm , r), and x = [∃(skSm , r) : (P kSm , r) = C.Com(skSm )]. – outputs the sponsored-member signature σ ′ = (σ, P kSm , π).

V erif y Sp (m, σ, pp) → 0/1, is run by the verifier and takes as input the message m, the sponsor signature σ, and the public parameters of the system pp, it – verifies the sponsor signature b = GS.V erif y(m, σ, pp) – outputs b. Sm • V erif y (m, σ ′ , pp) → 0/1, is run by the verifier and takes as input the message m, the sponsored-member signature σ ′ , and the public parameters of the system pp, it – parses the sponsored-member signature σ ′ = (σ, P kSm , π) – verifies the sponsor signature b = GS.V erif y(P kSm , σ, pp) – verifies the zero-knowledge proof b′ = N IZK.V erif y(crs, π, ρ, x) where ρ = (m, P kSm ) and x = [∃(skSm , r) : (P kSm , r) = C.Com(skSm )]. – outputs 1 if both b = 1 and b′ = 1, or 0 otherwise. SP • Open (msk, σ ′ ) → idSp , is run by M; it computes idSp = GS.Open(msk, σ), and outputs idSp . Sm • Open (msk, σ ′ ) → idSp , is run by M; it parses σ ′ = (σ, P kSm , π), then computes idSp = GS.Open(msk, σ), and outputs idSp . •

B. Security analysis The following theorem summarizes our security analysis: Theorem IV.1. Our generic construction of SP GS given in Section IV-A achieves correctness, non-frameability, sponsor anonymity, sponsor traceability, and sponsored-member linkability assuming GS ensures correctness, unforgeability, anonymity, traceability, the N IZK ensures completeness, computational zero knowledge, and computational knowledge soundness, and C is a hiding and binding additive homomorphic commitment scheme. Proof. The proof of theorem consists of a set of lemmas, one for each property, that are outlined below. The detailed proof sketch using hybrid games is given in the Appendix A. Lemma IV.2. Correctness. Our generic construction of SP GS achieves correctness, if the group signature GS and commitment C ensure correctness and N IZK ensure completeness. The proof is straightforward. Lemma IV.3. Non-frameability. Our generic construction of SP GS achieves non-frameability, if N IZK ensures knowledge soundness, the commitment C is binding, and the group signature GS is non-frameable. We consider two cases, where (i) attr = Sp, and (ii) attr = Sm. In (i) the adversary outputs a sponsor signature, which is a group signature. Due to the non-frameability of GS, the success probability of the adversary will be negligible. In (ii) the adversary outputs a sponsored-member signature which consists of a group signature, a committed public key,

and a NIZK proof. Since GS is non-frameable, and the join algorithm is executed honestly, the success probability of adversary to output a valid GS is negligible. Additionally, NIZK ensures knowledge soundness which means that the probability that adversary outputs a valid NIZK proof and the extractor extracts the witness w such that (w, x) ∈ / R is negligible. Furthermore, the commitment scheme is binding and the adversary cannot equivocate the private key w. Therefore, the success probability of adversary to output a valid NIZK proof for a public key that has been generated during the honest execution of Join (without knowing the witness) is negligible. Lemma IV.4. Sponsor anonymity. Our generic construction of SP GS achieves sponsor anonymity, if the group signature GS ensures anonymity for the signer. For a sponsor or sponsored-signature the only part that is related to the sponsor is the group signature. The NIZK proof and the sponsored-member public key are independent of the identity of the sponsor and they can be generated using a random private key. Due to the anonymity of GS, sponsor anonymity is obtained. Lemma IV.5. Sponsor traceability. The construction of SP GS given in Section IV-A achieves sponsor traceability, if the group signature GS ensures traceability. Sine the open algorithm uses the group signature (generated by the sponsor) to find the identity of the sponsor, the sponsor traceability is achieved because of the traceability of GS. Lemma IV.6. Sponsored-member privacy. Our generic construction of SP GS achieves sponsored-member privacy, if N IZK is a zero-knowledge argument and the commitment scheme C is hiding. We note that our construction does not include any information about the identity of the signer except for the private and public key information that is generated by sponsoredmember. The public key is shared with the sponsor, and since the commitment is hiding no information about the private key is revealed. Also, the NIZK is zero knowledge and it does not leak any information about the private key. So, the adversary cannot learn any information related to the sponsored-member and cannot identify the signer. Lemma IV.7. Sponsored-member linkability. Our generic construction of SP GS achieves sponsored-member linkability, if GS ensures non-frameability. All the signatures of a sponsored-member include the sponsor signature on their public keys that they have obtained during the Join algorithm. Since GS is non-frameable, no one can forge a valid sponsor signature to break the linkability. Therefore, the adversary can always link the signatures of a sponsored-member with high probability. C. Concrete construction To instantiate our construction, we use the BBS group signature scheme [27] for GS. BBS is a static group signature

scheme with known group size in the key generation phase. We set n to be large enough to accommodate the maximum group size. For commitment scheme, we consider the following Pedersen commitment scheme (on EC) that allows rerandomization and it is as follows: com = C.Com(x) = g x hr , where r = 0 for simplicity, and C.HCom(com, r′ ) = ′ ′ com.g r = g x+r = C.Com(x + r′ ). For N IZK, we consider a sigma protocol-based NIZK (on EC) for discrete log using Fiat-Shamir transform given in the random oracle model in Algorithms 1 and 2. Note that our NIZK in the sponsoredmember signature takes a message m as input (which can be seen as a signature of knowledge) thus in the NIZK algorithms given in 1 and 2, we also include m in the public parameters. m is given as input to H when computing the challenge. We give the NIZK for the case that Sm re-randomizes its key to get a new key after getting the sponsor signature. This allows Sm to use different keys for different applications. Note that in this case, all the signatures of Sm can still be linked to each other, since all of them have been originated from the same key. Algorithm 1: NIZK.Prove Input : Witness w = (skSm , r, r′ ) and statement ′ = x = [∃(skSm , r, r′ ) : P kSm ′ = C.HCom(P kSm , r′ ) ∧ skSm skSm + r′ ∧ (P kSm , r) = C.Com(skSm )], the ′ , m), where m is common input ρ = (P kSm , P kSm an arbitrary message, and the hash function H Output: The proof π 1: Choose two random values a and b in Zp∗ 2: Compute the commitment A = g a ∈ G and B = g b ∈ G ′ , m) 3: Compute the challenge c = H(A, B, P kSm , P kSm 4: Compute the response d1 = a + c × r ′ and d2 = b + c × skSm 5: return π = (A, B, d1 , d2 )

Algorithm 2: NIZK.Verify Input : The proof π = (A, B, d1 , d2 ) and the common ′ , m) input ρ = (P kSm , P kSm Output: bit 0/1 ′ , m) 1: Compute the challenge c = H(A, B, P kSm , P kSm ′ P kSm d1 ? c c ′ d2 ? 2: Check b : g = A × ( P k = B × P kSm ) and b : g Sm ′ 3: return b ∧ b

V. A PPLICATION OF SP GS IN SMART ENVIRONMENTS Providing spontaneous join and temporary access to guests while ensuring their privacy is an overlooked problem in smart environments. In existing systems that support guests, the infrastructure management (IM) manages the join and access of the guests by dedicated guest accounts that are created ahead of time for all of them (e.g. NIST SP-1800-36 [28], Kerberos). These accounts are protected by guest username and passwords that are either same for all guests which allows the guests to be anonymous but their access to the resources would be limited, or they have to contact IM to get customized guest accounts which will reveal their identity to the system. These approaches are not suitable for smart environments because of their rigidity and lack of security and privacy. We look into the problem of providing privacy preserving temporary guest accesses (spontaneously) in a smart building,

by enabling a host, who is a registered entity and knows the guest, as a mediator to enroll the guest into the system. This scenario models many real-life settings including visitors to smart condos, work environments (such as universities and corporations), hospitals, factories, etc. We design an anonymous guest access token, called AGAT, using a SPGS signature scheme that allows a host to act as a sponsor and enroll a guest spontaneously to the smart building. AGAT allows the guest to show its association to a host while the identity of the guest and host (and hence their relation) remains anonymous. We propose k-AGAT that allows host linkability and guest linkability; the host linkability is needed to bound the number of guest accesses per host to at most k (enforcing rate limit policy), and guest linkability is needed to trace the guest accesses to protect the system from the misbehaving guests who are second level members enrolled without contacting IM. Additionally, k-AGAT allows IM to open the tokens of misbehaving guests and identify the host who has enrolled the guest into the system to make the host accountable for their actions. Host can further help to identify the misbehaving guest. Furthermore, a k-AGAT token allows the host and environment both enforce policies on the guests, that is, the token issued by host also embeds some information about the guest access, such as duration of access or expiry time of token, that will be checked and enforced by the verifier (i.e., the environment). We note that alternative naive approaches such as providing guest certificates or simply signed guest tokens by host do not comply with our design goals. Certificates require registration and contacting certificate authorities which can become a complex and prolonged process. Also, the simple signed tokens by hosts do not allow host privacy, accountability, and bounded guest access. In the following, we give a system and threat model for guest accesses in a smart building and define our security requirements and design goals. We then propose k-AGAT that is used as the main building block to enable the guests join the smart building and get temporary access to the building resources. A. System and threat model We consider a smart building consisting of hosts equipped with smart devices such as mobile phones and computers, and a building with shared resources such as CCTV cameras, lightings, buzzers, printers, and so on. We consider a centralized architecture in which the smart building has a infrastructure management system IM consisting of: (i) Registration authority RA that registers the hosts and performs the authentication tasks. RA also acts as a token authority for k-AGAT . (ii) Access management authority (AA) which implements and enforces the access control mechanism; it checks and controls the hosts and guests accesses. AA also acts as the verifier for k-AGAT . We assume that each resource is either capable of performing cryptographic operations, for example for verifying the tokens, or there exists an edge device that manages the resource accesses. Our goal is to enable

the guests (visitors to buildings) to get spontaneous privacypreserving temporary access to the building shared resources through hosts. Threat model. We assume the guest and host mutually trust each other in the sense that the host takes the responsibility of guest enrollment and enabling their resource accesses. However, with respect to the IM, the guest and host may deviate from the protocol arbitrarily and collude to disrupt with the normal operation of building. We assume RA is trusted, but AA is semi-honest and wants to learn the about the host and guest identities, their accesses, an their relations. Security requirements and design goals. We consider the following properties and design goals: • Security: Only eligible users (hosts and guests) can join and get access to the available resources temporary. • Privacy: AA do not learn the identities and relation of honest guests and hosts, and therefore it cannot link the access profiles to a specific host or guest identity. • Accountability: The identity of the host who sponsors a misbehaving guest can be revealed. • Zero-touch enrollment: The guests can join and get access to building shared resources spontaneously, without any required set-up or registration with IM . • Collaborative policy enforcement: Both the IM and host can enforce their policy preferences on the guest accesses including bounded guest accesses. • Efficiency: The performance including the run time and storage size of the hosts, and guests are reasonable for real-world scenarios. B. k-times Anonymous Guest Access Token (k-AGAT) k-AGAT allows a host H to enroll with a Token Authority T A, and generate a token for a guest G (i.e. an unregistered entity in the system), such that a verifier V who knows the system parameters can verify the guest token without learning the actual identity of the host, the guest, and their relation. In k-AGAT hosts can dictate their policy preferences as part of the token content m including the token issuance and expiry time. Guests present the tokens to the verifiers such that tokens show the guest association with a valid host, and tokens can be linked together an counted by the verifier V . This counting allows the verifier bound the number og guest accesses per host. In the case of any misbehavior of the host or guest, the token can be traced back to the host, by the T A, who can further help to identify the guest. Entities. k-AGAT consists of the following entities: – Token authority (TA) is a trusted entity in the system who runs the set up and enrolls the hosts. It can also open the tokens and identify the host issuer in case of misbehavior. – Host (H) is a registered entity in the system who can issue tokens to guests while remaining anonymous. We assume, upon enrollment, each host receives a private (and public) key. – Guest (G) is an unregistered entity in the system which is only known to the host and it wants to get temporary access to the system and use its services. Guest and host mutually trust each other.

– Verifier (V) is a registered entity in the system who is known by the T A and it receives the system public parameters, and checks the validity of the tokens. In our setting, only the verifier who is chosen by the host can verify the validity of a guest token, but in general the tokens can be publicly verifiable. We note that the host and guest are not trusted with respect to the system, they may deviate arbitrarily and collude with each other. Additionally, we assume the verifier is semi-honest and wants to learn the host and guests identities, and their relations. In the following, we give the security requirements and the k-AGAT construction. The formal definitions and descriptions are given in Appendix A. Security requirements A k-AGAT scheme has the following properties: correctness, unforgeability, anonymity, and traceability. • Correctness ensures that AGAT token generation is correct, if a token that is generated by an honest host (within the k bound) and presented by the honest guest to the verifier will pass the verification. • Unforgeability ensures that no one can issue a token on behalf of an honest host without knowing their private keys. Additionally, it captures the fact that the adversary cannot generate more than k valid tokens that are accepted by the verifier. • Anonymity ensures that the identity of the host, guest, and their relation cannot be learned by the verifier. We define this property as below: given two guest identities G0 and G1 and two host identities H0 and H1 , the probability of linking the guests to hosts is negligible. Note that this definition is strong and implies both the guest anonymity and host anonymity since an adversary who can distinguish either G0 from G1 , or H0 from H1 by seeing the issued and presented tokens, can also distinguish the identity of the host and guest from the challenged token, and find the the guest-host relation. The anonymity definition does not imply host unlinkability and guest unlinkability. This is intentional since (i) the tokens issued by the same host should be linked together in order to bound the tokens originated from the same host, and (ii) the guest is not trusted and we want to allow the verifier to trace its access behavior without knowing their identities and their relation with any given host. • Traceability protects the system by allowing the token authority T A to reveal the actual identity of the host H who has issued the guest token. Our construction is generic and uses the generic SP GS construction proposed in Section IV-A, and a IND-CPA secure public key encryption scheme E as its building blocks (please see Section III and IV for their algorithms and security properties). In the nutshell, in our construction of k-AGAT , host act as the sponsor and guest acts as the sponsored-member of a SPGS scheme. Host uses a sponsor signature to sign the public key of the guest (which is a commitment to a random value

that is used as a private key by guest) and the token contents, and issues a guest token. The guest uses a sponsored-member signature and transforms the token to a new one by proving that it knows the private key. The important part in our scheme is that, SPGS provides complete anonymity that captures unlinkability for sponsors, but k-AGAT does not ensure complete anonymity, it allows host linkability. For this, we follow the approach of [15] and use pseudonyms together with our sponsored group signature to relax the anonymity of SPGS. Pseudonyms are generated by T A and shared with hosts during their enrollment. Host will encrypt their pseudonym when it issues a token. The verifier can decrypt the pseudonym ciphertext and link the tokens originated from the same host (without learning the host identity). The scheme is summarized as below (see Appendix A for details and formal description): Setup phase. T A maintains a pseudonym list Lw that initially consists of dummy values. It also generates the SPGS private and public parameters. • Host enrollment When a host joins, T A and host run the SPGS join algorithm for a sponsor, at the end of which host receives valid private and public keys. T A chooses a pseudonym wh for the host and adds it to the list Lw . After a batch of pseudonyms are added, it shares the list with the the verifier. Verifier do not see the link between pseudonyms and identity of the hosts and only use the list Lw to check the validity of the pseudonyms. • Guest token issuance. To issue a token, the host and guest interact according to the SPGS join algorithm for a sponsored-member which outputs a private and public key to the guest. Additionally, host decides on the token contents m such as expiry time, and signs m (that includes the public key of the guest) using the sponsor signature algorithm of SPGS. It also encrypts their pseudonym wh using the public key of the verifier. Note that to bind the SPGS signature and the pseudonym ciphertext and prevent mix and match attacks, the host will choose a random value r and use it twice: (i) it concatenates r with m and generate the sponsor signature on m||r, and (ii) encrypts wh ||r. Both the sponsor signature and the pseudonym ciphertext will be included in the guest token. • Guest token presentation. The guest will receive the guest token and transform the token to a new one by signing the token using the sponsored-member signature, and present the transformed token to the verifier. • Guest token verification. The verifier will verify the SPGS signatures, decrypts the ciphertext and checks whether wh is among the valid pseudonyms wh ∈ Lw and if it is valid it keeps a counter for wh to count the number of issued tokens by the same host. If the guest tokens originated from wh exceeds the limit k (or the value less than k determined by the host within the token) the verifier rejects the token.

•

Although to relax the anonymity one can use a different approach and let the hosts commit to their pseudonyms and

prove their validity to the verifier through NIZK2 without sharing the list Lw with the verifier [15], we chose to share Lw with the verifier directly for checking the validity of pseudonyms to keep our construction simple and efficient. We show that as long as the verifier is trusted this approach ensures a secure k-AGAT construction with the tradeoff that the pseudonyms should be added in batches and this can create a delay between when the host enrollment and when it can issue valid tokens. Since we do not have any restriction on hosts’ enrollment time this approach is reasonable. Concrete construction. To instantiate our construction, we use the SPGS concrete construction of section IV-C. For the encryption scheme E, we use the EC-based Elgamal encryption scheme. Security analysis. Below we give a theorem and a proof sketch for our construction of k-AGAT . Theorem V.1. Our k-AGAT construction ensures correctness, unforgeability, b1n -anonymity, and traceability assuming SP GS satisfies correctness, non-frameability, sponsor anonymity, sponsored-member privacy, sponsor traceability, and E is an IND-CPA secure encryption scheme. Proof sketch. We omit the proof due to the space and just give the informal arguments. Correctness is satisfied due to the correctness guarantee of the sponsored group signature scheme SP GS and the public key encryption scheme E. Unforgeability follows from (i) the non-frameability of the sponsored group signature scheme which prevents the adversary from generating a valid sponsor signature σ for a guest token without knowing the private key of the host, (ii) the randomness r used in both signature σ and ciphertext C prevents the adversary from mixing and matching different tokens to form a new token. Anonymity follows from (i) anonymity of the sponsored group signature scheme which does not let the verifier learn whether the sponsor signature σ in the token has been generated by host H0 or H1 , (ii) sponsored-member privacy of SPGS which prevents the verifier to learn the identity of the guest from the sponsored-member signature used in the token, (iii) the IND-CPA security of E which does let the verifier to learn the pseudonym of the host, (iv) the fact that the registered pseudonyms are independent of the real identity of the hosts, (v) pseudonyms are added to Lw in batches of size bn and the verifier who controls the join of hosts and sees the latest list Lw cannot guess the pseudonym of an honest host with probability greater than b1n . Issuer traceability is ensured due to the traceability of SPGS. C. Secure guest access protocol Our protocol uses the k-AGAT construction presented in previous section directly which will be integrated to ACEOAuth [29] as below. • The host enrolls with IM (more precisely RA) and receives the private and public parameters of the system 2 This approach is publicly verifiable and one can use it to relax the assumption about the verifier’s trustworthiness.

and installs the required software and configurations by authenticating itself using the sponsor signature. • When a guest visits the building, the host provides the url to install the required software and guest configuration which are stored in a public repository. The host then generates a k-AGAT guest token by interacting with the guest. • The guest sends its access request to AA (which is the authorization server in ACE-OAuth) together with the transformed guest token it has received from the host. • AA checks the access rights of the guest and also the access policy preferences dictated in the token by the host, such as the expiry time and the access limit. If the guest token is verified, the guest receives an access token (a signed message by the service provider, also called a proof of possession (PoP)), that it can send to the resource or edge device to get access to the resource. Note that until the guest token is valid the guest can send requests to AA. Depending on the access requests and the resources availability, the PoP can have different and possibly shorter expiry time. Security and privacy analysis. Below, we give an informal analysis of the security and privacy requirements of the scheme. Security: Only eligible hosts who have registered with the RA and guest who are associated with a registered host can access the resources. This is because of nonframeability of sponsor signatures in SPGS (that is used for host authetication), and due to the unforgeability of k-AGAT , which ensures that only registered hosts who are first-level members of the building can generate valid tokens for guests (that will be accepted). • Privacy: AA do not learn the identities and relation of honest guests and hosts due to the anonymity of k-AGAT and sponsor anonymity of SPGS. • Accountability: The traceability of k-AGAT ensures that the identity of the host associated with the misbehaving guest is revealed. • Zero-touch enrollment: The guests join through the host, and they do not need to interact with IM for registration. Also, they do not require any trusted setup. • Collaborative policy enforcement: Host can encode its preferences of access rights as part of the token content, which will be checked by AA. In general, AA determines the guest access rights and also the policies that host can choose from; for example the validity duration of the token, where AA can determine the maximum duration, and host can choose the exact duration. Additionally, both host and AA can limit the usage of the token. The guest can use the token at most k times (the host can determine a value lower than k when issuing the token to the guest). • Efficiency: See the following section for implementation and evaluation results. •

TABLE I C OMPUTATION AND S TORAGE C OST IN S ETUP P HASE Scheme Scheme w/o Privacy

Our Scheme

Role Guest Hosta IMb Guest Hostc IMd

Computation (ms) 0.359 1.052 0.389 1.213

Storage (bytes) 138 368 672 14438

TABLE II C OMPUTATION AND S TORAGE C OST IN GUEST ACCESS PHASE Scheme Scheme w/o Privacy

Our Scheme

a

a

b

b

E.KeyGen DS.KeyGen (×2) c E.KeyGen, E.Dec d E.KeyGen, DS.KeyGen (×2), GS.KeyGen, GS.Join, E.Enc, BN.Setup

D. Implementation and evaluation In the following, we give the implementation details, and evaluation results. The source codes are publicly available in our Github repository (https://github.com/shwdsun/GuestOnBoarding). Objective. Our goal is to measure the performance and overhead introduced by the cryptographic primitives used in the guest access protocol compared to a non-private baseline scheme. The baseline scheme uses a regular digital signature to generate a token for the guest instead of using the k-AGAT token of Section V-B. Specifically, we evaluate the runtime and storage for host, guest, and IM . Implementation Setup. Our experiments were conducted on Ubuntu Linux 6.11.0-24-generic with Python 3.10.17 (conda-forge). The test machine features a 13th-generation Intel Core i5-13600K processor (14 cores, 20 threads, 3.0 GHz base frequency, 24 MB L3 cache) with 32 GB RAM. All implementations used Python 3.10.17 with the following cryptographic libraries: Charm-crypto 0.50 [30], PBC 0.5.14, GMP 6.3.0, and OpenSSL 3.3.2, managed in a dedicated Conda environment Implementation Details. our cryptographic components integrates schemes from Charm-Crypto [30]( e.g., BBS, accessed through wrappers) with our own standalone implementations (i.e. ElGamal and NIZK). For group signatures, we implemented the BBS scheme [27] with MNT224 curve which requires the number of hosts to be predetermined - we set this to 100 for our implementation. The EC-ElGamal encryption implements 28-byte message padding for secure encoding. We use ECDSA for a regular signature scheme. which implements a standard signature scheme with state management. For N IZK, we implemented Schnorr NIZK scheme for discrete log with Fiat-Shamir transform (see Section IV-C. All primitives (except BBS) are implemented over secp256k1 curve. Protocol Performance Evaluation. We evaluate the computational and storage cost. Note that all byte measurements use library serialization methods, resulting in larger sizes than theoretical values due to encoding overhead. Our evaluation reveals the performance trade-offs between privacy and efficiency across both setup and on-boarding phases. Setup Phase: As shown in Table I, the setup phase introduces minimal computational overhead but significant storage requirements for IM. The host’s overhead is related to BBS

Role Guesta Hostb IMc Guestd Hoste IMf

Computation (ms) 0.730 1.410 2.802 0.733 12.347 17.378

Storage (bytes) 230 1049 362 230 1605 412

Randomize key, NIZK.Prove DS.KeyGen, DS.Sign DS.Verify, DS.Sign, NIZK.Verify d Randomize key, NIZK.Prove e DS.KeyGen, GS.Sign, E.Enc f GS.Verify, E.Dec, DS.Sign, NIZK.Verify c

group keys and pseudonyms. The IM’s storage overhead is particularly pronounced due to maintaining member keys for all hosts in the system. Notably, both the setup time and storage for the BBS scheme exhibit approximately linear growth with the number of hosts. Guest access phase: Table II demonstrates the performance impact of our proposed scheme. While guest devices experience minimal overhead, both host and IM face significant computational costs due to BBS group signature operations and ElGamal encryption/decryption. In terms of storage, the host requires additional space for the larger BBS signature and group public key, while IM and the guest storage requirements remain relatively modest. Despite these overheads, the costs remain reasonable for practical deployments. The millisecond-scale computation times are negligible compared to typical network latencies, and the kilobyte-scale storage are well within modern smart device capabilities. VI. C ONCLUSION We proposed sponsored group signature (SPGS), a variation of a group signature that supports two levels of signers. The level 1 signers (sponsors) can enroll level 2 signers (sponsoredmembers) while allowing both members sign anonymously and ensure their signatures remain unforgeable. In SPGS the sponsored-signature can be linked together and in case of misbehavior the identity of the sponsor can be revealed by the group manager. We formalized SPGS using the game-based model and proposed a generic construction using a commitment, a partially dynamic group signature, and a knowledge sound NIZK scheme. We also showed the application of SPGS in constructing a guest access token, k-AGAT , for a smart building scenario in which a host provides spontaneous privacy preserving temporary access to its guests to access the building shared resources. The k-AGAT construction k-AGAT allows the verifier to bound the number of guest tokens that can be presented by the guest of the same host. We proposed a secure guest access protocol using k-AGAT and showed its efficiency by providing a proof-of-concept implementation of its cryptographic components. Extending our work to a multibuilding scenario and different levels of guests is an interesting future work.

R EFERENCES [1] D. Chaum and E. Van Heyst, “Group signatures,” in Workshop on the Theory and Application of of Cryptographic Techniques. Springer, 1991, pp. 257–265. [2] H. Zheng, Q. Wu, B. Qin, L. Zhong, S. He, and J. Liu, “Linkable group signature for auditing anonymous communication,” in Australasian Conference on Information Security and Privacy. Springer, 2018, pp. 304–321. [3] J. K. Liu, V. K. Wei, and D. S. Wong, “Linkable spontaneous anonymous group signature for ad hoc groups,” in Australasian Conference on Information Security and Privacy. Springer, 2004, pp. 325–335. [4] J. Bootle, A. Cerulli, P. Chaidos, E. Ghadafi, and J. Groth, “Foundations of fully dynamic group signatures,” in Int. Conference on Applied Cryptography and Network Security. Springer, 2016, pp. 117–136. [5] M. Buser, J. K. Liu, R. Steinfeld, A. Sakzad, and S.-F. Sun, “Dgm: Ad ynamic and revocable g roup m erkle signature,” in European Symposium on Research in Computer Security. Springer, 2019, pp. 194–214. [6] M. Bellare, H. Shi, and C. Zhang, “Foundations of group signatures: The case of dynamic groups,” in Cryptographers’ track at the RSA conference. Springer, 2005, pp. 136–153. [7] L. Chen and T. P. Pedersen, “New group signature schemes,” in Workshop on the Theory and Application of of Cryptographic Techniques. Springer, 1994, pp. 171–181. [8] S. D. Gordon, J. Katz, and V. Vaikuntanathan, “A group signature scheme from lattice assumptions,” in International conference on the theory and application of cryptology and information security. Springer, 2010, pp. 395–412. [9] J. Camenisch and M. Stadler, “Efficient group signature schemes for large groups,” in Annual international cryptology conference. Springer, 1997, pp. 410–424. [10] J. Camenisch and M. Michels, “A group signature scheme with improved efficiency,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 1998, pp. 160–174. [11] M. Abhilash and B. Amberker, “Efficient group signature scheme using lattices,” International Journal of Information Technology, vol. 14, no. 4, pp. 1845–1854, 2022. [12] Q. Alamélou, O. Blazy, S. Cauchie, and P. Gaborit, “A code-based group signature scheme,” Designs, Codes and Cryptography, vol. 82, no. 1, pp. 469–493, 2017. [13] W. Beullens, S. Dobson, S. Katsumata, Y.-F. Lai, and F. Pintore, “Group signatures and more from isogenies and lattices: Generic, simple, and efficient,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2022, pp. 95–126. [14] M. Fadavi, S. Karati, A. Erfanian, and R. Safavi-Naini, “Dgmt: A fully dynamic group signature from symmetric-key primitives,” Cryptography, vol. 9, no. 1, p. 12, 2025. [15] M. Belenkiy, J. Camenisch, M. Chase, M. Kohlweiss, A. Lysyanskaya, and H. Shacham, “Randomizable proofs and delegatable anonymous credentials,” in Advances in Cryptology-CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings. Springer, 2009, pp. 108–125. [16] M. Belenkiy, J. Camenisch, M. Chase, M. Kohlweiss, A. Lysyanskaya, and et al., “Delegatable anonymous credentials,” Cryptology ePrint Archive, 2008. [17] O. Mir, D. Slamanig, B. Bauer, and R. Mayrhofer, “Practical delegatable anonymous credentials from equivalence class signatures,” Proceedings on Privacy Enhancing Technologies, 2023. [18] E. C. Crites and A. Lysyanskaya, “Delegatable anonymous credentials from mercurial signatures,” in Cryptographers’ Track at the RSA Conference. Springer, 2019, pp. 535–555. [19] J. Blömer and J. Bobolz, “Delegatable attribute-based anonymous credentials from dynamically malleable signatures,” in International Conference on Applied Cryptography and Network Security. Springer, 2018, pp. 221–239. [20] P. P. Tsang and V. K. Wei, “Short linkable ring signatures for e-voting, e-cash and attestation,” in International Conference on Information Security Practice and Experience. Springer, 2005, pp. 48–60. [21] J. K. Liu, M. H. Au, W. Susilo, and J. Zhou, “Linkable ring signature with unconditional anonymity,” IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 1, pp. 157–165, 2013. [22] N. Tran, K. Nguyen, D. Liu, J. Pieprzyk, and W. Susilo, “Manytime linkable ring signatures,” in International Conference on Provable Security. Springer, 2025, pp. 3–22.

[23] M. Kohlweiss and I. Miers, “Accountable tracing signatures,” Cryptology ePrint Archive, 2014. [24] B. Libert, K. Nguyen, T. Peters, and M. Yung, “Bifurcated signatures: folding the accountability vs. anonymity dilemma into a single private signing scheme,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2021, pp. 521– 552. [25] A. Kiayias, Y. Tsiounis, and M. Yung, “Traceable signatures,” in International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2004, pp. 571–589. [26] A. Boldyreva, A. Palacio, and B. Warinschi, “Secure proxy signature schemes for delegation of signing rights,” Journal of Cryptology, vol. 25, no. 1, pp. 57–115, 2012. [27] D. Boneh, X. Boyen, and H. Shacham, “Short group signatures,” in Annual int. cryptology conference. Springer, 2004, pp. 41–55. [28] M. Fagan, J. Marron, P. Watrobski, M. Souppaya, W. Barker, C. Deane, J. Klosterman, C. Rearick, B. Mulugeta, S. Symington et al., “Trusted internet of things (iot) device network-layer onboarding and lifecycle management: Enhancing internet protocol-based iot device and network security,” NIST, Tech. Rep., 2023. [29] E. Blog, “Ace-oauth – a new standard for lightweight authorization and access control,” 2025. [Online]. Available: https://www.ericsson.com/ en/blog/2023/7/ace-oauth-standard-for-lightweight-authorization [30] J. H. U. ISI. (2018) Charm-crypto documentation. [Online]. Available: https://jhuisi.github.io/charm/ [31] J. Bootle, A. Cerulli, P. Chaidos, E. Ghadafi, and J. Groth, “Foundations of fully dynamic group signatures,” Journal of Cryptology, vol. 33, no. 4, pp. 1822–1870, 2020. [32] F. Benhamouda, M. Raykova, and K. Seth, “Anonymous counting tokens,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2023, pp. 245–278. [33] D. Bernhard, O. Pereira, and B. Warinschi, “How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2012, pp. 626–643. [34] M. Chase and A. Lysyanskaya, “On signatures of knowledge,” in Annual International Cryptology Conference. Springer, 2006, pp. 78–96. [35] A. De Santis and G. Persiano, “Zero-knowledge proofs of knowledge without interaction,” in 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 1992, pp. 427–436. [36] A. De Santis, G. Di Crescenzo, and G. Persiano, “Necessary and sufficient assumptions for non-interactive zero-knowledge proofs of knowledge for all np relations,” in International Colloquium on Automata, Languages, and Programming. Springer, 2000, pp. 451–462.

A PPENDIX Bootle et al. [31] proposed a framework to model and define the security requirements of a dynamic group signature scheme. We adapt their model to our setting and define the model and security properties that are required for a group signature scheme that is used in our SPGS generic construction. Also, these definitions are used as a basis to define the SPGS security model. The partially dynamic group signature GS composed of the following algorithms: λ • GS.Setup(1 , setpp) = (pp, msk), is run by M and it takes the security parameter λ and set up parameters SP , and outputs the public parameters pp and the manager’s secret key msk. • GS.Join(idu , paramM ) is an interactive algorithm that is run between a M and the user idu who desire to join the group (we assume all interactions takes place over a secure channel similar to [5]). • GS.Sign(m, paramu ) = σ, this algorithm is run by the member idu with its private parameters paramu , and outputs a valid anonymous signature σ.

GS.V erif y(m, σ, pp) = 0/1, is run by the verifier and takes as input the message m, the signature σ, and the public parameters of the system pp, and outputs 1 if the signature is valid, or 0 otherwise. • GS.Open(msk, σ) = idu , is run by M to reveal the identity of the signer of σ. We consider that the group manager M act as both issuing authority and opening authority, and is assumed to be partially corrupted (i.e., its private state can be leaked). Also, we do not consider the Judge algorithm since M follows the protocol correctly and traces the signatures if needed. Additionally, we consider that the group is partially dynamic (the entities can join at any time). Security requirements. We consider that GS ensures the following security requirements: • Correctness ensures that if an honest member joins and generates a signature, their signature will be verified. In the partially dynamic setting where the members can join at any time, these two conditions should hold for all honest members under any schedule under which the members join the group. Therefore, to formalize correctness we consider an adversary who can control users’ joining process and chooses the messages and the identity of the signers. We require that for any messages and identities that the adversary chooses, the signatures generated can be verified correctly. • Non-frameability ensures that no one can frame an honest member; that is, even if group members collude (all except at least one member) and even the group manager’s private state is leaked, they cannot generate a valid signature that is opened to the honest member who has not generated the signature. This notion of non-frameability implies unforgeability of the group signature, since the adversary can corrupt and learn all keys except for the honest member that it generates the signature for. • Anonymity states that no one can distinguish the member who has generated a given group signature from idu0 and idu1 better than a random guess even if they have seen the output of the Open algorithm for some signatures. M is considered trusted for anonymity as M can always open the signatures and learn the identity of the sponsors. This definition captures unlinkability as well. • Traceability protects the group manager by ensuring that any valid signature will be opened to the identity of a group member. This is achieved even if the group manager’s private state is leaked (i.e., M is considered partially corrupted). Oracles. To formally define the security requirements, we use the following oracles (given in Figure 3). • AddHU(idu ): This oracle allows the adversary to add honest users through honest execution of GS.Join without learning their private parameters. • CorrU(idu ) allows the adversary to corrupt the users and learn both their communication transcript when they •

run GS.Join algorithm honestly and their private parameters (including signing keys). • AddCU(idu ): This oracle allows the adversary to add corrupted users to the group. The adversary can deviate from the GS.Join protocol and send arbitrary messages to M see its output outM . • AChalb (pp, m, idu0 , idu1 ): This is a left-right oracle for defining anonymity. It takes as input the group public parameters pp, a message m, and two honest users identities idu0 and idu1 , and returns a group signature on the message m using the private parameters of paramub for b ← {0, 1}. The adversary can call this oracle once. • SignHU(m, paramu ) This oracle is used by the adversary to obtain signatures for an honest user whose private parameters are not known by the adversary. It returns a signature σ on the message m using the GS.Sign algorithm with the private parameters of idu . • Open(msk, m, σ, pp) returns the identity of the sponsor idu who has generated the group signature σ. The oracle cannot be called on a signature obtained from the AChalb . • CorrM() returns the private parameters of the manager M. AddHU(idu ) • If N > Nmax Return ⊥ • Update H ∪ {idu } and N = N + 1 • paramu ← GS.Join(idu , paramM ) • Let the Join transcript is stored in trscJoinu • Store QHU = QHU ∪ (idu , trscJoinu , paramu , outM ) • Return pp CorrU(idu ) • If idu ∈ / H Return ⊥ • Update C ∪ {idu } and H = H\{idu } • Retrieve (idu , trscJoinu , paramu , outM ) from QHU • Return trscJoinidu , paramu , and outM AddCU(idu ) • If idu ∈ H Return ⊥ • Update C ∪ idu • paramu ← GS.Join(idu , paramM ) • Return paramu and outM AChalb (pp, m, idu0 , idu1 ) • If idu0 , idu1 ∈ / H Return ⊥ • σb ← GS.Sign(m, paramub ) • If GS.V erif y(m, σb , pp) = 0 Return ⊥ • Update QAChal ∪ (m, σb ) • Return σb SignHU(m, paramu ) • If paramu =⊥ Return ⊥ • σ ← GS.Sign(m, paramu ) • Update QSign ∪ (m, σ) • Return σ Open(msk, m, σ, pp) • If (m, σ) ∈ QSign ∪ QAChal Return ⊥ • If GS.V erif y(m, σ, pp) = 0 Return ⊥ • Return GS.Open(msk, σ) CorrM() • Return paramM Fig. 3. Oracles used in experiments

Definition A.1. For any security parameter λ ∈ N and for any

PPT adversary A, we say that SP GS provides: 1) Correctness if there exists a negligible function ν1 such Corr that AdvGS,A (λ) = P r[ExpCorr GS,A (λ) = 1] ≥ 1 − ν1 (λ) 2) Non-frameability if there exists a negligible N on−F rame function ν2 such that AdvGS,A (λ) = N on−F rame P r[ExpGS,A (λ) = 1] ≤ ν2 (λ) 3) Anonymity if there exists a negligible function ν3 such 1 Anon that AdvGS,A (λ) = P r[ExpAnon−b GS,A (λ) = 1] ≤ 2 +ν3 (λ) 4)

Traceability if there exists a negligible function ν4 T race race such that AdvGS,A (λ) = P r[ExpTGS,A (λ) = 1] ≤ ν4 (λ)

N on−F rame T race where ExpCorr , ExpAnon GS,A , ExpGS,A GS,A , ExpGS,A , are defined in Figure 4.

ExpCorr GS,A (pp, msk) ← GS.Setup(λ, setpp), N = 0 (m, idu ) ← AAddHU,CorrU,AddCU,CorrM (pp) If idu ∈ / H Return 0 σ ← GS.Sign(m, paramu ) If GS.V erif y(m, σ, pp) = 0 Return 0 Return 1 on−F rame ExpN GS,A (pp, msk) ← GS.Setup(λ, setpp), N = 0, QSign = ∅ (idu , m, σ) ← AAddHU,CorrM,SignHU (pp) If idu ∈ / H Return 0 If GS.V erif y(m, σ, pp) = 0 Return 0 If (m, σ) ∈ QSign Return 0 ? Return GS.Open(msk, σ) = idu

ExpAnon−b GS,A (pp, msk) ← GS.Setup(λ, setpp), N = 0, QAChal = ∅ b′ ← AAddHU,CorrU,AddCU,Open,AChalb (pp) If b′ ̸= b Return 0 Return 1 race ExpTGS,A (pp, msk) ← GS.Setup(λ, setpp), N = 0 (m, σ) ← AAddHU,CorrU,AddCU,Open,CorrM (pp) If GS.V erif y(m, σ, pp) = 0 Return 0 ? Return GS.Open(msk, σ) =⊥

Fig. 4. Security games of group signature GS

NIZK allows a prover who knows a witness w for a statement x can convince a verifier that (w, x) ∈ R, without revealing the witness w, where R is a relation (R ⊂ L) defined in language L. NIZK consists of the following algorithms: • N IZK.Setup(R) which takes the relation R (which implicitly defines the security parameter λ) and outputs the common reference string crs. • N IZK.P rove(crs, ρ, x, w) which takes the common reference string crs, the common input ρ, the statement x that is being proven about ρ, and the witness w as input and outputs the proof π. • N IZK.V erif y(crs, π, ρ, x) receives the common reference string crs, the proof π, the common input ρ, and

the statement being proven as input and outputs 1 if the proof is verified and 0 otherwise. Security requirements. We consider a NIZK that ensures perfect completeness, computational zero-knowledge, and computational knowledge-soundness properties [32]. Perfect completeness ensures that an honestly generated proof π for a true statement (w, x) ∈ R will pass the verification. That is, for all relations R and (w, x) ∈ R, for all crs ← N IZK.Setup(R), and honestly generated proofs π ← N IZK.P rove(crs, ρ, x, w), the verification passes: 1 ← N IZK.V erif y(crs, π, ρ, x) Computational zero-knowledge ensures that the proof π does not reveal any additional information about the witness w other than the fact that the statement is correct, i.e., (w, x) ∈ R. Formally, this means that for all relations R and all PPT adversaries A, there exists a simulator Sim that outputs the public parameters and a trapdoor td which allows to verify the proofs without knowing the witness. 

crs ← N IZK.Setup(R); 1 ← AN IZK.P rove(crs,ρ,x,w) (crs)   (crs, td) ← Sim(R); ≤ ν(λ) Pr 1 ← ASim(td,ρ,x,·) (crs) Pr

 −

Computational Knowledge Soundness ensures that (i) for all relations R and for every PPT adversary A there exists an extractor Extract that can extract a valid witness for every valid proof π that the adversary generates and (ii) the extractorgenerated crs is indistinguishable from an honestly generated crs (this is called set-up indistinguishability). Our definition follows from [32] which removes the access to a simulation oracle in [33], and simplify it by allowing the extractor to select the random coins of the adversary, and allowing the use of a crs. Extractability: (crs, td) ← Extract(R);  r ← rndA ; P r  (x, π) ← A(crs, r) w ← ExtractA (td, x, π, r) ≤ ν(λ) 

 1 ← N IZK.V erif y(crs, π, ρ, x)∧   (w, x) ∈ /R

where rndA is the distribution of random coins of the adversary. Statistical set-up indistinguishability: for arbitrary adversary B (even non-polynomial time)   P r crs ← N IZK.Setup(R) 1 ← B(crs) −   P r (crs, td) ← Extract(R) 1 ← B(crs) ≤ 21 + ν(λ)

SOK allows a signer who knows a valid witness w for a statement x ∈ L, for the N P language L, such that ML (x, w) = accept, and ML is a polynomial time Turing machine, to generate a signature on message m. A signature of knowledge (SOK) should ensure SimExt-security which implies correctness, simulatability and exractability. It was

shown in [34] that using a dense public key cryptosystem3 [35] (which is equivalent to a commitment scheme4 [36]) and a simulation-sound non-interactive zero knowledge proof, one can construct a signature of knowledge for any language L. The sponsored-member signature in our generic construction can be seen as a group signature and a SOK (with weaker security than [34]). One can also use the generic SOK construction of [34], but we note that the SOK of [34] has stronger security properties that is needed for SPGS. Our constructions use minimal security assumptions. Lemma A.1. The sponsored signature linkability of SPGS (defined by ExpSmLink−b SP GS,A ) is equivalent to the signer linkability notion defined for LSAG (the linkable spontaneous anonymous group signature) of [3]. Proof. We argue that the two definitions are equivalent, meaning that if the Liu et al. linkability definition [3] holds, our sponsored-member linkability definition will hold and vice versa. Let’s consider that there is an SPGS scheme which ensures linkability notion as defined by statements (i) and (ii) above. Therefore, there exists a PPT algorithm F that can link the two signatures with high probability. We show that this scheme also ensures the linkability notion of Definition 1.5. To find the advantage of A in ExpSmLink−b SP GS,A , we assume A uses the algorithm F as a subroutine, it sends the messages and signatures received by LChalb to F and outputs b′ = 0 if F outputs 1, and outputs b′ = 1 if F outputs 0. Note that if F can link the two signatures that are issued by the same signer with non-negligible probability (i.e., corresponding to the probability statement i) then if challenger chooses set0 then the probability that F will output 1 will be non-negligible. Also, if F always outputs 0 for the two signatures that are issued by different signers with non-negligible probability (i.e., corresponding to the probability given in statement ii) then if challenger chooses set1 according to our definition then the probability then F will output 0 will be non-negligible. Therefore, the advantage of A is equal to advantage of F which is non-negligible (i.e. 1 − ν(λ)). The reverse side of the statement state that if there is an algorithm A that can win the ExpSmLink−b with nonSP GS,A negligible probability, then there exists an algorithm F that can link the two signatures with non-negligible probability. We use contradiction to prove this statement. Let’s consider that the algorithm F will link the two signatures with only negligible probability, then it is clear that A which uses F 3 A dense public key cryptosystem is a public key cryptosystem consisting of (KeyGen, Enc, Dec) algorithms with two differences: (i) the public key output by the KeyGen algorithms is indistinguishable from a uniform distribution, and (ii) Rather than for all public keys, for only a sufficient set of public keys the security properties hold. 4 An extractable commitment scheme is a commitment scheme that outputs a trapdoor together with system parameters, such that an extractor can extract the committed value using the trapdoor. It ensures extractability in addition to hiding and binding properties. Extractability is defined as follows: there exists an extractor who can extract the value it has been committed knowing the public random string an the auxiliary data.

as a subroutine will succeed with negligible probability which contradicts our assumption. The proof of theorem consists of a set of lemmas, one for each property, that are outlined below. Lemma A.2. Correctness. The construction of SP GS given in Section IV-A achieves correctness, if the group signature GS and commitment C ensure correctness and N IZK ensures completeness. The proof is straightforward. If GS ensures correctness, then the sponsor signature σ will be correct. Also, if the commitment scheme C ensures correctness the the proof π can be constructed correctly for the P KSm . Additionally, the completeness property of the N IZK ensures that any proof generated by the honest parties will be verified. Therefore, the sponsored signature σ ′ will be verified. Lemma A.3. Non-frameability. The construction of SP GS given in Section IV-A achieves non-frameability, if N IZK ensures knowledge soundness, the commitment C is binding, and the group signature GS is non-frameable. Depending on attr, We consider two cases: (i) SP-nonframeability, where attr = Sp, and the adversary A in on−F rame game ExpN after issuing oracle queries outputs SP GS,A (Sp, idSp , m, σSp ), and (ii) Sm-non-frameability, where on−F rame attr = Sm, and the adversary A in game ExpN SP GS,A after issuing oracle queries outputs (Sm, idSm , m, σSm ). (i) Sp-non-frameability. In this game, the adversary A can only issue queries to SignHU (Sp, ·, ·) oracle and at the end it wins if it outputs a valid sponsor signature for an honest member which can be opened to the sponsor correctly. The sponsor signature σSp in our scheme is generated through a group signature GS, and thus the Sp-non-frameability of SP GS directly reduces to the non-frameability of GS. In another words, we show that if SP GS does not ensure Spnon-frameability then we can construct an adversary A who can break the non-frameability of GS. Let’s consider that there exists an adversary B who can output (m, σ) that opens to on−f rame idSp in ExpN with non-negligible probability. Then SP GS,B A can use B as a subroutine to break the non-frameability of GS. A will answer the AddHU (Sp, ·), CorrM , and on−f rame SignHU (Sp, ·, ·) queries of B in ExpN experiment SP GS,B by using AddHU , CorrM , and SignHU oracles of GS on−f rame (see ExpN in Appendix A). When B outputs GS,A (Sp, m, σ), A outputs (m, σ). The success probability of A is the same as the success probability of B. This contradicts the assumption that GS is non-frameable, and hence we conclude that SP GS ensures Sp-non-frameability. (ii) Sm-non-frameability. In this game, the adversary A can issue queries to both SignHU (Sp, ·, ·) and SignHU (Sm, ·, ·) oracles, and it wins if it can output a valid signature σSm = σ ∗ such that it is opened to the actual sponsor. We prove Sm-nonframeability using the hybrid game as below:

Hyb0 . This game corresponds to the non-frameability game of SP GS. Hyb1 . This game is similar to the previous one except that for any query to SignHU oracle, N IZK set up is done by the extractor from the knowledge soundness. Due to the set up indistinguishability from knowledge soundness this game is indistinguishable from the previous game. Hyb2 . This game is similar to the previous one except that after the adversary outputs a forgery (m∗ , σ ∗ ) where ∗ σ ∗ = (σ, P kSm , π), the game aborts if the extractor aborts and cannot extract a valid witness from π. This game is computationally indistinguishable from the previous game under the extractability of the N IZK (the abort event happens only with negligible probability). Hyb3 . This game is similar to the previous one except that the game aborts if the extracted witness does not match ∗ the forgery σ ∗ = (σ, P kSm , π). Let’s consider that ∗ the witness is (skSm , r). Therefore, we should have ∗ ∗ (P kSm , r) = C.Com(skSm ). This game is indistinguishable from the previous game since C ensures binding property, and the probability that any of these checks fails is negligible. Additionally, if any of these statements are not satisfied then the proof π will not be verified and the extractor aborts. ∗ Hyb4 . Let’s consider the forgery is σ ∗ = (σ, P kSm , π) on ∗ message m . This game is similar to the previous one ex∗ , ·)) ∈ / QSign . cept that the game aborts if (m∗ , (σ, P kSm This game is indistinguishable from the previous game since if this is the case then σ should have been forged, which only happens with negligible probability due to the non-frameability of GS. We can see that assuming the N IZK ensures knowledgesoundness, and commitment C is binding, we can reduce the Sm-non-frameability of the SP GS to the last hybrid game. ∗ , π) on This shows that if A outputs a forgery σ ∗ = (σ, P kSm m then we can construct an attacker B which can use the A as subroutine to output a valid forgery for the group signature σ on m = P k ∗ Sm. This concludes the proof. Lemma A.4. Sponsor anonymity. The construction of SP GS given in Section IV-A achieves sponsor anonymity, if GS ensures anonymity for the signer. We give the hybrid game as below: Hyb0 . This game corresponds to the sponsor anonymity game of SP GS. Hyb1 . This game is similar to the previous one except that for any choice of b ∈ {0, 1}, σb′ is generated by GS using private parameters of a random entity id′Sp . This is indistinguishable from the previous game since GS satisfies anonymity. We can see that the last game does not have anything related to the identity of the actual sponsor idSp and hence it is indistinguishable from the random except with a negligible probability. This concludes the proof. Lemma A.5. Sponsor traceability. The construction of

SP GS given in Section IV-A achieves sponsor traceability, if the group signature GS ensures traceability. We show that if GS ensures traceability, then our construction of SP GS ensures traceability. Note that Open algorithm only uses the sponsor signature (computed through GS) to identify the sponsor identity. Let’s assume that SP GS does not ensure sponsor traceability and there exists an adversary B that can output (SP, m, σ) such that SP GS.OpenSp (msk, σ) =⊥, or outputs (Sm, mσ) such that SP GS.OpenSm (msk, σ) =⊥ with non-negligible probability. Then we can construct the adversary A who can use B as a subroutine to break the traceability of GS. A will respond to the AddHU (Sp, ·),CorrU (Sp, ·), AddCU (Sp, ·), Open(Sp, ·) and CorrM queries of B in race ExpSpT SP GS,B using the AddHU , CorrU , AddCU , Open race and CorrM oracles of GS (see ExpTGS,A in Appendix A) respectively. When B outputs (Sp, m, σ), A outputs (m, σ). If B outputs (Sm, m, σ), A parses σ = (σ ′ , m, m′ , π), and outputs (m, σ ′ ). The success probability of A in this game is the same as the success probability of B. This contradicts the assumption that GS ensures traceability, and hence we conclude that SPGS ensures sponsor traceability. Lemma A.6. Sponsored-member privacy. The construction of SP GS given in Section IV-A achieves sponsored-member privacy, if N IZK is a zero knowledge argument and the commitment scheme C is hiding. We give the hybrid game as below: Hyb0 . This game corresponds to the sponsored-member privacy game of SP GS. Hyb1 . This game is similar to the previous one except that for any query to SignHU oracle and for signature σb = (σ ′ , P kSm , π) sent to the adversary, the proof π is generated through the N IZK simulator. This game is indistinguishable from the previous one because of N IZK is zero-knowledge. Hyb2 . This game is similar to the previous one except that for any query to SignHU oracle and for signature σb = (σ ′ , P kSm , π) sent to the adversary, P kSm is chosen randomly, and the proof π is generated through the N IZK simulator. This game is indistinguishable from the previous one because the commitment C that is used to generate P kSm is hiding. We can see that assuming the N IZK is zero-knowledge, and commitment C is hiding, we can reduce the sponsoredmember privacy of the SP GS to the last hybrid game. The last game does not have reveal any information about the identity of the sponsored-member and hence it is indistinguishable from the random except with a negligible probability. This concludes the proof. Lemma A.7. Sponsored-member linkability. The construction of SP GS given in Section IV-A achieves sponsoredmember linkability, if GS ensures non-frameability.

We give the hybrid game as below: Hyb0 . This game corresponds to the sponsored-member linkability game of SP GS. Hyb1 . This game is similar to the previous one except that when the adversary receives two signatures, i.e., σb = b (σb′ , P kSm , πb ) for b ∈ {0, 1}, it compares the two signatures σb′ and outputs 1 if σ0′ = σ1′ and outputs 0 if σ0′ ̸= σ1′ . If σ0′ ̸= σ1′ and one (or both) σb′ have not been queried to SignHU oracle before, meaning that (σb′ , P kb,Sm , ·) ∈ / QSign the adversary aborts. This game is indistinguishable from the previous one since if σb′ has not been queried before, then it should have been forged which happens only with negligible probability since GS is non-frameable. We can see that the last hybrid game shows the adversary can output the bit b correctly with high probability. Otherwise, one can construct an adversary B which can output a valid forgery for the group signature σ ′ and break its nonframeability. This concludes the proof. We define k-AGAT with the following algorithms: AGAT.Setup(λ) is run by T A which takes the security parameter λ and outputs the system public parameters pp and the private parameters P rivT A for the T A. pp includes the registered verifiers’ public parameters, the threshold value k, the show function f (). • AGAT.Enroll(pp, H, P rivT A ) is an interactive algorithm run between the T A and the host H. It takes pp, the identity of the host H, and the private parameters of T A, P rivT A , as input, and outputs the host’s private parameters P rivh that includes a private key skh to the host H, and success ⊤ or failure ⊥ to T A. 5 • AGAT.Issue(pp, G, m, , P ubV , P rivh ) is an interactive algorithm run by the host H and guest G, and takes pp, the identity of the guest G, the message m, the verifier’s public parameters P ubV , and the host’s private parameters P rivh , and outputs a token T on m together with private parameters P rivg to the guest, and success ⊤ or failure ⊥ to H. • AGAT.Show(pp, T , P rivg ) is run by the guest G and takes pp, the token T , and the private parameters of the guest P rivg , and outputs a token T ′ which will be presented to V . T ′ = f (T ), and the function f () transforms the token according to the system specifications, that is, f () is defined by the system and included in pp. • AGAT.V erif y(pp, T , P rivV ) is run by V , and outputs 1 if T is a valid token and 0 otherwise. Note that AGAT.V erif y internally checks the policy N T okenh ≤ k (rate limit). • AGAT.Open(pp, T , P rivT A ) is run by T A and takes pp, the token T , and the private parameters of the token authority P rivT A , and outputs the actual identity H of the issuer.

•

5 This algorithm can be defined as a non-interactive algorithm as well.

Security requirements A k-AGAT scheme has the following properties: correctness, unforgeability, anonymity, and traceability. Correctness ensures that AGAT token generation is correct, if for an honest host and guest, AGAT.Issue and AGAT.Show create a token T that AGAT.V erif y accepts, even if the adversary can schedule joining of the hosts and guest and choose their identities and messages. • Unforgeability ensures that if a guest token T is generated, the token generation has actually occurred. Additionally, it captures the fact that the adversary cannot generate more than k valid tokens per verifier V (the rate limit is done as part of AGAT.V erif y algorithm). More formally, we require that for all PPT adversaries A there exists a negligible function ν(λ) such that the adversary who can add corrupted members or corrupt the honest ones after enrollment and is given access to AGAT.Issue oracle should have only a negligible probability of outputting a forged token. • Anonymity ensures that the host, guest, and host-guest relation cannot be learned by the verifier. We define this property as the unlinkability of the host and guests identities, that is, given two guest identities G0 and G1 and two host identities H0 and H1 , the probability of linking the guests to hosts is negligible after seeing tokens issued by AGAT.Issue, AGAT.Show. We allow the adversary to make oracle calls to AGAT.Issue and AGAT.Show for different guests and hosts excluding the challenged ones. Note that this definition is strong and implies both the guest anonymity and host anonymity since an adversary who can distinguish either G0 from G1 , or H0 from H1 by seeing the issued and presented tokens, can also distinguish the identity of the host and guest from the challenged token, and find the the guest-host relation. We note that our definition does not capture host and guest unlinkability, since we do not allow the adversary to see different tokens issued or presented by the challenged entities other than the ones returned by AnonChalb . Excluding these queries on challenged identities prevent trivial attacks where the adversary adds a host or a guest and sees their tokens by querying AGAT.Issue and AGAT.Show, and later links these tokens to the tokens received from AnonChalb . • Traceability protects the system by allowing the token authority T A to reveal the actual identity of the host H who issued the token. More formally, the probability that a PPT adversary A outputs a token T such that the Open algorithm can not identify the host issuer is negligible. •

Note. The anonymity definition does not imply host and guest unlinkability with respect the verifier. This is intentional since (i) the tokens issued by the same host should be linked together in order to apply the rate limit policy on the number of tokens originated from the same host, and (ii) the guest is not trusted and we want to allow the service provider (verifier) to

trace and analyze its access patterns. The anonymity property just ensures that the identity of the honest entities cannot be learned from their tokens and hence the relation between the actual host and guest remains anonymous to the verifier. Oracles. To formally define the security requirements, we use the following oracles: • AddH(H): This oracle allows the adversary to add honest hosts through honest execution of AGAT.Enroll without learning their private parameters. • AddC(H): This oracle allows the adversary to add corrupted hosts. The adversary can deviate from the AGAT.Enroll protocol and send arbitrary messages to T A and see its output out. • CorrU(id) allows the adversary to corrupt the host or guest and learn their communication transcript and their private parameters (including private keys). • Issue(m, G, V, H) This oracle is used by the adversary to obtain a guest token for guest G which can be verified by V , from an honest host H whose private parameters P rivh are not known by the adversary. It returns a token T on the message m using the AGAT.Issue(pp, G, m, P ubV , P rivh ) algorithm. • Show(T , G) This oracle is used by the adversary to obtain a token that can be presented by G. It returns a token T ′ = f (T ) on the message m using the AGAT.Show(pp, T , P rivg ) algorithm. • Open(T ) returns the identity of the host issuer of T . This oracle cannot be called on a token obtained from the AnonChalb oracle. • AnonChalb (pp, m, H0 , H1 , G0 , G1 ): This is a leftright oracle for defining anonymity. It takes as input the group public parameters pp, a message m, two host identities, H0 , H1 , and two guest identities, G0 and G1 , and returns a token Tb issued by Hb and presented by Gb for a randomly chosen b ∈ {0, 1} on the message m. The adversary can call this oracle once. Definition A.2. For any security parameter λ ∈ N and for any PPT adversary A, we say that k-AGAT provides: 1) Correctness if there exists a negligible function ν1 such Corr that Advk-AGAT,A (λ) = P r[ExpCorr k-AGAT,A (λ) = 1] ≥ 1 − ν1 (λ) 2) Unforgeability if there exists a negligible function ν2 U nf orge nf orge such that Advk-AGAT,A (λ) = P r[ExpU k-AGAT,A (λ) = 1] ≤ ν2 (λ) 3) Anonymity if there exists a negligible function ν3 such Anon that Advk-AGAT,A (λ) = P r[ExpAnon k-AGAT,A (λ) = 1] ≤ 1 + ν (λ) 3 2 4) Traceability if there exists a negligible function ν4 such T race race that Advk-AGAT,A (λ) = P r[ExpTk-AGAT,A (λ) = 1] ≤ ν4 (λ) nf orge where ExpCorr ExpU ExpAnon k-AGAT,A , k-AGAT,A , k-AGAT,A , T race Expk-AGAT,A are defined in Figure 5.

ExpCorr k-AGAT,A (pp, P rivT A ) ← AGAT.Setup(λ), N = 0 (m, H, G, V ) ← AAddH,CorrU,AddC (pp) If H ∈ / H or G ∈ / H Return 0 T ← AGAT.Issue(pp, G, m, P ubV , P rivh ) T ′ ← AGAT.Show(pp, T , P rivg )paramSm ) If AGAT.V erif y(pp, T ′ , P rivV ) = 0 Return 0 Return 1 nf orge ExpU k-AGAT,A (pp, P rivT A ) ← AGAT.Setup(λ), N = 0, QIssue = ∅ (m, H, G, T ) ← AAddH,CorrU,AddC,Issue (pp) If H ∈ / H or G ∈ / H Return 0 T ′ ← AGAT.Show(pp, T , P rivg ) If AGAT.V erif y(pp, T ′ , P rivV ) = 0 Return 0 If (m, T ) ∈ / QIssue Return 1

ExpAnon−b k-AGAT,A (pp, P rivT A ) ← AGAT.Setup(λ), N = 0, QAChal = ∅ b′ ← AAddH,CorrU,AddC,Issue,Show,Open,AnonChalb (pp) If b′ ̸= b Return 0 Return 1 race ExpTk-AGAT,A (pp, P rivT A ) ← AGAT.Setup(λ), N = 0 (m, T ′ ) ← AAddH,CorrU,AddC,V erif y,Open (pp) If AGAT.V erif y(pp, T ′ , P rivV ) = 0 Return 0 ? Return AGAT.Open(pp, T ′ , P rivT A ) =⊥

Fig. 5. Security games of k-AGAT

Our construction is generic and uses a sponsored group signature SP GS, and a public key encryption scheme E as its building blocks (please see Section III and IV for their algorithms and security properties). In the nutshell, in our scheme, host act as the sponsor and the guest acts as the sponsored-member of a SPGS scheme. Host uses a sponsor signature to issue a guest token, and the guest uses a sponsored-member signature when it wants to show the token to the verifier. The important point in our scheme is that, SPGS provides complete anonymity that captures unlinkability for sponsors, but the token generation system should not ensure complete anonymity. To enforce the rate limit policy, the token generation should allow host linkability. For this, we use the idea of using pseudonyms together with a group signature to relax their anonymity which is inspired by existing works such as [15]. In our scheme, pseudonyms are generated by T A and shared with hosts during their enrollment. T A maintains a pseudonym list Lw that consists of dummy pseudonyms initially; when the hosts join, T A adds their pseudonyms to the list in batches and after shuffling them it shares the list with the verifier. Verifier do not see the linkage between pseudonyms and identity of the hosts and only use the list Lw to check the validity of the pseudonyms. In guest token issuing algorithm, the host encrypts their pseudonym w using the public key of the verifier and include it in the guest token together with the SPGS sponsor signature. The verifier decrypts the ciphertext and checks whether w is among the valid pseudonyms w ∈ Lw

and if it is valid it keeps a counter for w to count the number of issued tokens by the same host. Although one can use a different approach and let the hosts commit to their pseudonyms and prove their validity to the verifier through the zero knowledge proofs6 without sharing the list Lw with the verifier [15], we chose to share Lw with the verifier directly for checking the validity of pseudonyms to keep our construction simple and efficient. We show that as long as the verifier is trusted this approach ensures a secure k-AGAT construction with the tradeoff that the pseudonyms should be added in batches and this can create a delay between when the host enrolls and when it can issue valid tokens. Additionally, to prevent the guests to steal the pseudonyms, and mix and match of the ciphertext and the the SPGS sponsor signatures in the token, we let the host to choose a fresh random value r and include it both in the ciphertext and the SPGS sponsor signature every time it generates a new guest token. Please see the details of construction below: 1) AGAT.Setup(1λ ) is run by T A and outputs the system parameters pp (related to SP GS and E). T A sets the set up parameters setpp for the SPGS, and runs (pp′ , msk) ← SP GS.Setup(1λ , setpp), and obtains (pp′ , msk). The T A’s private key is set to be the SPGS master private key P rivT A = msk. T A also receives the public key P ubV of the valid verifiers V . Also, it initializes the list of pseudonyms Lw with some random dummy values. T A outputs pp = pp′ ||P ubV ||Lw . 2) AGAT.Enroll(pp, H, P rivT A ) is run by T A and the host H when the host joins. It runs paramSp ← JoinSp (H, P rivT A ), and chooses a random pseudonym wh for the host and outputs P rivh = paramSp ||wh . It also adds wh to Lw . 3) AGAT.Issue(pp, G, m, P ubV , P rivh ) is run between host H and guest G. It first runs paramSm ← JoinSm (G, P rivh ). Then, it chooses a fresh randomness r and runs σ ← SignSp (m||r, P rivh ), and C = E.Enc(P ubV , wh ||r). It outputs a guest token T = (m, r, σ, C) and P rivg = paramSm to the guest. 4) AGAT.Show(pp, T , P rivg ) is run by G. It parse the token as T = (m, r, σ, C), runs σ ′ ← Sm Sign (m||r, P rivg ) and outputs a new token T ′ which is T ′ = (T , σ ′ ). 5) AGAT.V erif y(pp, T ′ , P rivV ) is run by V ; it parses the guest token as T ′ = (m, r, σ, C, σ ′ ). It decrypts C, and obtains (w′ ||r′ ) = E.Dec(P rivV , C) and checks whether r′ = r. If so, it stores (w′ , r′ , T ′ ). It then outputs 1 if (i) SP GS.V erif y Sp (m||r, σ, pp) outputs 1, (ii) SP GS.V erif y Sm (m||r, σ ′ , pp) outputs 1, (iii) w′ is in the list Lw , and w′ has not issued more than k tokens. It also increases the counter N T oken[w′ ] by one. Otherwise, outputs 0. 6) AGAT.Open(pp, T , P rivT A ) is run by T A which takes P rivT A , parses the token as T ′ = (m, r, σ, C, σ ′ ), 6 This approach is publicly verifiable and one can use it to relax the assumption about the verifier’s trustworthiness.

and outputs H ′ = SP GS.OpenSm (P rivT A , σ ′ ) = SP GS.OpenSp (P rivT A , σ). Concrete construction. To instantiate our construction, we use the SPGS concrete construction of section IV-C. For the encryption scheme E, we use the EC-based Elgamal encryption scheme. Security analysis. Below we give a theorem and a proof sketch for our construction of k-AGAT . Theorem A.8. Our k-AGAT construction ensures correctness, unforgeability, b1n -anonymity, and traceability assuming SP GS satisfies correctness, non-frameability, sponsor anonymity, sponsored-member privacy, sponsor traceability, and E is an IND-CPA secure encryption scheme. Proof sketch. We omit the proof due to the space and just give the informal arguments. Correctness is satisfied due to the correctness guarantee of the sponsored group signature scheme SP GS and the public key encryption scheme E. Unforgeability follows from (i) the non-frameability of the sponsored group signature scheme which prevent the adversary to generate a valid sponsor signature σ for a guest token without knowing the private key of the host, (ii) the randomness r used in both signature σ and ciphertext C prevents the adversary to mix and match different signatures and ciphertexts from different tokens to form a new token. Anonymity follows from (i) anonymity of the sponsored group signature scheme which does not let the verifier learn whether the sponsor signature σ in the token has been generated by H0 or H1 , (ii) sponsored-member privacy of SPGS which prevents the verifier to learn the identity of the guest from the sponsored-member signature used in the token, (iii) the IND-CPA security of E which does let the verifier to learn the pseudonym of the host, or even distinguish the encrypted pseudonym from random, (iv) the fact that the registered pseudonyms are independent of the real identity of the hosts, (v) pseudonyms are added to Lw in batches of size bn and the verifier who controls the join of hosts and sees the latest list Lw cannot guess the pseudonym of an honest host with probability greater than b1n . Issuer traceability is ensured due to the traceability of the sponsored group signature scheme.