Hyoseung Kim
email: hyoseungkim@korea.ac.kr.

Olivier Sanders
email: olivier.sanders@orange.com.

Michel Abdalla
email: michel.abdalla@ens.fr.

Jong Hwan Park
email: jhpark@smu.ac.kr.

Practical Dynamic Group Signatures Without Knowledge Extractors

Keywords: Algebraic Group Model, Group Signatures, Knowledge Extractors, PS assumption, Random Oracle Model, Subverted CRS

Dynamic group signature (DGS) allows a user to generate a signature on behalf of a group, while preserving anonymity. Although many existing DGS schemes have been proposed in the random oracle model for achieving efficiency, their security proofs require knowledge extractors that cause loose security reductions. In this paper, we first propose a new practical DGS scheme whose security can be proven without knowledge extractors in the random oracle model. Moreover, our scheme can also be proven in the strong security model where an adversary is allowed to generate group managers' keys maliciously. The efficiency of our scheme is comparable to existing secure DGS schemes in the random oracle model using knowledge extractors. The security of our scheme is based on a new complexity assumption that is obtained by generalizing the Pointcheval-Sanders (PS) assumption. Although our generalized PS (GPS) assumption is interactive, we prove that, under the symmetric discrete logarithm (SDL) assumption, the new GPS assumption holds in the algebraic group model.

Introduction 1.Related Works

Introduced by Chaum and Van Heyst [START_REF] Chaum | Group signatures[END_REF] in 1991, group signature is a primitive which enables users to join a group managed by a so-called issuer. From this point on, these users become group members that are able to anonymously sign on behalf of the group. More specifically, a common verifier can check that a signature σ was issued by a group member thanks to the group public key but it cannot link σ back to a specific member. Without additional requirements, group signature would be trivial to achieve: the group manager could simply generate a signature key pair (sk, pk) for some standard digital signature scheme and distribute sk to each member. Such a system would obviously achieve perfect and irrevocable anonymity. However, such a strong level of anonymity may be undesirable in many scenarios as it is likely to encourage abuses that could tarnish the reputation of the group as a whole or even engage liability for each of its members.

It is therefore more reasonable to implement safeguards which, in the case of group signature schemes, take the form of a specific procedure called opening. This procedure, run by an appointed entity, the opener, require knowledge extractors when proving the non-frameability. Indeed, non-frameability usually relies on the knowledge of the secret value usk which embeds a discrete logarithm challenge during the security proof. Roughly speaking, a successful adversary against non-frameability must have produced a valid proof of usk which is then extracted through rewinding techniques.

Removing Knowledge Extractors. Several approaches, including straight-line extraction techniques such as extractable commitments [START_REF] Garay | Strengthening zero-knowledge protocols using signatures[END_REF], online extractors [START_REF] Fischlin | Communication-efficient non-interactive proofs of knowledge with online extractors[END_REF] and adaptive proofs of knowledge [START_REF] Bernhard | Adaptive proofs of knowledge in the random oracle model[END_REF], have led to fairly inefficient DGS constructions in attempts to remove (rewinding) knowledge extractors from all security proofs in the ROM. Delerablée and Pointcheval [START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF] used the Paillier encryption [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] as an extractable commitment based on a common reference string (CRS). However, such a CRS model entails a critical issue in practice, aside from its complexity. During the security analysis, the CRS is generated along with a trapdoor (e.g., the decryption key of the Paillier encryption), which is used to extract a witness for a NIZK proof. Although the trapdoor enables to effectively complete the relevant security proof, a recent work by Bellare, Fuchsbauer, and Scafuro [START_REF] Bellare | Nizks with an untrusted CRS: security in the face of parameter subversion[END_REF] revisited the security of NIZKs in the presence of a subverted CRS. The authors stressed that the existing techniques to obtain the trusted CRS (such as [START_REF] Ben-Sasson | Secure sampling of public parameters for succinct zero knowledge proofs[END_REF]) are not clear, and thus a CRS subversion using the trapdoor is a realistic attack as shown in the standardized random number generator embedding backdoors (disclosed by Snowden).

Until now, such a CRS-based technique has been widely used in many DGS constructions (e.g., [START_REF] Clarisse | Group signature without random oracles from randomizable signatures[END_REF][START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF][START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF]), based on the DGS model suggested by Bellare, Shi, and Zhang [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF]. In the BSZ notion, it is assumed that there exists a trusted third party which generates an entire group public key gpk, containing all group managers' keys, public parameters, and (if necessary) a CRS (a more general case where these elements are generated independently is considered in [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF]). This is the most convenient setting from the theoretical standpoint but its plausibility is questionable. In all cases, removing the trusted setup assumption is a worthwhile goal as it clearly facilitates practical deployments.

Recently, Fischlin et al. [START_REF] Fischlin | Signatures from sequential-or proofs[END_REF] introduced sequential OR-proofs that were used as a versatile tool to build a DGS scheme without a CRS and knowledge extractors. The resulting DGS scheme is provably secure in the non-programmable ROM, but in a weaker security model where the group managers (i.e., the issuer and the opener) are not separated. In addition, the size of a group public key and a group signature increases linearly in the number of group members. If we consider the real world use of group signatures (and variants) such as [START_REF]Intel. A cost-effective foundation for end-to-end iot security, white paper[END_REF]48], this means group signatures containing billions of elements.

To sum up, several works such as those mentioned above have attempted to overcome the drawbacks of knowledge extractors, but usually at the cost of efficiency or by assuming a trusted setup. A practical DGS scheme, without a CRS, proven without knowledge extractors is thus still an open problem.

Our Contributions

Our goal is to construct a practical DGS scheme that is proven to be secure in the ROM without a CRS and knowledge extractors. To achieve this, we focus on the following three steps:

Revisiting traceability proofs. As we explain above, there is often a small gap in the traceability proof of previous DGS schemes. The latter indeed try to rely on the unforgeability of the signature scheme Σ used by the issuer to sign usk but need at the same time to hide this value from the issuer to ensure nonframeability and also anonymity. This leads to enrolment protocols where the new member first sends to the issuer a commitment of usk (in practice some elements of a group G) to get a signature on usk and thereby to essentially two proofs strategies.

If Σ signs elements of G [START_REF] Abe | Optimal structure-preserving signatures in asymmetric bilinear groups[END_REF][START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF], then the proof is rather simple as the reduction can simply forward the commitment to the signing oracle of Σ. The price to pay is the use of such specific signature schemes (called structure-preserving) that are less efficient than their counterparts signing scalars in Z p (in particular because they yield signatures containing elements of both G 1 and G 2 , where (G 1 , G 2 , G T ) are so-called bilinear groups). Moreover, as said above, the use of such signatures will not solve our problems regarding non-frameability.

Else, Σ signs scalars and the reduction must then find a way to recover usk to query the corresponding signing oracle. This solution has the merit of being compatible with extremely efficient signature schemes [START_REF] Boneh | Short group signatures[END_REF][START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF] but requires knowledge extractors or one of the alternatives discussed in Section 1.1.

At first sight, it seems that we are stuck with these two alternatives. Fortunately, this is true only if one is willing to rely on the unforgeability of Σ, which is more than what is needed to prove traceability. Indeed, in the case where Σ signs groups elements, we do not need full-fledged structure-preserving signatures and their associated negative results [START_REF] Abe | Optimal structure-preserving signatures in asymmetric bilinear groups[END_REF] as a forgery (σ * , M * ) is intuitively useful to an adversary against traceability only if it can prove some statement about M * .

We therefore follow a different strategy and prove traceability directly under computational assumptions. As we want to leverage the efficiency of PS signatures [START_REF] Pointcheval | Short randomizable signatures[END_REF], our computational assumptions will be related to the one (called PS assumption) underlying security of such signatures. More specifically, we define generalized variants of the PS assumption, which we call GPS i (i ∈ {0, 1, 2}) and prove that traceability of our scheme essentially relies on GPS 2 . Clearly, introducing a new assumption to prove the security of our scheme is not ideal but we would like to emphasize two points.

Firstly, the most efficient groups signature schemes (e.g. [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF]) are built upon signature schemes that already rely on interactive ad-hoc assumptions. In this regard, it seems more natural to prove traceability directly under a tailored assumption: this is the same methodology but in our case it has the advantage of avoiding knowledge extractors. Put differently, as it is the case with the most efficient group signature schemes, our construction relies on a tailored assumption but our assumption at least allows us to get a tighter proof.

Secondly, our GPS 2 assumption is not a straightforward adaptation of the PS assumption where one could simply query the signing oracle on g α instead of α. To provide confidence in our new computation problems, we indeed want to prove that they are as hard as the well-known symmetric discrete logarithm (SDL) problem in the algebraic group model (AGM) [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF]. This leads us to define more elaborate inputs and outputs compared to original PS problem. In particular, the adversary now has to query its oracle with pairs (g α , u α ) for different basis g and u which brings us back to something similar to the knowledge of exponents assumption (KEA) [START_REF] Bellare | The knowledge-of-exponent assumptions and 3-round zeroknowledge protocols[END_REF][START_REF] Damgård | Towards practical public key systems secure against chosen ciphertext attacks[END_REF].

Revisiting non-frameability proofs. Once we have dealt with the problem of knowledge extractors in the traceability proofs, we can focus on removing those from the non-frameability proofs. As we explain above, the need for knowledge extractors in the latter comes from the classical combination of proofs of knowledge (of usk) with the Fiat-Shamir heuristic. In the non-frameability proof, the challenger extracts usk from the NIZK proof contained in the forged signature and thereby solves some computational problem. In our construction, we depart from this standard strategy by relying instead on the lossy key technique from [START_REF] Abdalla | Tightly-secure signatures from lossy identification schemes[END_REF][START_REF] Goh | Efficient signature schemes with tight reductions to the diffie-hellman problems[END_REF]. Thanks to this technique, we only require simulation soundness (not extractability) from our NIZK proof, which can be proved without rewinding techniques in our case using the results from [START_REF] Faust | On the nonmalleability of the fiat-shamir transform[END_REF]. Concretely, in our non-frameability proof, we will gradually change the targeted user's public key and thus eventually force the adversary to produce a NIZK proof of a false statement, which contradicts simulation soundness. Of course, it remains to show how one can switch to lossy keys but this can be done quite easily in our concrete construction.

Revisiting anonymity proofs. Our last step in removing trusted setup and knowledge extractors is to revisit the anonymity proof. Indeed, to be as efficient as possible, we have chosen to use a rerandomizable signature scheme (essentially the PS signature scheme [START_REF] Pointcheval | Short randomizable signatures[END_REF]) to issue members' certificates. Thanks to such schemes, the groups members can include a rerandomized version of their certificate without encrypting it, which improves efficiency but also makes zero-knowledge proofs simpler (which further decreases complexity). This approach, originating (to our knowledge) from [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF], has thus the merit of being more efficient than the standard one where the certificate is encrypted, but it makes the anonymity proof slightly harder. Indeed, contrarily to the standard approach, anonymity of the group signature cannot simply rely on the IND-CCA security of the encryption scheme. The usual strategy for such schemes (e.g. [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Clarisse | Group signature without random oracles from randomizable signatures[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF]) is then to replace, in the challenge signature, the certificate on the user's secret key usk * b by one generated on a random key usk, which removes any information on the signer from the group signature and thereby makes any adversary's advantage negligible. However, this strategy requires to issue a valid certificate on the random usk without interacting with the issuer. Existing solutions solve this problem by assuming a trusted setup [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Clarisse | Group signature without random oracles from randomizable signatures[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF], which allows the challenger to generate the issuer's secret key ik and so to produce new certificates. An alternative solution where the issuer's public key would contain a proof of knowledge of ik can be found in [START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF]. The challenger could then extract ik, which brings us back to our first case. Unfortunately, these solutions force us to either rely on a trusted setup or to use knowledge extractors, which we want to avoid. We therefore use a different proof strategy where we end up with a certificate (generated by the adversary) valid for both targeted users, making the adversary's advantage negligible .

In the end, we thus get a DGS construction that can be proved in a model stronger than the BSZ one [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] (that is, we do not require honest key generation for the issuer), without knowledge extractors. Contrarily to previous attempts, this is done with almost no impact on the efficiency, as shown in Section 6 where we compare our scheme with the most relevant ones from the state-of-the-art.

Preliminaries

Basic Notations

We use Z p to denote the set {0, . . . , p -1}, where p is a prime. Function f : R → R is called negligible if, for any d > 0, the inequality | f (k)| < 1/k d holds for sufficiently large k. We denote by P(A(str A ) ↔ B(str B )) → (out A ; out B ) the protocol P containing the interactive algorithms A and B, where the algorithms respectively take str A and str B as input and then output out A and out B as results. x ← $ S indicates the uniformly random sampling of the element x from the finite set S. λ is used to denote a security parameter. All group operations are done modulo p unless otherwise stated throughout this paper. Bilinear Maps. A bilinear group is a tuple BG = (p, G 1 , G 2 , G T , g, ĝ, e), where G 1 , G 2 and G T are groups of prime order p, g ∈ G 1 , ĝ ∈ G 2 are generators of each group, and e is a bilinear map such that e : G 1 × G 2 → G T . As usual, a bilinear map (i.e., pairing) e satisfies the following properties for all g and ĝ: bilinearity, non-degeneracy, and efficiency. We assume the existence of a (deterministic) group-generation algorithm GrGen(1 λ ) → BG. In this paper, we only consider type-3 bilinear groups according to the classification in [START_REF] Galbraith | Pairings for cryptographers[END_REF], that is, we assume that no efficiently computable homomorphism exists between G 1 and G 2 , in either direction. Digital Signature. A digital signature scheme consists of three algorithms: (1) DSKg(1 λ ) → (sk, vk): a key generation algorithm that outputs a signing key sk and a public key vk under λ ; (2) DSSig(sk, m) → σ DS : a signing algorithm that takes a singing key sk and a message m as input and then outputs a signature σ DS ; and (3) DSVf(vk, m , σ ) → {0, 1}: a verifying algorithm that takes a verifying key vk, a message m , and a signature σ DS and then returns 1 if (m, σ ) is valid under vk; otherwise, 0. We consider that a digital signature scheme is secure if it achieves existential unforgeability under chosen message attacks (EUF-CMA) [START_REF] Goldwasser | A digital signature scheme secure against adaptive chosen-message attacks[END_REF].

Algebraic Group Model

Following [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF], we use an algebraic security game parametrized by a cyclic group G = (p, G) where a challenger C interacts with an algebraic adversary A alg . Intuitively, an algebraic adversary can produce a new element in G only through linear combinations of known elements in G. The formal definition is as follows:

Definition 2.1. An algorithm A alg executed in an algebraic security game G G is called algebraic if for all elements h ∈ G that A alg returns, it also outputs the representation of h regarding received elements in G. More precisely, if Q = {g 1 , ..., g |Q| } is the list of group elements in G that A alg has received so far, then

A alg additionally returns a vector h = (h 1 , ..., h |Q| ) ∈ Z |Q| p , so that h = ∏ |Q| k=1 g h k k , letting [h] h denote such an output.
As with the standard security model, when G G provides a collection of oracles, C deals with those oracles to answer queries from A alg . At the end of the game, G G,A alg1 outputs a bit b ∈ {0, 1} as usual, and we identify that A alg wins when b = 1. Then, we define its advantage as Adv G G,A alg = Pr[G G,A alg = 1]. According to [START_REF] Bauer | A classification of computational assumptions in the algebraic group model[END_REF], the algebraic algorithm for a type-3 bilinear group BG can be defined by setting G ∈ {G 1 , G 2 , G T }. An important fact is that elements in G 2 and G T are not helpful to produce an element in G 1 for this type of bilinear group as no efficiently computable isomorphism is known between these groups. We use this to prove new assumptions later in Section 3.2.

Dynamic Group Signature

We begin with the syntax of DGS which is a slight modification of [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF]. In the well-known models such as BSZ [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] and KY [START_REF] Kiayias | Group signatures with efficient concurrent join[END_REF], a single trusted entity executes a group key generation to obtain a group public key and secret keys, and gives the relevant secret keys to each of the issuer and the opener. Such a key generation in the BSZ model must be assumed to be honest, and (if necessary) a CRS can also be included in the group public key. Conversely, Bootle et al. [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF] separated the group key generation into three ones; a setup algorithm for generating public parameters, a key generation algorithm for the issuer and a key generation algorithm for the opener. Moreover, in terms of security, [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF] allows an adversarial issuer or opener to generate its key maliciously and thus encompasses the weaker security model of [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF][START_REF] Kiayias | Group signatures with efficient concurrent join[END_REF].

In the following description, there exists slight difference between [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF] and our syntax; a user is associated with an identity i by using a PKI (such as [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF]), and the issuer/opener key generation algorithm is executed individually without interaction.

Setup(1 λ ) → pp. Under a security parameter λ , the setup algorithm outputs the public parameter pp.

IKg(pp) → (ik, ipk). Given a public parameter pp, the issuer key generation algorithm outputs the issuer's public/secret key pair (ipk, ik).

OKg(pp) → (ok, opk). Given a public parameter pp, the opener key generation algorithm outputs the opener's public/secret key pair (opk, ok).

UKg(1 λ , i) → (upk i , usk i ). User i invokes the user key generation algorithm to produce its public key upk i and secret key usk i . We assume that upk i is authenticated by a certification authority (CA).

GJoin(Join(i, usk i , gpk) ↔ Iss(i, upk i , ik)) → (gsk i ; reg i ). User i executes the GJoin protocol with the issuer. The algorithm Join, run by the user i, takes the user secret key usk i and the group manager's public key gpk := (pp, ipk, opk). The algorithm Iss, run by the issuer, takes the user public key upk i and its secret key ik. At the end of the protocol, the user obtains a group signing key gsk i , and the issuer adds registration information reg i for the user i onto registration list reg. This list is shared with the opener, who then has access to read reg.

GSig(gsk i , m) → σ . User i, with group signing key gsk i , invokes the signing algorithm to produce a signature σ on a message m ∈ {0, 1} * .

GVf(gpk, m, σ ) → {0, 1}. Anyone can invoke the verification algorithm to verify a group signature. The algorithm takes the group manager's public key gpk = (pp, ipk, opk), a message m, and a signature σ , and outputs 1 if σ is valid on m; otherwise, it outputs 0.

GOpen(ok, m, σ , reg) → (i, Π) or ⊥. The opener invokes the opening algorithm to recover the identity i of a user who has produced a given signature. The algorithm takes the opening key ok, a message m, a valid signature σ and the registration list reg. It outputs an identity i and a proof Π claiming that the user i produced σ on m or it outputs ⊥.

GJudge(m, σ , gpk, i, upk i , Π) → {0, 1}. Anyone can invoke the judging algorithm to verify the opener's output. The algorithm takes a message m, a valid signature σ on m, the group public key gpk = (pp, ipk, opk), an identity i along with its public key upk i , and a proof Π that was generated while opening. It outputs 1 if Π is valid; otherwise, it outputs 0.

Definition 2.2. A DGS scheme is correct if the following conditions hold for an honest user i and any message m:

Pr           pp ← Setup(1 λ ), (ik, ipk) ← IKg(pp), (ok, opk) ← OKg(pp), //gpk := (pp, ipk, opk) (upk i , usk i ) ← UKg(1 λ , i), GVf(gpk, m, σ ) = 1 ∧ : (gsk i , reg i ) ← GJoin Join(i, usk i , gpk) GJudge(m, σ , gpk, i, upk i , Π) = 1 ↔ Iss(i, upk i , ik) , ∧ i = j σ ← GSig(gsk i , m), ( j, Π) ← GOpen(ok, m, σ , reg)           = 1.

Oracles Description.

To define security models where the challenger C interacts with an adversary A, we give the description of oracles used by A in Figure 1. C therein maintains the following lists (L h , L c , L sk , L σ , and L ch ) to control those oracles. Here, the state cont indicates that the user is corrupted but has not yet joined, while the state accept indicates that the user is corrupted and has already been accepted to join the system.

Security Models.

Following [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF] with the minor syntactic changes, our security definitions of anonymity and non-frameability capture strong notions by allowing maliciously generated keys of issuer and/or opener.

Anonymity. We here consider the selfless anonymity notion [START_REF] Camenisch | Group signatures: Better efficiency and new theoretical aspects[END_REF] which states that a signature generated using a key gsk can be opened only by the opener and the owner of gsk (that is, a group member is always

AddU(i): -(upk i , usk i ) ← UKg(1 λ , i). -(gsk i ; reg i ) ← GJoin(Join(i, usk i , gpk) ↔ Iss(i, upk i , ik)).
reg ← reg ∪ {reg i }.

-

L h ← L h ∪ {i}.
-Return upk i .

CrptU(i, upk):

upk i ← upk.

-

L c ← L c ∪ {(i, cont)}. SndToI(i): -If (i, cont) / ∈ L c then return ⊥.
-

reg i ← GJoin(A ↔ Iss(i, upk i , ik)).
reg ← reg ∪ {reg i }.

-

L c ← L c ∪ {(i, accept)}. SndToU(i): -(upk i , usk i ) ← UKg(1 λ , i).
gsk i ← GJoin(Join(i, usk i , gpk) ↔ A).

-L h ← L h ∪ {i}.

USK(i):

-If (i, * , * ) ∈ L ch then return ⊥.

-L sk ← L sk ∪ {i}.

-Return (gsk i , usk i ).

RReg(i):

-Return reg i .

WReg(i, ρ):

reg i ← ρ.

Sig(i, m):

-If i / ∈ L h , then return ⊥.
σ ← GSig(gsk i , m).

-

L σ ← L σ ∪ {(i, m, σ )} -Return σ . Open(m, σ ): -If ( * , m * , σ * ) ∈ L ch , then return ⊥.
-Return GOpen(ok, m, σ , reg).

CH b (i * 0 , i * 1 , m * ): -If i * 0 / ∈ L h or i * 1 / ∈ L h then return ⊥. -If i * 0 ∈ L sk or i * 1 ∈ L sk then return ⊥. -σ * ← GSig(gsk i * b , m * ). -L ch ← {(i * 0 , m * , σ * ), (i * 1 , m * , σ * )}. -Return σ * .
Figure 1: Oracles used by an adversary able to recognize his signatures). It is formally defined in Figure 2. The goal of A, which may control the issuer, is to successfully guess if either i * 0 or i * 1 is the signer's identity for the challenge signature σ * , provided that gsk i * 0 and gsk i * 1 did not leak. The advantage of A in the anonymity game in Figure 2 is therefore defined as

Adv Anon DGS,A = Pr[G Anon-0 DGS,A = 1] -Pr[G Anon-1 DGS,A = 1] .
Definition 2.3. A group signature scheme DGS is anonymous if Adv Anon DGS,A is negligible for any λ and any polynomial-time adversary A.

Non-frameability. This notion ensures that an adversary cannot generate a valid signature that opens to a certain honest user who has never actually signed the message of the signature. Non-frameability is required to hold even when the issuer and the opener are both compromised. The non-frameability game is defined in

G Anon-b DGS,A : -pp ← Setup(1 λ ).
-(ipk, st A ) ← A(pp).

-(ok, opk) ← OKg(pp).

b ← A SndToU, USK, WReg, Sig, Open,CH b (opk; st A ).

-Return b . . Following [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF], we assume without loss of generality that a single user i * is honest. The goal of A is then to create a valid forgery σ * on a message m * that can be opened to i * , along with a judge-accepted proof Π * . The advantage of A in the non-frameability game defined in Figure 3 is

Adv N f DGS,A = Pr[G N f DGS,A = 1].
Definition 2.4. A group signature scheme DGS is non-frameable if Adv N f DGS,A is negligible for any λ and any polynomial-time adversary A.

G N f DGS,A : -pp ← Setup(1 λ ).
-(ipk, opk, st A ) ← A(pp).

gpk := (pp, ipk, opk).

-(m * , σ * , i * , Π * ) ← A SndToU, USK, Sig (st A ).
-If the following conditions hold, then return 1.

(1) GVf(gpk, m * , σ * ) = 1.

(

) {i * } = L h \L sk and i * / ∈ L sk and (i * , m * , * ) / ∈ L σ . (3) GJudge(m * , σ * , gpk, i * , upk * , Π * ) = 1. 2
-Return 0. Traceability. This notion implies that an adversary can only produce traceable signatures when the issuer is honest and the opener is partially corrupt. The meaning of being partially corrupt is introduced in [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF], where the opener is controlled by A but invokes the GOpen algorithm honestly. This is a necessary restriction as one cannot retain any meaningful notion otherwise (a fully malicious opener could return ⊥ as the result of each query). Concretely, this means that the knowledge of the opener secret key ok is of no help to escape identification. We note that the notion of the partial corruption is almost the same as in [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF]. The traceability game is defined in Figure 4. A can succeed in either of two ways: (a) by generating a valid signature σ * that cannot be opened (i.e., GOpen outputs ⊥ on σ * ) (b) by preventing the challenger from outputting a valid proof Π * , i.e. one accepted by GJudge. The advantage of A in the traceability game shown in Figure 4 is

Adv Trace DGS,A = Pr[G Trace DGS,A = 1].
Definition 2.5. A group signature scheme DGS is traceable if Adv Trace DGS,A is negligible for any λ and any polynomial-time adversary A .

G Trace

DGS,A :

pp ← Setup(1 λ ).

-(ik, ipk) ← IKg(pp).

-(ok, opk) ← OKg(pp).

gpk := (pp, ipk, opk).

-(m * , σ * ) ← A AddU, CrptU, SndToI, USK, RReg (gpk, ok).

-If the following conditions hold, then return 1.

(1) GVf(gpk, m * , σ * ) = 1.

(2) When (i * , Π * ) ← GOpen(ok, m * , σ * , reg),

(i * , Π * ) = ⊥ or GJudge(m * , σ * , gpk, i * , upk * , Π * ) = 0.
-Return 0.

Complexity Assumptions

Let BG = (p, G 1 , G 2 , G T , g, ĝ, e) be a type-3 pairing group.

Symmetric Discrete Logarithm (SDL) Assumption [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF]. Given a tuple (g, g z ), where z ← $ Z p , the DL problem is to find z. The symmetric version (the so-called SDL) is defined when a pair ( ĝ, ĝz ) is additionally given, where ĝ ∈ G 2 is a generator.

External Diffie-Hellman (XDH) Assumption [START_REF] Boneh | Short group signatures[END_REF]. Given a tuple (g, g a , g b , T ), where a, b ← $ Z p , the XDH problem in G 1 (denoted by XDH G 1 ) is to decide whether T = g ab or R ← $ G 1 .

GPS Assumptions and Their Relations

GPS Assumptions

Pointcheval and Sanders [START_REF] Pointcheval | Short randomizable signatures[END_REF] introduced a new interactive assumption called the PS assumption, thereby realizing a very efficient randomizable signature scheme. Recently, the generalized version of PS (denoted as GPS) assumption was introduced in [START_REF] Kim | Practical dynamic group signature with efficient concurrent joins and batch verifications[END_REF] by splitting the equipped oracle into two ones, analogously to the generalized LRSW assumption [START_REF] Camenisch | One TPM to bind them all: Fixing TPM 2.0 for provably secure anonymous attestation[END_REF]. On top of those results, we furthermore expand the GPS assumption in the direction of replacing all exponential values with group elements, which can be viewed as a first step to construct a structure-preserving signature from the PS assumption2 . Those assumptions are defined in a type-3 pairing group BG = (p, G 1 , G 2 , G T , g, ĝ, e) as follows:

PS Assumption [START_REF] Pointcheval | Short randomizable signatures[END_REF]. Given a tuple ( ĝx , ĝy ) and an oracle

O PS (m) → (u, u x+ym ) ∈ G 2 1 , where x, y ← $ Z p , m ∈ Z p and u ← $ G 1 , the PS problem is to find a tuple (u * , v * , m * ) ∈ G 2 1 ×Z p such that (1) u * = 1 and m * = 0, (2) v * = u * x+ym *
, and (3) for all m queried to O PS , m * = m. The PS assumption holds if the advantage of solving the problem is negligible in the security parameter λ . GPS i Assumption. For i ∈ {0, 1, 2}, given a tuple ( ĝx , ĝy ), where x, y ← $ Z p and two oracles O 1 and O 2 as shown in Figure 6, the GPS i problem is to find a tuple (u * , v * , m * ) in the GPS 0 and GPS 1 along with a tuple ( f * , u * , v * , w * ) in the GPS 2 . The GPS i assumption holds if the advantage of solving the problem is negligible in λ .

We note that the definition of the GPS 2 problem does not allow to verify the relation log g f * = log u * w * given only the group elements ( f * , u * , v * , w * ) in G 1 . However, this will not be a problem for our DGS construction because it uses an additionally NIZK proof to prove the equality of these discrete logarithms. The Figure 5 shows the relations between these new assumptions and the SDL one. Proof. Consider two security reductions: one from GPS 2 to GPS 1 where an adversary A 1 against GPS 1 and its challenger C 1 (i.e., an adversary A 2 against GPS 2 together) exist, and one from GPS 1 to GPS 0 , where an adversary A 0 against GPS 0 and its challenger C 0 exist. Therein, C 0 bridges these reductions by playing a role in A 1 together. Now, it is desirable to show that while C 1 , given an GPS 2 instance, simulates GPS 1 for A 1 (= C 0 ), C 0 simulates GPS 0 for A 0 . Since the problem instances are the same as ( ĝx , ĝy ) for some hidden x, y ∈ Z p , C 1 relays the instance to C 0 , and sequentially, C 0 relays it to A 0 . Whenever C 0 is asked to invoke

O GPS 0 1 from A 0 , it requests O GPS 1 1 , which is managed by C 1 . Then, C 1 calls O GPS 2 1
to obtain u as output. This value u is forwarded to C 0 and A 0 in sequence. Whenever A 0 sends a query . It is obvious that C 1 can win with

(u, m) ∈ G 1 × Z p to O GPS 0 2 , C 0 computes f = g m and w = u m . Using these, C 0 calls O GPS 1
( f * , u * , v * , w * ).
Finally, it was shown in [START_REF] Kim | Practical dynamic group signature with efficient concurrent joins and batch verifications[END_REF] that the adversary against the GPS 0 problem can be changed into one against the original PS problem, leading to the following lemma.

Lemma 3.2. The original PS assumption holds under the GPS 0 assumption.

Oracles Output GPS [40] O 1 (•) → u: -u ← $ G 1 .
-

Q 1 = Q 1 ∪ {u}. O 2 (u, m) → v: // m ∈ Z p . -If u / ∈ Q 1 or (u, * ) ∈ Q 2 then return ⊥. -v = u x+my .
-

Q 2 = Q 2 ∪ {(u, m)}. A O 1 ,O 2 ( ĝx , ĝy ) → (u * , v * , m * ). // u, v ∈ G 1 . // m ∈ Z p .
Output is valid if (1) u * = 1 and m * = 0.

(

) v * = u * x+m * y . (3) ∀( * , m) ∈ Q 2 , m * = m. GPS [40] O 1 (•) → u: -r ← $ Z p . 2
u = g r .

-

Q 1 = Q 1 ∪ {u}. O 2 ( f , u, w)→ v: // f , w ∈ G 1 . -If u / ∈ Q 1 or (u, * ) ∈ Q 2 then return ⊥.
-If w = f r s.t. r = log g u, then return ⊥.

v = u x w y .

-

Q 2 = Q 2 ∪ {(u, f )}. A O 1 ,O 2 ( ĝx , ĝy ) → (u * , v * , m * ). // u, v ∈ G 1 . // m ∈ Z p .
Output is valid if (1) u * = 1 and m * = 0.

(

) v * = u * x+m * y . (3) ∀( * , f ) ∈ Q 2 , g m * = f . GPS O 1 (•) → u: -r ← $ Z p . 2
u = g r .

-

Q 1 = Q 1 ∪ {u}. O 2 ( f , u, w)→ v: // f , w ∈ G 1 . -If u / ∈ Q 1 or (u, * ) ∈ Q 2 then return ⊥.
-If w = f r s.t. r = log g u, then return ⊥.

v = u x w y .

-

Q 2 = Q 2 ∪ {(u, f )}. A O 1 ,O 2 ( ĝx , ĝy ) → ( f * , u * , v * , w * ). // f * , u * , v * , w * ∈ G 1 .
Output is valid if (1) u * = 1 and f * = 1.

(2) v * = u * x w * y .

(

) log g f * = log u * w * . // non-falsifiable (4) ∀( * , f ) ∈ Q 2 , f * = f . 3

Reduction from SDL to GPS 2 in the AGM

Our reduction from SDL to GPS 2 in the AGM shares many similarities with the one from DL to Knowledge of Exponent Assumption (KEA) [START_REF] Bellare | The knowledge-of-exponent assumptions and 3-round zeroknowledge protocols[END_REF][START_REF] Damgård | Towards practical public key systems secure against chosen ciphertext attacks[END_REF]. We therefore start by describing the latter 3 , as it may help to understand the strategy behind the former.

KEA in the AGM. The KEA states that, for any adversary A that has a tuple (g, u = g r ) ∈ G 2 for input will output ( f , w = f r ) ∈ G 2 , there exists an extractor E KEA A that, with the same input, returns m such that f = g m and w = u m . In the AGM, when an algebraic adversary A alg outputs ( f , w) along with their representations (described below), there exists an extractor E KEA A alg which outputs the discrete logarithm m = log g f = log u w that A alg knows if the DL assumption holds in the group G. In terms of proving the equality of discrete logarithms (EDL) especially using fixed bases given to A alg , we now have an efficient knowledge extractor in the AGM even without any extraction techniques, such as (rewinding) proofs of the EDL or extractable commitments. More formally, we prove that there is an extractor for KEA in the AGM under the DL assumption.

Theorem 3.3. Under the DL assumption, the KEA holds in the AGM.

Proof. Borrowing the proof strategy in [START_REF] Bauer | A classification of computational assumptions in the algebraic group model[END_REF], we show that a non-zero polynomial yields the DL solution as one of its roots, given the adversary's representations. Let (g, g z ) be a DL instance. If an algebraic adversary

A alg with input (g, u = g r ) outputs ( f = g m , w = u m ) along with their representations f = (f 1 , f 2 ) ∈ Z 2 p and w = (w 1 , w 2 ) ∈ Z 2
p , this means that f = g f 1 u f 2 and w = g w 1 u w 2 . The equation log g f = log u w then gives the following equation:

w 1 + (w 2 -f 1 )r -f 2 r 2 = 0. (1)
There are two possible cases. If the polynomial w 1 + (w 2 -f 1 )r -f 2 r 2 is the zero polynomial (i.e., all coefficients are zero with respect to the variable r), we have the relations w 1 = 0, w 2 = f 1 , and f 2 = 0, which give f = g f 1 and w = u w 2 . Therefore, we can build an extractor E KEA A alg that outputs m := f 1 as the discrete logarithm. Otherwise, if the polynomial w 1 + (w 2 -f 1 )r -f 2 r 2 is a non-zero polynomial, (i.e., some coefficients are not zero with respect to the variable r), we can solve the DL problem as follows: by setting u = (g z ) s g t for randomly chosen s,t in Z p , r can be implicitly set as r = sz + t. In this case, the equation (1) can be rewritten to a 0 + a 1 z + a 2 z 2 = 0, where

a 0 = w 1 + w 2 t -f 1 t -f 2 t 2 , a 1 = w 2 s -f 1 s -2f 2 st, and a 2 = -f 2 s 2 . As w 1 + (w 2 -f 1 )r -f 2 r 2 is
a non-zero polynomial with one root, we know that we cannot have w 2 -f 1 = f 2 = 0. Therefore, since s is randomly sampled and information-theoretically hidden from the view of A alg , the probability that a 0 = 0 ∧ a 1 = 0 ∧ a 2 = 0 is negligible. Consequently, we can solve the DL problem by finding roots of the non-zero polynomial

a 0 + a 1 Z + a 2 Z 2 ∈ Z p [Z] of a degree that is at least 1.
With this observation, we now prove that the GPS 2 problem in the AGM is at least as hard as the SDL problem. We recall the Schwarz-Zippel lemma: Lemma 3.4 (Schwarz-Zippel Lemma). Let P ∈ F[X 1 , ..., X ] be a non-zero polynomial of total degree d ≥ 0 over a field F. If the values r 1 , ..., r are independently chosen at random from a finite subset S ⊂ F, then Pr[P(r 1 , ..., r ) = 0] ≤ d |S| .

We now provide additional notations relative to representations that an algebraic adversary A alg outputs in the AGM. Let Q = {g 1 , ..., g |Q| } be the set of group elements known to A alg . By definition 2.1,

A alg should outputs [h] h which contains h ∈ G and h = (h 1 , ..., h |Q| ) ∈ Z |Q| p such that h = ∏ |Q| k=1 g h k k . We denote such an element h k regarding g k ∈ Q by [h|g k ].
If each of {log g g k } is represented by an -variate polynomial in Z p [X 1 , ..., X ] for some ∈ N, we can define a polynomial P h [ X], where X = (X 1 , ..., X ), to denote log g h =

∑ |Q| k=1 [h|g k ] • log g g k .
It is easy to see that the coefficients of P h [ X] are composed of linear combinations of elements in h. Moreover, an evaluation of the polynomial P h [ X] at x = (x 1 , ..., x ), where x j ∈ X j , specifies log g h to some value z ∈ Z p (i.e., P h (x) = z). Regarding any polynomial P, we hereafter use P(x) = 0 to mean that the polynomial evaluates zero at the point x, and use P[ X] = 0 to mean that the polynomial in variables X is the zero-polynomial (of which all coefficients are zero). Based on these notations, we refer to the following lemma from [START_REF] Bauer | A classification of computational assumptions in the algebraic group model[END_REF]. The probability that Q[Z] is the zero-polynomial is less than the probability that the leading coefficient

a d of Q[Z] is zero (i.e., Pr[Q[Z] = 0] ≤ Pr[a d = 0]
). Putting lemmas 3.4 and 3.5 together, we can obtain the upper-bounded probability that Q[Z] = 0 in security reductions.

GPS 2 problem in the AGM. Figure 7 presents the GPS 2 problem in the AGM. Compared to the previous GPS 2 problem in Figure 6, there are two primary differences, besides the representations about the group elements that an adversary (denoted as A alg ) outputs. The fist one is that the O 2 oracle contains the extractor Ẽ (marked in the red dotted box) which is a (deterministic) polynomial-time algorithm; briefly speaking, Ẽ takes two group elements f , w ∈ G 1 along with their representations, and outputs an exponent m ∈ Z p such that f = g m and w = u m or ⊥. Whether Ẽ outputs m or ⊥ depends on whether or not the new polynomial

R k P f k [ X] -P w k [ X],
determined by the input of A alg , is the zero-polynomial. If the polynomial is not the zero-polynomial, Ẽ outputs ⊥, in which case, fortunately, the SDL problem is solved. That is, assuming that the SDL problem is hard, Ẽ succeeds in extracting the discrete logarithm m and thus O 2 is able to respond to the A alg query. The other difference is that the equality of log g f * = log u * w * in (w3) can be efficiently checked by a polynomial evaluation, which was not possible in the GPS 2 problem in Figure 6; indeed, the equality log g f * = log u * w * can be written by evaluating polynomials as follows:

P * f (x) = log g f * = log g w * log g u * = P * w (x) P * u (x)
, where x is a vector of points chosen by the challenger to A alg . The GPS 2 assumption is thus falsifiable in the AGM. We can now formally state our result regarding the reduction from SDL to GPS 2 .

Theorem 3.6. Under the SDL assumption, the GPS 2 assumption in the AGM holds.

Proof. Let A alg be an algebraic adversary and C be a challenger. As an adversary of the SDL problem, C is given an SDL instance (g, ĝ, Z = g z , Ẑ = ĝz ). C begins a simulation by sampling {s 0 ,t 0 , s 0 ,t 0 } ← $ Z p , and implicitly sets x = s 0 z + t 0 and y = s 0 z + t 0 . A alg is initially given X = ĝx = Ẑs 0 ĝt 0 and Ŷ = ĝy = Ẑs 0 ĝt 0 . Let q 1 be the maximum number of oracle queries to O 1 . For the i-th O 1 query, C 2 returns u i = Z s i g t i where {s i ,t i } ← $ Z * p , implicitly setting r i = s i z + t i . For the k-th O 2 query, we assume that C successfully responds to the previous (k -1)-th O 2 queries. In that case, {v = g r (x+m y) } k-1 =1 are given to A alg ,

G GPS 2 BG,A alg : -BG = (p, G 1 , G 2 , G T , g, ĝ, e) ← GrGen(1 λ ). -x ← $ Z p := X, y ← $ Z p := Y. -[ f * ] f * , [u * ] u * , [v * ] v * , [w * ] w * ← A O 1 ,O 2 alg ( ĝx , ĝy ).
-If the following conditions hold, then return 1.

(w1) f * = 1 and u * = 1.

(w2

) v * = u * x w * y . (w3) log g f * = log u * w * ↔ P f * (x)P u * (x) -P w * (x) = 0. // x := (x, y, r 1 , ..., r |Q 1 | ). (w4) ∀ f k ∈ Q 2 , f * = f k . -Return 0. O 1 (•): //k-th query -r k ← $ Z p := R k .
u k = g r k .

-

Q 1 = Q 1 ∪ {u k }. -Return u k . O 2 ([ f k ] f k , [u k ] u k , [w k ] w k ): // x := (x, y, r 1 , ..., r |Q 1 | ) -If u k = Q 1 or (u k , * ) ∈ Q 2 then return ⊥. -For r k = log g u k , if f r k k = w k (i.e., r k P f k [x] -P w k [x] = 0), then return ⊥. -m k ← Ẽ([ f k ] f k , [w k ] w k ). -v k = u x k w y k = u x+m k y k . -Q 2 = Q 2 ∪ {(u k , f k )}. -Return v. Ẽ([ f k ] f k , [w k ] w k ): // X := (X, Y, R 1 , ..., R |Q 1 | ). -If R k P f k [ X] -P w k [ X] = 0, then return ⊥. -Return [f k |g].
([ f k ] f k , [u k ] u k , [w k ] w k
), which after reordering {u i } values depending on the O 2 query's input, determines the following polynomials:

P f k [ X] = [f k |g] + q 1 ∑ =1 R [f k |u ] + k-1 ∑ =1 R [f k |v ](X + m Y), P w k [ X] = [w k |g] + q 1 ∑ =1 R [w k |u ] + k-1 ∑ =1 R [w k |v ](X + m Y),
where [ X] = (X, Y, R 1 , ..., R q 1 ). We notice that the two polynomials are represented by the fact that {u = g r } q 1 =1 (set by O 1 ) and {v = g r (x+m y) } k-1 =1 (set by O 2 ). If w k = f r k k , which is ensured by the second condition of O 2 , then this equality implies that the following polynomial

P * k [ X] = R k P f k [ X] -P w k [ X]
of degree 3 must have at least one root that is the vector of x = (x, y, r 1 , ..., r q 1 ). That is, P * k (x) = 0. There are two possible cases:

Claim 1. If P * k [ X] = 0, then Ẽ([ f k ] f k , [w k ] w k ) works correctly.
Proof. This claim means that Ẽ is able to extract the correct m k from the fact P * k [ X] = 0. As the equality

R k P f k [ X] = P w k [ X]
holds, the coefficients (which are components of the representation vectors f k and w k ) are determined by equating coefficients of monomials in both sides as follows:

-

[f k |g] = [w k |u k ] (due to R k ). -[f k |u ] = 0 for all ∈ {1, ..., q 1 } (due to R k R ). -[f k |v ] = 0 for all ∈ {1, ..., k -1} (due to R k R X).
-[w k |u ] = 0 for all ( = k) ∈ {1, ..., q 1 } (due to R ).

-[w k |v ] = 0 for all ∈ {1, ..., k -1} (due to R X).

Eventually, the above equations indicates that

f k = g [f k |g] and w k = u [w k |u k ] k
, and thus Ẽ outputs

m k := [f k |g] as the discrete logarithm. Claim 2. If P * k [ X] = 0, then the SDL problem is solved. ( Ẽ does not work.) Proof. By converting variables X, Y, {R } into S 0 Z + T 0 , S 0 Z + T 0 , {S Z + T }, a univariate polynomial Q * k [Z] can be defined from P * k [ X]. If Q * k [Z]
is a non-zero polynomial, it must have at least one root (including z as the solution of the SDL problem) since

P * k (x) = Q * k (z) = 0. Based on this fact, C first checks if Q * k [Z]
= 0, and if so, C aborts. In fact, the probability that Q * k [Z] = 0 is statistically negligible due to the following reason. As P * k [ X] has degree 3, the leading coefficient a 3 of Q * k [Z] can be represented by a polynomial in Z p [S 0 , S 0 , S 1 , ..., S q 1 ] of degree 3 by lemma 3.5. Since s = (s 0 , s 0 , s 1 , ..., s q 1 ) were perfectly hidden, s is independently chosen at random from the view of A alg . Hence, the Schwartz-Zippel lemma (Lemma 3.4) implies that the probability of the coefficient a 3 evaluating 0 at s is upper-bounded by 3 p . This eventually implies that the inequality Pr

[Q * k [Z] = 0] ≤ Pr[a 3 = 0] ≤ 3 p .
In this case, C can obtain the solution z for the given SDL problem by finding roots of the equation Q * k [Z] = 0. It is obvious that the event when P * k [ X] = 0 occurs is equivalent to the event that the extractor Ẽ does not work (denoted by ¬ Ẽ). When denoting Pr P

* k [ X] = 0 = Pr[¬ Ẽ], we have Pr[¬ Ẽ] ≤ Pr P * k [ X] = 0 ∧ Q * k [Z] = 0 + Pr[Q * k [Z] = 0] ≤ Adv SDL G,C + 3 p .
Let q 2 be the maximum number of oracle queries to O 2 . Due to Claim 2, we can assume that Ẽ works correctly for all O 2 queries under the SDL assumption. Finally, A alg outputs

([ f * ] f * , [u * ] u * , [v * ] v * , [w * ] w *
), based on the given values g, {u = g r } q 1 =1 , {v = g r (x+m y) } q 2 =1 where q 2 ≤ q 1 , and m is extracted using Ẽ. For X = (X, Y, R 1 , ..., R q 1 ), consider polynomials in Z p [ X] corresponding to the output of A alg , which can be represented by

P f * [ X] = [f * |g] + q 1 ∑ =1 [f * |u ]R + q 2 ∑ =1 [f * |v ](X + m Y)R , P u * [ X] = [u * |g] + q 1 ∑ =1 [u * |u ]R + q 2 ∑ =1 [u * |v ](X + m Y)R , P v * [ X] = [v * |g] + q 1 ∑ =1 [v * |u ]R + q 2 ∑ =1 [v * |v ](X + m Y)R , P w * [ X] = [w * |g] + q 1 ∑ =1 [w * |u ]R + q 2 ∑ =1 [w * |v ](X + m Y)R .
If A alg wins, the conditions (w1), (w2), (w3), and (w4) (described in Figure 7) are satisfied. In that case, we define the following events:

-Event E 1 : G GPS 2 BG,A alg = 1 ∧ Ẽ works correctly.

-Event E 2 :

P * w2 [ X] = P v * [ X] -(P u * [ X] • X + P w * [ X] • Y) is the zero-polynomial. -Event E 3 : P * w3 [ X] = P w * [ X] -P u * [ X] • P f * [ X] is the zero-polynomial,
where the polynomials P * w2 [ X] and P * w3 [ X] are from the winning conditions (w2) and (w3), respectively.

Claim 3. Pr[E 1 ∧ E 2 ∧ E 3 ] = 0. Proof. Assume that E 1 ∧ E 2 ∧ E 3 happens. From P * w2 [ X] = 0, the equality P v * [ X] = P u * [ X] • X + P w * [ X]
• Y holds. We can see that the following coefficients are zero by equating the coefficients of monomials on both sides as follows:

-[u * |v k ] = 0 and [w * |v k ] = 0, ∀k ∈ {1, , , q 2 } (due to monomials of degree 3).

-[u * |g] = 0 and [w * |g] = 0 (due to X).

-[v * |u ] = 0, ∀ ∈ {1, ..., q 1 } (due to {R }). -[v * |g] = 0 (due to the constant). -[u * |u ] = [w * |u ] = 0, ∀ ∈ {q 2 + 1, , , ., q 1 } (due to {XR }), which shows that P u * [ X] = ∑ q 2 =1 [u * |u ]R and P w * [ X] = ∑ q 2 =1 [w * |u ]
R whose degrees should be all 1. In that case, E 3 ensures that the equality

P u * [ X]P f * [ X] = P * w [ X]
holds, implying that the degree of P f * must be 0 (i.e., it is a constant polynomial). We can thus consider

P f * [ X] = [ f * |g], which is now denoted by m * . Recall that P v * [ X] = ∑ q 2 =1 [v * |v ](X + m Y)R .
Based on these facts, the polynomial P * w2 [ X] can be rewritten as follows:

P * w2 [ X] = P v * [ X] -P u * [ X](X + P f * [ X]Y) = q 2 ∑ =1 c (X + m Y)R - q 2 ∑ =1 c (X + m * Y)R , where c = [v * |v ] = [u * |u ]. If {c } q 2
=1 are all 0, then P u * [ X] is the zero-polynomial, which is a contradiction to the condition (w1). Therefore, there must be at least one non-zero c k for some k ∈ {1, ..., q 2 }. Say only

c k = 0, in which case P * w2 [ X] = c k (m k -m * )YR k * .
By condition (w1), f * = 1 leads to m * = 0. Moreover, by condition (w4), m k = m * , eventually resulting in P * w2 [ X] = 0. This is the contradiction to the event [Z] = 0, which gives the following equality:

E 2 . Claim 4. Pr[E 1 ∧ ¬E 2 ] + Pr[E 1 ∧ E 2 ∧ ¬E 3 ] ≤ Adv SDL G,C + 7 p . Proof. If E 2 does not happen, C can build a univariate polynomial Q * w2 [Z]
Pr[E 1 ] = Pr[E 1 ∧ ¬E 2 ] + Pr[E 1 ∧ E 2 ∧ ¬E 3 ] + Pr[E 1 ∧ E 2 ∧ E 3 ] = Pr[E 1 ∧ ¬E 2 ] + Pr[E 1 ∧ E 2 ∧ ¬E 3 ] ≤ Adv SDL G,C + 7 p .
Using the fact that Pr

[E 1 ] = Pr[G GPS 2 BG,A alg = 1 ∧ Ẽ], we conclude that Adv GPS 2 BG,A alg = Pr[G GPS 2 BG,A alg = 1 ∧ ¬ Ẽ] + Pr[G GPS 2 BG,A alg = 1 ∧ Ẽ] ≤ Pr[¬ Ẽ] + Pr[G GPS 2 BG,A alg = 1 ∧ Ẽ] ≤ Adv SDL G,C + 3 p + Adv SDL G,C + 7 p = 2Adv SDL G,C + 10 p ,
as required.

4 Our Dynamic Group Signature Scheme

Idea Behind Removing Knowledge Extractors

We explain how we can eliminate knowledge extractors throughout our security analysis without resorting to a common reference string (CRS). We first recall that knowledge extractors were mostly required to prove the security notions of traceability and non-frameability. At a high level, our DGS scheme is based on a variant [START_REF] Kim | Practical dynamic group signature with efficient concurrent joins and batch verifications[END_REF] of the PS signature. For a signing key (x, y) ∈ Z 2 p , a signature on a (committed) message α ∈ Z p consists of (u, v = u x+αy , w = u α ) ∈ G 3 1 , which is also randomizable as it is the case with the original PS signature. The main difference with [START_REF] Pointcheval | Short randomizable signatures[END_REF] and common variants is that this signature is no longer generated from α or g α but from a tuple (g α , u, u α ) for some u that we will define below. In our DGS scheme, the issuer uses the secrets (x, y) to issue such a (modified) PS signature (especially, the v value) for a prospective user through a joining protocol.

Roughly speaking, breaking traceability requires an adversary to generate a new (modified) PS signature (u * , v * = (u * ) x+α * y , w * = (u * ) α * ), where α * has not been previously used by another user. To ensure that α is fresh during the joining protocol, we introduce an additional element f = g α and ask the user to provide a NIZK proof π 1 with respect to α in order to prove that f = g α and w = u α . Since g is a fixed public element, the issuer easily checks that f (and so α) is fresh at the time of joining. In the traceability proof, after checking the validity of π 1 and the freshness, the tuple ( f , u, w) is queried to the oracle O 2 provided by the GPS 2 problem to get the appropriate value v. As a valid tuple against the GPS 2 problem must contain the element f * = g α * we need to embed this element in our group signatures. In our construction, this will be done by adding an El Gamal encryption of this element, that is, a pair (c * 0 = g s , c * 1 = f * D s 1 ) for some public D 1 and random secret s. An interesting outcome of this additional pair is that it leads to constant time opening if one sets D 1 as the opener's public key.

At this stage, we get a signature consisting of (u

* , v * , w * , c * 0 , c * 1 , π 2 )
, where π 2 is a NIZK proof ensuring that every element is well formed. If the adversary breaks traceability and thus generates an untraceable signature with respect to a new f * = g α * , then we can obtain a new (modified) PS signature (u * , v * = (u * ) x+α * y , w * = (u * ) α * ) and the relevant f * . Especially, f * is easily recovered, since the opener is assumed to be partially corrupted in the traceability game. The relation v * = (u * ) x+α * y comes from the pairing equation test as in the PS signature, and the relations w * = (u * ) α * and f * = g α * come from the (statistical) simulation soundness of the NIZK proof π 2 . The important point is that, during the above analysis, neither extracting α * nor α * itself are required, so that we can obtain a new and valid forgery of the (modified) PS signature without extracting the witnesses. Eventually, this allows us to remove knowledge extractors from the traceability proof.

In the case of the non-frameability game, the adversary is asked to generate a signature that GOpen links back to some user without knowing this user's secret α * . As explained in the introduction, nonframeability of many existing DGS schemes in the ROM is proven under the hardness of the SDL problem. More specifically, the reduction extracts the discrete logarithm α * of the SDL problem by rewinding the adversary. Our idea behind removing knowledge extractors is to extend the element f = g α above (which essentially acts as the member's public key) with f 2 = h α , for some different (public) basis h. This means that a signature generated with α * now contains

(u * , w * = (u * ) α * , v * = (u * ) x (w * ) y , g s , f * D s 1 , f * 2 D s 2 , π 2 )
, where D 2 is another public key of the opener. Here again, π 2 proves consistency of the resulting signature and in particular that α * used to generate w * is such that f * = g α * and f * 2 = h α * . But now, using the lossy key technique, we can replace at some point in the proof the element f * 2 by some random element in G 1 . This cannot be detected by the adversary under the XDH G 1 assumption. Once this is done, the only way for the adversary to accuse the owner of α * of having produced a signature σ is to encrypt g α * and the random f * 2 while proving that both elements have the same discrete logarithm with respect to (g, h). This clearly breaks the (statistical) simulation soundness of π 2 , which is assumed to impossible. We can therefore prove non-frameability of our scheme without needing to rewind the adversary.

At first sight, our strategy to remove knowledge extractors has led us to add the elements

(g s , f * D s 1 , f * 2 D s
2 ) to our signature. However, we would like to stress that this does not really increase the size of our group signature as the latter must anyway contain an IND-CCA2 encryption of the signer's identifier to achieve constant time opening while being able to answer opening queries. In our setting, the most classical solution would be to use the Naor-Yung transformation [START_REF] Naor | Public-key cryptosystems provably secure against chosen ciphertext attacks[END_REF] on El Gamal ciphertexts, which would result in something similar to what we get with (g s , f * D s 1 , f * 2 D s 2 ) combined with π 2 . Actually, we are even more efficient than this generic transform as we use randomness-sharing of the ciphertext and merge the corresponding zero-knowledge proof with π 2 . This way, we get a scheme proven secure without knowledge extractor which is still competitive with the most efficient solutions from the state-of-the-art (see Section 6).

Non-Interactive Zero Knowledge Proofs

We employ NIZK proofs obtained by the Fiat-Shamir transformation [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] in the ROM, which do not require a CRS generation. These NIZK proofs are defined with a NP-language L R = {Y ∈ {0, 1} * |∃ω : (Y, ω) ∈ R}, where R ∈ {0, 1} * × {0, 1} * is an efficiently recognizable relation. If Y ∈ L R , then we call such a Y a true statement for a witness ω; otherwise, a false statement. We denote a NIZK proof π by π = NIZK{ω : (Y, ω) ∈ R}. Such a proof π is generated by the Prove(Y, ω) algorithm, and the Vf(Y, π) algorithm outputs 1 if Y is true for ω; otherwise, it outputs 0.

Let G 1 be a cyclic group of a type-3 bilinear group, and let H : {0, 1} * → Z p be a hash function. We use the following three NIZK instantiations that essentially rely on the well-known NIZK proof of a generalized representation [START_REF] Camenisch | Efficient group signature schemes for large groups (extended abstract)[END_REF] of discrete logarithms. For group elements in G 1 , our NIZK proofs are defined as follows:

• NIZK 1 for the relation

R 1 = { Y = (g, h, u, f 1 , f 2 , w), ω = α ∈ G 6 1 ×Z p } such that f 1 = g α ∧ f 2 = h α ∧w = u α . A proof π is composed of (c, s) ∈ Z 2 p , where c = H(Y, g k , h k , u k ) and s = k -cα for k ← $ Z p . If c = H(Y, g s f c 1 , h s f c 2 , u s w c ) holds, then π is valid. • NIZK 2 for the relation R 2 = { Y = ( ũ, g, h, D 1 , D 2 , w, c 0 , c 1 , c 2 ), ω = (α, s) ∈ G 9 1 × Z 2 p } such that w = ũα ∧ c 0 = g s ∧ c 1 = g α D s 1 ∧ c 2 = h α D s 2 . A proof is π = (c, s 1 , s 2 ) ∈ Z 3 p , where c = H(Y, ũk 1 , g k 2 , g k 1 D k 2 1 , h k 1 D k 2 2 ), s 1 = k 1 -cα and s 2 = k 2 -cs for k 1 , k 2 ← $ Z p .
The proof is valid only when c = H(Y, ũs 1 wc ,

g s 2 c c 0 , g s 1 D s 2 1 c c 1 , h s 1 D s 2 2 c c 2 ) holds.
• NIZK 3 for the relation

R 3 = { Y = (g, c 0 , c 1 , f 1 , f 2 , D 1 , D 2 ), ω = (d 1 , d 2 ) ∈ G 7 1 × Z 2 p } such that c 1 f -1 1 = c d 1 0 ∧ D 1 = g d 1 ∧ c 2 f -1 2 = c d 2 0 ∧ D 2 = g d 2 . A proof π = (c, s 1 , s 2 ) ∈ Z 3 p is computed by c = H Y, (c 1 f -1 1 ) k 1 , g k 1 , (c 2 f -1 2 ) k 2 , g k 2 , s 1 = k 1 -cd 1 and s 2 = k 2 -cd 2 for k 1 , k 2 ← $ Z p , and it is valid when c = H Y, (c 1 f -1 1 ) s 1 c c 0 , D s 1 1 g c , (c 2 f -1 2 ) s 2 c c 0 , D s 2 2 g c holds.
Notice that our NIZK proofs above are formalized as the true or false statements by which the simulation soundness property can be defined. According to the Faust et al.'s work (especially, Theorem 2 in [START_REF] Faust | On the nonmalleability of the fiat-shamir transform[END_REF]), under the assumption that H is modeled as a random oracle, those NIZK proofs satisfy the following properties: informally, (completeness) a proof generated by an honest prover should be verified successfully; (zero-knowledge) there is a zero-knowledge simulator S that, not knowing the witness, simulates a valid proof statistically indistinguishable from a real one; and (simulation soundness) a cheating prover is unable to generate a new proof for a false statement even when receiving simulated proofs for true or false statements. The latter property is proved in [START_REF] Faust | On the nonmalleability of the fiat-shamir transform[END_REF] without rewinding the adversary.

In our second construction, the second NIZK proof will be transformed into a signature variant of the NIZK proof by additionally including a message m into the hash function H. To avoid confusion, we denote this variant by sNIZK 2 {ω : (Y, ω) ∈ R 2 }(m) for a message m ∈ {0, 1} * . The group public key is gpk = (pp, ipk, opk).

Construction

UKg. User i obtains its key pair (upk i , usk i ) by running DSKg.

Join (i, usk i , gpk)

Iss (i, upk i , ik) α ← $ Z p f 1 = g α , f 2 = h α u = H( f 1 ), w = u α π 1 = NIZK 1 {(α) : f 1 = g α ∧ f 2 = h α ∧ w = u α } σ DS ← DSSig(usk i , f 1 || f 2 ) τ=( f 1 , f 2 ,u,w,π 1 ,σ DS ) ------------→
If f 1 is fresh and π 1 and σ DS are valid: GJoin. As shown in Figure 8, the user i and the issuer execute the group-joining protocol using the Join and Iss algorithms, respectively.

v = u x w y reg i = (i, τ) reg = reg ∪ {reg i } v ← ---------- Check e(v, ĝ) ? = e(u, X)e(w, Ŷ ) Store gsk i = (α, f 1 , f 2 , u, v, w)
1. Join: The user performs the following:

(1) After choosing α ← $ Z p , the user computes f 1 = g α , f 2 = h α , u = H( f 1 ) and w = u α .

(2) The proof π 1 is generated as

π 1 = NIZK 1 {(α) : f 1 = g α ∧ f 2 = h α ∧ w = u α } ∈ Z 2 p .
(3) The user obtains σ DS by running DSSig(usk i , f 1 || f 2 ).

(4) The tuple τ = ( f 1 , f 2 , u, w, π 1 , σ DS ) is sent to the issuer.

2. Iss: Given the above tuple, the issuer computes u = H( f 1 ) and checks that:

(1) f 1 has never appeared in a previous or current joining session.

(2) π 1 is valid with respect to (g, h, u, f 1 , f 2 , w).

(3) σ DS is valid on f 1 || f 2 under upk i .

(4) If all the above conditions are satisfied, it computes v = u x w y and adds reg i = (i, τ) to the list reg.

(5) v is sent to the user.

3. Join: If the following equation e(v, ĝ) = e(u, X)e(w, Ŷ ) holds, the user stores its group signing key

gsk i = (α, f 1 = g α , f 2 = h α , u, v = u x+yα , w = u α ) ∈ Z p × G 5 1 .
GSig. Given a message m to be signed, the user invokes this algorithm as follows:

1. It picks r ← $ Z p , and it computes ũ = u r , ṽ = v r and w = w r .

It uses

s ← $ Z p to compute (c 0 = g s , c 1 = f 1 D s 1 , c 2 = f 2 D s 2 ) ∈ G 3 1 . 3.
The proof π 2 is generated as

π 2 = sNIZK 2 {(α, s) : w = ũα ∧ c 0 = g s ∧ c 1 = g α D s 1 ∧ c 2 = h α D s 2 }(m) ∈ Z 3 p .
4. The group signature is σ = ( ũ, ṽ, w,

c 0 , c 1 , c 2 , π 2 ) ∈ G 6 1 × Z 3 p .
GVf. A verifier checks if a signature σ = ( ũ, ṽ, w, c 0 , c 1 , c 2 , π 2 ) is valid on a message m as follows:

1. It checks if π 2 is valid with respect to ( ũ, g, h, D 1 , D 2 , w, c 0 , c 1 , c 2 ) and m.

2. If so, it checks if e( ṽ, ĝ) = e( ũ, X)e( w, Ŷ ).

3. If all the above conditions hold, it outputs 1; otherwise, 0.

GOpen. Given a valid σ on a message m, the opener does the following:

1. For (c 0 , c 1 , c 2 ) in σ , it obtains f 1 = c 1 c -d 1 0 and f 2 = c 2 c -d 2 0 by using ok = (d 1 , d 2 ).
2. If there is no reg i = (i, τ) ∈ reg, where τ = ( f 1 , f 2 , u, w, π 1 , σ DS ) such that f 1 = f 1 , f 2 = f 2 and a valid π 1 with respect to (g, h, u, f 1 , f 2 , w), then it outputs ⊥.

3. If there is one more such {reg i }, then it outputs ⊥.

4. Otherwise, the proof π 3 is generated as

π 3 = NIZK 3 {(d 1 , d 2 ) : c 1 • f -1 1 = c d 1 0 ∧ D 1 = g d 1 ∧ c 2 • f -1 2 = c d 2 0 ∧ D 2 = g d 2 } ∈ Z 3 p .
5. It outputs the identity i along with Π = ( f 1 , f 2 , σ DS , π 3 ).

Security Proofs

Let L h , L c , L sk , L σ and L ch be initialized as empty sets. Let BG = (p, G 1 , G 2 , G T , g, ĝ, e) be published as a public parameter. For each security proof, we create a sequence of hybrid games where the original game G 0 is gradually changed into the final game G F .

Non-frameability

Theorem 5.1. Let H : {0, 1} * → G 1 be modeled as a random oracle. Our DGS is non-frameable under the zero-knowledge property of both NIZK 1 and sNIZK 2 , the simulation soundness of both sNIZK 2 and NIZK 3 , the EUF-CMA of DS, and the XDH G 1 assumption.

Proof. We show how to change G 0 into G F under the security properties of underlying primitives. We next show that, in G F , the probability that A breaks the non-frameability becomes zero.

• G 0 : This is the original non-frameability game G N f DGS,A . • G 1 : This is the same game as G 0 , except that C simulates NIZK 1 and sNIZK 2 proofs using the corresponding simulators. By the (statistical) zero-knowledge property of the NIZKs, G 0 is indistinguishable from G 1 .

• G 2 : This is the same game as G 1 , except that C aborts if A generates a proof of either sNIZK 2 or NIZK 3 on a false statement. By the (statistical) simulation soundness property of the sNIZK 2 or NIZK 3 , G 1 is indistinguishable from G 2 .

• G 3 : This is the same game as G 2 , except that C guesses a target (honest) user i * among the q number of the SndToU queries. C chooses k ← $ {1, . . . , q} and considers the k-th appeared identity in SndToU queries as i * . If A queries i * to USK oracle or outputs a forgery σ * that cannot be linked to i * , then C aborts. The probability that C does not abort is exactly 1/q.

• G 4 : This is the same game as G 3 , except that f * 1 = g α * and f * 2 = h α * initially stored in the i * -th entry reg * are not modified by WReg queries. Under the EUF-CMA property of DS, G 3 is indistinguishable from G 4 .

• G F : This is the same game as G 4 , except that reg i * now contains a pair

( f * 1 , f * 2 ) such that log g f * 1 = log h f * 2 .
Since G 2 we have excluded proofs of false statements. Therefore, a successful adversary against nonframeability must have produced a group signature σ * along with a proof Π * such that σ * contains an El Gamal encryption of ( f * 1 , f * 2 ) (otherwise GJudge would reject Π * ).

σ * contains a proof that log g f *

1 = log h f * 2 .
As it is impossible to fulfil both requirements, A cannot succeed in this last game.

Claim 1: Under the XDH G 1 assumption, G 4 is indistinguishable from G F .
Proof of Claim 1. Let (g, A = g a , B = g b , T ) be an instance of the XDH G 1 problem. C first sets up the public parameter that includes h = H(g) as it is in the real scheme, and then receives ipk = ( X, Ŷ ) and opk = (D 1 , D 2 ) from A. All oracle queries are managed by C as follows:

-Hash-H. For a new input n ( = g), C chooses δ n ∈ Z p and computes µ = g δ n . For the special input g, C sets H(g) = B = h, leading to µ = B. C returns µ and adds either (n, δ n , µ) or (g, ⊥, µ) to L H . If n has queried before, C returns µ stored in L H .

Traceability

Theorem 5.3. Let H : {0, 1} * → G 1 be modeled as a random oracle. Our DGS is traceable under the simulation soundness of both NIZK 1 and sNIZK 2 and the GPS 2 assumption.

Proof. In the following hybrid argument, we aim to show that the probability that A breaks the traceability becomes zero in the last game G F .

• G 0 : This is the original traceability game G Trace DGS,A . • G 1 : This is the same game as G 0 , except that C aborts if a proof of a false statement is generated for NIZK 1 or sNIZK 2 . Because of the (statistical) simulation soundness of these NIZKs, G 0 is indistinguishable from G 1 .

• G 2 : This is the same game as G 1 , except that C aborts if the proof Π generated by GOpen for some identity i( = ⊥) is rejected by GJudge.

Claim 1: G 1 is identical to G 2 .
As we assume that GOpen does not return ⊥, it necessarily returns Π = ( f 1 , f 2 , σ DS , π 3 ) accusing i (we recall that GOpen is always invoked honestly in the traceability game). As NIZK 3 has perfect completeness, the first condition tested by GJudge holds. Moreover, an invalid signature σ DS on f 1 || f 2 would have been rejected by C during the corresponding AddU or SndToI queries. Therefore, Π also passes the second test of GJudge, which concludes our proof.

• G F : This is the same game as G 2 , except that GOpen never outputs ⊥ when run on a valid group signature. In G F , the probability that A breaks traceability is zero. Claim 2: Under the GPS 2 assumption, G 2 is indistinguishable from G F .

Proof. We show that C can solve the GPS 2 problem using A. For generators g ∈ G 1 and ĝ ∈ G 2 , C is given an instance of the GPS 2 problem as the tuple ( X, Ŷ ) equipped with the O GPS Then, the issuer's secret key is implicitly set as ik = (x, y) such that X = ĝx and Ŷ = ĝy . C sends gpk and ok to A. All oracle queries are managed as follows:

-Hash-H. For an input n where n ∈ G 1 , if n is new, C obtains µ ∈ G 1 by calling O GPS 2 1 . Then, µ is returned as output, and (n, µ) is added to L H . If n was queried before, C returns µ stored in L H .

-AddU. For a queried i, C initializes the honest user i by generating (usk i , upk i ). To generate gsk i without knowing ik, C computes f 1 = g α , f 2 = H(g) α , u = H( f 1 ) and w = u α , where α ← $ Z p . In addition, C simulates a proof π 1 with respect to α. C sends ( f 1 , u, w) to O GPS and obtains v = u x w y . C then sets gsk = (α, f 1 , f 2 , u, v, w) and reg i = (i, τ), where τ = ( f 1 , f 2 , u, w, π 1 , σ DS ). In the end, C sends upk i to A. The list L h is updated by adding i.

-CrptU. For a queried (i, upk), C initializes the dishonest user i by setting the user pubic key of i as upk.

The list L c is updated by adding (i, cont).

-SndToI. For a queried i such that (i, cont) ∈ L c , C executes the GJoin protocol without ik. Given a tuple ( f 1 , f 2 , u, w, π 1 , σ DS ) from A, C checks the freshness of f 1 and also checks that π 1 and σ DS are both valid. If so, α = log g f 1 = log u w holds for some unknown α, because of the simulation soundness of or traceability security analyses. All their non-frameability proofs are justified under the hardness of some computational problems such as the (S)DL [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF][START_REF] Libert | Practical "signatures with efficient protocols" from simple assumptions[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF] or the co-Diffie-Hellmam Inversion [START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF], and like the security analysis of the Schnorr signature, the witness used as the user secret key must be extracted as the solution of their underlying computational hardness problem. Furthermore, regarding the traceability proofs, BCN+10, LMP+16, and PS16 require sequential O(q) rewinding extractions for dealing with O(q) joining queries that are issued by an adversary. However, in case of DP06, DS18, and KLA+20, such sequential O(q) extractions are ruled out by respectively employing a straight-line extractable commitment [START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF], a structure-preserving signature on equivalence classes [START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF], and a new assumption that is redefined as the GPS 1 assumption in this paper.

Regarding a common reference string (CRS), DP06, DS18, CS20 and CS20* need a CRS that has an embedded trapdoor during their security analyses. More concretely, a CRS in DP06 is necessary to remove sequential O(q) rewinding extractions resulting from joining queries, thereby forcing a prospective user to use an extractable commitment based on the CRS. However, in the case of a subverted CRS, the entity possessing the trapdoor can possibly extract the witness as the user secret key. A CRS in DS18 is used to provide full anonymity (CCA2), by forcing a signer to generate an El Gamal encryption based on the CRS. This means that in the subversion of a CRS, the entity with the trapdoor (i.e., the El Gamal decryption key) can extract user-specific opening information from the El Gamal ciphertext and identify the signer without the opener's secret key. The CRS in CS20 and CS20* is essential for proving non-frameability, by forcing a signer to use two CRS elements (X = g x , X = gx ) based on the CRS. In case of a subverted CRS, however, the entity knowing the discrete logarithm x can forge a signature on an arbitrary message, given a valid signature generated by a target user. As a result, those CRS-based DGS schemes work securely only in contexts where CRS subversion never happens.

We recall that opening soundness, introduced in [START_REF] Sakai | On the security of dynamic group signatures: Preventing signature hijacking[END_REF], is the property satisfied by schemes whose group signatures cannot be opened to two distinct users. The soundness is weak if this property only holds for honest users. Essentially, a scheme is opening sound if a user secret key cannot be shared by different users. 5 For most schemes, this can be achieved by checking the freshness of the user's key at the joining time. The case of DS18 and CS20 is more complex as certificates are issued on equivalence classes, which makes key sharing more difficult to detect. Comparing DGS security models, DP06, LMP+16, DS18, KLA+20, and CS20* are all based on either the BSZ model [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] or the KY model [START_REF] Kiayias | Group signatures with efficient concurrent join[END_REF] that considers a dynamic group and separable group managers. In particular, our scheme is proven to be secure in the security model, denoted by 'BSZ*' [START_REF] Bootle | Foundations of fully dynamic group signatures[END_REF], which captures the stronger security than the BSZ by allowing an adversary to generate group managers' keys maliciously. BCN+10, PS16, and CS20 are proven in the weaker model as denoted by BMW* and placed between [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF] and [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF], where dynamic joining is allowed but the group managers are not separated. Regarding anonymity, DP06, LMP+16, DS18 and CS20* provide fully anonymity (CCA2), meaning that a target signature is anonymous even though the signing key of the target user is given to the adversary. In DCN+10, PS16, KLA+20, and our scheme, leaking such a signing key leads to breaking anonymity so that a slightly weaker notion (CCA-) called selfless anonymity is justified by disallowing USK (i.e., user secret key) queries for the target user. CS20 also provides selfless anonymity. For traceability proofs, only LMP+16 relies on the standard SXDH assumption. BCN+10, PS16, KLA+20, and our scheme are all based on the interactive LRSW, PS, GPS 1 , and GPS 2 assumptions, respectively, but notably the LRSW, PS, GPS 1 and GPS 2 (Section 3.2) assumptions in the AGM are all proven to be at least as hard as the standard SDL assumption [START_REF] Bauer | A classification of computational assumptions in the algebraic group model[END_REF]. DP06 is based on the q-SDH assumption, which is still implied by the non-standard q-DL assumption even in the AGM [START_REF] Bauer | A classification of computational assumptions in the algebraic group model[END_REF]. Also, DS18, CS20, and CS20* rely on a signature scheme whose security is proven directly in the generic group model (GGM).

Figure 2 :

 2 Figure 2: Anonymity game for DGS

Figure 3 :

 3 Figure 3: Non-frameability game for DGS

Figure 4 :

 4 Figure 4: Traceability game for DGS

Figure 5 :

 5 Figure 5: Relations between GPS assumptions

2 with 2 .

 22 ( f , u, w), and then C 1 relays the tuple to O GPS 2 Clearly, such a ( f , u, w) should be valid for both O GPS 12 and O GPS 2 2 as long as the query from A 0 valid. If O GPS 2 2 returns v, then A 0 and C 0 can receive v from their respective challengers. In the end, A 0 outputs (u * , v * , m * ) ∈ G 2 1 × Z p . If A 0 wins, then C 0 can send a valid output to C 1 by forwarding the tuple. From this, C 1 obtains f * = g m * and w * = u * m *

Figure 6 :

 6 Figure 6: Description of GPS i problems

Lemma 3 . 5 (

 35 Lemma 2.1 in[START_REF] Bauer | A classification of computational assumptions in the algebraic group model[END_REF]). Let P[ X] ∈ Z p [X 1 , ..., X ] be a non-zero multivariate polynomial of the total degree d ∈ N, and letQ[Z] ∈ Z p [Z] be a univariate polynomial generated as P[S 1 Z + T 1 , ..., S Z + T ].Then, the coefficient of the maximal degree of Q[Z] is a polynomial in Z p [S 1 , ..., S ] of degree d.

Figure 7 :

 7 Figure 7: GPS 2 problem in the AGM

2 .

 2 It computes D 1 = g d 1 and D 2 = g d 2 .3. The opener's secret and public keys are ok = (d 1 , d 2 ) ∈ Z 2 p and opk = (D 1 , D 2 ) ∈ G 2 1 , respectively.

Figure 8 :

 8 Figure 8: Overview of the GJoin protocol

2

 2

1 and O GPS 2 2

 12 oracles as described in Section 3. C first sets gpk = (h = H(g), D 1 = g d 1 , D 2 = g d 2 , X, Ŷ ) and ok = (d 1 , d 2 ), where d 1 , d 2 ← $ Z p .

2

 2

2

 2

π 1 .

 1 With this fact, C sends the tuple ( f 1 , u, w) to O GPS 2 2 and obtains v = u x w y . Note that u is obtained from O GPS 2 1 on input f 1 . C finally sends v to A.

  GPS 2 =⇒ GPS 1 =⇒ GPS 0 =⇒ PS

	Th. 3.6	Lem. 3.1	Lem. 3.1	Lem. 3.2
	SDL =⇒ (alg)

  by changing the variables of P * w2 into sZ +t for some s,t ∈ Z p . By a similar argument to the proof of Claim 2, we see that Q * w2 (z) = 0 because of the condition (w2), and thus one of the roots of the polynomial Q * w2 [Z] has to be the solution of the SDL problem. In addition, by lemmas 3.4 and 3.5, the probability that Q * As long as C does not abort, C can obtain the solution z of the SDL problem by finding roots of Q * w2 [Z] = 0 or Q * w3

	w2 [Z] = 0 (i.e., C aborts) is at most 3 p .
	Similarly, if P * w3 [ X] = 0 (i.e., if E 3 does not occur), then the non-zero polynomial Q * w3 [Z] gives the SDL solution with a probability of at least 1 -4 p . That is, C aborts with a probability of 4 p at most. Thereby, in
	both cases, we have Pr[C aborts] ≤ 7 p .

For simplicity, we omit λ in related notation throughout this paper.

As explained in the Section 1.2, we do not want a full-fledged structure-preserving signature as it would expose us to the associated negative results[START_REF] Abe | Optimal structure-preserving signatures in asymmetric bilinear groups[END_REF] such as the impossibility of unilateral signatures (that is, signatures only containing elements of G 1 ).

In[START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF], the authors mentioned that the KEA holds in the AGM, but a concrete reduction was not provided.

According to Bellare et al.[START_REF] Bellare | Nizks with an untrusted CRS: security in the face of parameter subversion[END_REF], our setup algorithm can be non-trusted if a bilinear-group generation algorithm is deterministic and public. Also, the element h is computable by anyone and thus publicly verifiable from the generated bilinear group.

It outputs 1 if all the above conditions hold; otherwise, 0.It is easy to see that our DGS works correctly because of the completeness of the NIZKs and the correctness of the (variant of) PS signature and DS. In addition, as in[START_REF] Kim | Practical dynamic group signature with efficient concurrent joins and batch verifications[END_REF], our DGS scheme can provide pairing-batch computations (i.e., the pairing equation of Step 2 in GVf can be batched) to verify n group signatures from distinct signers. We omit the details of the correctness and the pairing-batch verification algorithm in this paper.

This notion is slightly different from that of[START_REF] Sakai | On the security of dynamic group signatures: Preventing signature hijacking[END_REF].

-SndToU. For i = i * , C obtains a pair (usk i , upk i ) by DSKg. While executing the GJoin protocol, i's secret α ← $ Z p is chosen by C. At the end of the protocol, C obtains gsk i = (α, f 1 , f 2 , u, v, w). For i = i * , C implicitly sets α * = a = log g A and sends A the following tuple:

where π * 1 is a simulated proof with respect to the unknown α * , and σ * DS is a digital signature on the message f * 1 || f * 2 . After A sends v * to C in response to the tuple, C stores gsk i * = (⊥, f * 1 , f * 2 , u * , v * , w * ). Note that if T = g ab , log g f * 1 = log h f * 2 , which is G 4 , and if T = g ab , log g f * 1 = log h f * 2 , which is G F . Finally, the list L h is updated by adding i.

-USK. For i = i * , C returns (usk i , gsk i ) and updates L sk by adding i.

-Sig. For i = i * , C uses gsk i to generate σ on m as is the case in the real scheme, except for a simulated proof π 2 . For i = i * , C computes ((u * ) r , (v * ) r , (w * ) r ) by using gsk i * and r ← $ Z p . In addition, it computes c 0 = g s , c 1 = A • D s 1 and c 2 = T • D s 2 for the randomly chosen s ← $ Z p . Then, σ contains those values along with π 2 that is a simulated proof. Note that the returning σ passes the GVf algorithm and is opened with reg i * even though T is random. Finally, the list L σ is updated by adding (i, m, σ ).

A finally outputs (m * , σ * , i * , Π * ), where σ * = ( ũ * , ṽ * , w * , c * 0 , c * 1 , c * 2 , π * 2 ) and Π * = ( f * 1 , f * 2 , σ * DS , π * 3 ). If T = g ab , C simulates G 4 ; otherwise, C simulates G F . Any change of behaviour of A can thus be used to break the XDH G 1 assumption.

We now show that A can never win the security game in G F . Depending on whether either π * 2 or π * 3 is valid, there are two possible cases of the forgery: In that case, for the values

respect to the witness d 2 . We notice that even though A knows the witness d 2 , the simulation-soundness property of NIZK 3 means that it is statistically infeasible for A to generate a valid proof π 3 for a false statement.

(2) Case when π * 3 is valid: Because of the simulation-soundness of NIZK 3 , the validity shows that c *

In that case, for the values

Overall, if A is an adversary succeeding against the non-frameability of our construction with probability ε = Adv N f DGS,A , then we have proven the following bound:

where Adv ZK (s)NIZK,A resp. Adv SS (s)NIZK,A is the advantage of A against the zero-knolwedge property (resp. the simulation soundness) of (s)NIZK, Adv EUF-CMA DS,A is the advantage of A against the unforgeability of the signature scheme DS and finally Adv XDH G 1 ,A is the advantage of A against the XDH G 1 assumption.

True or False Any/any ok Original Game G Anon-0

True or False Any/any ok Zero-knowledge

True Any/any ok Simulation-soundness

Anonymity

Theorem 5.2. Let H : {0, 1} * → G 1 be modeled as a random oracle. Our DGS is anonymous under the zero-knowledge of all NIZKs, the simulation soundness of sNIZK 2 , DGS non-frameability, and the XDH G 1 assumption.

Proof. As shown in Table 1, we begin with G 0 that is the original game of G Anon-0 DGS,A . At the end, we arrive at G F where the challenged σ * is valid for both i * 0 and i * 1 . Thus, from the adversary standpoint, the signature σ * becomes perfectly indistinguishable. Note that it is required to create a sequence of the next hybrid games in order to change G F into the original game of G Anon-1 DGS,A . However, we omit the details because it is easy to consider it by reversing the first hybrid games.

• G 0 : This is the original game G Anon-0 DGS,A with respect to the target identity i * 0 , where the challenge signature

is generated under the group signing key of i * 0 . • G 1 : This is the same as G 0 , except that C simulates all proofs of the NIZKs without witnesses. By the (statistical) zero-knowledge property of all NIZKs, G 0 is indistinguishable from G 1 .

• G 2 : This is the same as G 1 , except that C aborts if A produces a proof of sNIZK 2 on a false statement. By the (statistical) simulation soundness property of the sNIZK 2 , G 1 is indistinguishable from G 2 .

• G 3 : This is the same as G 2 , except that C guesses target identities i * 0 and i * 1 that will be queried to the CH b oracle. Let q be the number of the SndToU queries. C picks k 0 , k 1 ← $ {1, ..., q} and then considers the k 0 -th (and k 1 -th) appeared identity in SndToU queries to be i * 0 (and i * 1 , respectively). If the guess of C is wrong, then C aborts but this reduces the overall advatange by a factor, at worse, 1/q 2 .

• G 4 : This is the same as G 3 , except that A is not allowed to create a new valid signature for i * 0 and i * 1 without going through the Sig oracle. This means that C is able to answer opening oracle queries with respect to i * 0 and i * 1 using only the list

By the DGS non-frameability (Theorem 5.1), G 3 is indistinguishable from G 4 .

• G 5 : This is the same as G 4 , except that the element c * 2 of σ * = ( ũ * , ṽ * , w * ,

and X, Ŷ are output by A so that ok = (d 1 , ⊥). C then sends opk to A, and all oracles are handled as follows:

-Hash-H. If a new n is queried as input, C chooses δ n ∈ Z p and computes µ = g δ n . C returns µ and adds (n, δ , µ) to L H . If n has queried before, C returns the µ stored in L H .

-SndToU. For any i (including i * 0 and i * 1 ), C obtains a key pair (usk i , upk i ) from UKg and chooses a random α i ← $ Z p . C invokes the Join algorithm except that π 1 is simulated by using the zero-knowledge simulator S. C finally stores gsk i . The list of honest users L h is updated by adding i.

-USK. As a queried i must not be i * 0 and i * 1 , C can send (usk i , gsk i ) for all queries. C updates L sk by adding i.

-WReg. For a queried i and ρ, C sets reg i = ρ.

-Sig. For all i ∈ L h , C uses α i to generate σ on a message m by performing GSig, except when simulating π 2 . The list L σ is updated by adding (i, m, σ ).

-Open. To answer an opening query about σ = (u, v, w, c 0 , c 1 , c 2 , π 2 ), C first uses L σ for i * b , where b ∈ {0, 1}, by checking whether or not (i * b , m, σ ) ∈ L σ . If not, for other identities, C uses only the d 1 , which it knows, by checking whether or not f 1 = c 1 c d 1 0 is included in some reg i ∈ reg. Note that f 1 and f 2 are bounded to the secret exponent α i by the simulation soundness of π 2 . Namely, f 1 and f 2 never indicate different users.

-CH 0 . Given challenge identities i * 0 , i * 1 and m * , C uses ok = (d 1 , ⊥) and • G 6 : This is the same as G 5 , except that the element c *

Proof. The proof is almost analogous to the preceding proof for G 4 ≈ G 5 , except that d 1 is implicitly set as a = log g A of an XDH G 1 instance (g, A = g a , B = g b , T ), and d 2 ← $ Z p is now chosen at random by C. With this setting, when SndToU(i) is called for any i, C uses a key pair (usk i , upk i ) generated by UKg and α i ← $ Z p to execute the Join algorithm, in which π 1 is simulated. For all i (including i * 0 and i * 1 ) ∈ L h , C is able to respond to all USK (unless either i * 0 or i * 1 is queried) and Sig queries by using α i . C now uses L σ and d 2 to deal with Open queries. This is also valid due to the simulation soundness of π 2 .

In CH 0 , C having

implicitly sets the random exponent as s * = log g B for the challenge signature

where r * ← $ Z p , R ← $ G 1 and the proof π * 2 is simulated. If T = g ab , C simulates G 5 ; otherwise, C simulates G 6 . Thus, the ability of A to distinguish between G 5 and G 6 can be transformed into the ability of C to solve the XDH G 1 problem.

• G 7 : This is the same as G 6 , except that, when C generates τ

Proof. Let (g, A = g a , B = g b , T ) be an XDH G 1 instance that C is given. C sets h = g δ g for some random scalar δ g and the opener key pair as ok = (d 1 , d 2 ) and opk = (

, where d 1 , d 2 ← $ Z p . It receives the issuer's public key ipk = ( X, Ŷ ) from A. All oracles are managed as follows:

-Hash-H. If a new n is queried as input, C chooses δ n ∈ Z p and computes µ = g δ n . C returns µ and adds (n, δ n , µ) to L H . If n has queried before, C returns µ stored in L H .

-SndToU. If i = i * 0 , C invokes the Join algorithm by obtaining a key pair (usk i , upk i ) from DKg and choosing its secret α ← $ Z * p , except for simulating a proof π 1 . If i = i * 0 , C simulates the proof π * 1 with respect to the following elements:

Here, u i * 0 = H( f * 1 ) is set as B by programming the random oracle accordingly. This defines the unknown α * 0 as a = log g A. Note that if T = g ab , w i * 0 = (u i * 0 ) α * 0 . Otherwise, if T = g ab , then β * = log u i * 0 w i * 0 is set as a random value distinct from α * 0 . A is given the above elements along with (π * 1 , σ * DS ), where σ * DS is a digital signature on the message f * 1 || f * 2 . In response to those elements, C receives a relevant v i * 0 which satisfies e(v i * 0 , ĝ) = e(u i * 0 , X)e(w i * 0 , Ŷ ). C finally stores gsk = (α, f 1 , f 2 , u, v, w) for i = i * 0 , and it stores

The list of honest users L h is updated by adding i. -USK. As a queried i must not be either i * 0 or i * 1 , C can send (usk i , gsk i ) for all queries. C updates L sk by adding i.

-WReg. For a queried i and ρ, C sets reg i = ρ.

-Sig. For any i, C can generate σ on a message m by performing GSig and simulating the proof π 2 therein.

The list L σ is updated by adding (i, m, σ ).

-Open. C uses either L σ or ok to answer an opening query.

where r * ← $ Z p and R 0 , R 1 , R 2 ← $ G 1 , and π * 2 is a simulated proof. The list L ch is updated by adding

and otherwise, C simulates G 7 . Thus, the ability of A to distinguish between G 6 and G 7 can be transformed into the ability of C to solve the XDH G 1 problem.

• G 8 : This is the same as G 7 , except that, when C deals with SndToI(i * 1 ), the value

Proof. A simulation of C is the same as that of G 6 ≈ G 7 , except for the following case in SndToU(i):

, where δ g and δ f * 1 are random values associated with

) is given to A where π 1 is a simulated proof, and σ DS is a digital signature on f 1 || f 2 . Under this simulation, if T = g ab , C simulates G 7 , and otherwise, C simulates G 8 . Therefore, the ability of A to distinguish between G 7 and G 8 can be transformed into the ability of C to solve the XDH G 1 problem.

• G F : This is the same as G 8 , except that, in response to SndToI(i * 0 ) and SndToI(i * 1 ), C sets the same exponent γ * such that log u i * 0

The same exponent γ * in G F shows that the values ( ũ * , ṽ * , w * ) of σ * could be possibly computed by the group signing key for i * 0 and i * 1 with the same possibility. Claim 5. Under the XDH G 1 assumption, G 8 is indistinguishable from G F .

Proof. Given an XDH G 1 instance (g, A = g a , B = g b , T ), C first receives issuer's public key ipk = ( X, Ŷ ) that is generated by A. Then, C generates an opener key pair (ok, opk) to provide A with opk. All oracles are managed as follows:

-Hash-H. If a new n is queried as input, C chooses δ n ∈ Z p and computes µ = g δ n . C returns µ and adds (n, δ n , µ) to L H . If n has queried before, C returns µ stored in L H .

-SndToU. For each query i, C first obtains a key pair (usk i , upk i ) by running DKg. To execute Join, C works as follows. If i = i * 0 , C generates a simulated proof π * 1 with respect to the elements:

where α * 0 ← $ Z p and h = g δ g and B = u i * 0 = g

. Note that δ f * 1 and β * are implicitly set as unknown exponents δ f * 1 = b = log g B and β * = log B T , respectively. If i = i * 1 , C sets γ * as a = log g A, to which the proof π 1 is generated with respect to the values:

,

, such a tuple is computed by α i ← $ Z p as it is in the real scheme. The list L h is updated by adding i.

The list L sk is updated by adding i. -WReg. For all i and ρ, C sets reg i = ρ.

-Sig. For all i, C can respond to A by invoking GSig, except for simulating π 2 . The list L σ is updated by adding (i, m, σ ).

-Open. C uses either L σ or ok to answer an opening query.

-CH 0 . For challenge identities i * 0 , i * 1 and m * , C generates the challenge signature

where r * ← $ Z p and R 0 , R 1 , R 2 ← $ G 1 , and π * 2 is a simulated proof. The list L ch is updated by adding (i * 0 , m * , σ * ) and (i * 1 , m * , σ * ). If T = g ab , we see that β * = γ * , where C simulates G 8 . Otherwise, if T = g ab , we see that β * = γ * and C simulates G F . The ability of A to distinguish between G 8 and G F can then be transformed into the ability of C to solve the XDH G 1 problem.

To conclude the proof, we note that, in G F , the certificate ( ũ * , ṽ * , w * ) contained in σ * is valid for both users i * 0 and i * 1 . The other elements of σ * are the random (since

1 and the NIZK proof π * 2 that do not carry any information about i * 0 or i * 1 . The advantage of an adversary in this game is then, at best, negligible. Overall, if A is an adversary succeeding against the anonymity of our construction with probability ε = Adv Anon DGS,A , then we have proven the following bound:

where Adv ZK (s)NIZK,A resp. Adv SS (s)NIZK,A is the advantage of A against the zero-knolwedge property (resp. the simulation soundness) of (s)NIZK, Adv N f DGS,A is the advantage of A against the non-frameability of DGS and finally Adv XDH G 1 ,A is the advantage of A against the XDH G 1 assumption.

-USK. For a user i as input, C outputs gsk i and usk i . The list L sk is updated by adding i.

-RReg. For a user i as input, C outputs reg i .

A finally outputs a forgery σ

Here, the simulation soundness of π * 2 leads to the equality of discrete logarithms such that w * = (u * ) α * , f * 1 = g α * and f * 2 = h α * for some unknown α * , where f * 1 and f * 2 are obtained by c * 1 (c * 0 ) d -1 1 and c * 2 (c * 0 ) d -1 2 , respectively. If A wins, σ * is valid (i.e., e(u * , X)e(w * , Ŷ ) = e(v * , ĝ)) but the opening of σ * fails, which is the only distinction between G 2 and G F . The opening failure indicates that, for all (

. Based on this fact, C outputs ( f * 1 , u * , v * , w * ) as a solution for the GPS 2 problem. Overall, if A is an adversary succeeding against the traceability of our construction with probability ε = Adv Trace DGS,A , then we have proven the following bound:

where Adv SS (s)NIZK,A is the advantage of A against the simulation soundness of (s)NIZK, and Adv GPS 2 BG,A is the advantage of A against the GPS 2 assumption.

Comparison

Tables 2 and 3 provide a comparison between previous DGS schemes and ours in terms of security and efficiency, respectively. In the comparison, we consider several well-known practical DGS schemes proven in the random oracle model (ROM), including DP06 by Delerablée and Pointcheval [START_REF] Delerablée | Dynamic fully anonymous short group signatures[END_REF], BCN+10 by Bichsel et al. [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF], PS16 by Pointcheval and Sanders [START_REF] Pointcheval | Short randomizable signatures[END_REF], LMP+16 by Libert et al. [START_REF] Libert | Practical "signatures with efficient protocols" from simple assumptions[END_REF], DS18 by Derler and Slamanig [START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF], and KLA+20 by Kim et al. [START_REF] Kim | Practical dynamic group signature with efficient concurrent joins and batch verifications[END_REF]. We additionally consider the very recent CS20 and CS20* by Clarisse and Sanders [START_REF] Clarisse | Group signature without random oracles from randomizable signatures[END_REF], which can be proven secure without ROM. • Rew. Ext. stands for Rewinding Extraction.

• q is the number of queries to the Join oracle in the traceability proof.

• ⇒ alg represents the algebraic reduction via the AGM.

As shown in Table 2, we emphasize that the security of CS20, CS20*, and our schemes can be proven without any rewinding extraction, meaning that these are free from the rewinding problems. In contrast, the other DGS schemes require at least one or more rewinding extractions in either their non-frameability • For i ∈ {1, 2, T }, E i indicates an exponentiation in G i .

• P is a pairing operation. • N is the number of users in DGS.

Table 3 illustrates that our DGS scheme has comparable efficiency. We emphasize that, except for CS20, CS20* and our schemes, the efficiency of all other schemes should be considered by taking into account the fact that they use knowledge extractors, which eventually causes security degradation. Regarding computational cost, our GSig algorithm only requires 12 exponentiations in G 1 , and our GVf algorithm requires 3 pairing operations plus 10 exponentiations in G 1 . In particular, contrarily to CS20 and CS20*, we manage to keep all signer's computations in G 1 , which avoid implementing the complex arithmetic of G 2 . Similarly, one must take into account that the elements of G 2 are at least twice as large as those in G 1 for usual type-3 curves like BN [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF]. Finally, we achieve constant time (and fast) opening contrarily to schemes that exclusively use rerandomizable signatures.