Rémi Clarisse

Olivier Sanders

Group Signature without Random Oracles from Randomizable Signatures

Group signature is a central tool for privacy-preserving protocols, ensuring authentication, anonymity and accountability. It has been massively used in cryptography, either directly or through variants such as direct anonymous attestations. However, it remains a complex tool, especially if one wants to avoid proving security in the random oracle model. In this work, we propose a new group signature scheme proven secure without random oracles which significantly decreases the complexity in comparison with the state-of-the-art. More specifically, we halve both the size and the computational cost compared to the most efficient alternative in the same model. Moreover, our construction is also competitive against the most efficient ones in the random oracle model. Our construction is based on a tailored combination of two popular signatures, which avoids the explicit use of encryption schemes or zeroknowledge proofs while signing. It is flexible enough to achieve security in different models and is thus suitable for most contexts.

Introduction

Group Signature, introduced by Chaum and van Heyst [START_REF] Chaum | Group signatures[END_REF], enables members of a group to sign on behalf of the group. The point is that the signature is anonymous, i.e. it cannot be traced back to its issuer, except for a specific entity, the opening authority, which can "open" any valid group signature.

Related Works. Combining seemingly contradictory properties such as authentication and anonymity has proved tricky, the first really practical solution being provided by Ateniese et al. [START_REF] Ateniese | A practical and provably secure coalition-resistant group signature scheme[END_REF]. Few years later, Bellare, Micciancio and Warinschi [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF] proposed the first security model (BMW model) for static group signature, which was later extended to the case of dynamic group signature by Bellare, Shi and Zhang [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] (BSZ model). Besides providing a way to assess existing schemes, these seminal works have introduced a generic construction that has become the implicit framework for most of the following group signatures.

Informally, a group member of this generic construction receives from a socalled group manager a certificate (a digital signature) τ on his public key pk when he joins the group. To compute a group signature on some message m, he first generates a digital signature σ on m (using the corresponding signing key sk) and then encrypts σ and τ . Finally, he provides a non-interactive zeroknowledge (NIZK) proof that every element is well formed. This three-steps approach is usually known as Sign-Encrypt-Prove (SEP) in the literature.

The strength of the SEP paradigm is that it is based on standard cryptographic primitives for which many instantiations exist. Unfortunately, it leads to quite complex constructions because of the security requirements placed on each building block, but primarily because of the complexity of the resulting NIZK proof. Indeed, the signer must prove, without revealing σ and τ , that the group signature is a valid encryption of the signature σ that has been generated using keys certified by the group manager. Such a statement is difficult to prove and this becomes worse if one wants to achieve security without relying on the random oracle model (ROM). Indeed, NIZK proofs are much more complex outside this setting and even by using the Groth-Sahai methodology [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], group signatures still contain dozens of elements (see e.g. [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF]).

A natural question arising from this observation is whether it is possible to construct more efficient schemes by using a different paradigm. Bichsel et al. [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF] proposed an interesting answer to this question. They indeed introduced a very efficient alternative, at the cost of a slightly weaker notion of anonymity. This allows them to circumvent the result of Abdalla and Warinschi [START_REF] Abdalla | On the minimal assumptions of group signature schemes[END_REF] and thus to avoid encryption. More specifically, their idea was to remove encryption by using re-randomizable [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF] certificates τ and by merging σ with the NIZK proofs, leading to a signature of knowledge. The resulting construction is very efficient (see Table 4 at the end of the paper) and can be further improved by instantiating it with the randomizable signature scheme of Pointcheval and Sanders (PS) [START_REF] Pointcheval | Short randomizable signatures[END_REF].

Another alternative based on equivalence-class signature [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF] has recently been proposed by Derler and Slamanig [START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF]. It shares commonalities with [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF], such as the absence of explicit encryption, but manages to achieve full anonymity at the cost of increased complexity. Unfortunately, both [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF] and [START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF] inherently rely on signature of knowledge and so rather fit the random oracle model.

Very recently, Backes et al. [START_REF] Backes | Signatures with flexible public key: Introducing equivalence classes for public keys[END_REF] proposed a different framework based on a new primitive called signatures with flexible public keys. It yields secure constructions without random oracles with improved efficiency compared to the state-of-theart in this setting. However, the resulting group signatures are three times larger than the ones in the ROM and require more computations to be generated.

More generally, designers of group signature schemes are confronted with the choice of either proving security without random oracles or favoring efficiency by relying on the random oracle model whose limits are known [START_REF] Canetti | On the random-oracle methodology as applied to length-restricted signature schemes[END_REF].

Our Contribution. In this work, we propose a new group signature scheme avoiding the ROM that halves the size and the computational complexity compared to the state-of-the-art [START_REF] Backes | Signatures with flexible public key: Introducing equivalence classes for public keys[END_REF]. More specifically, our group signature only consists of 2304 bits which makes it very competitive, even against constructions in the ROM (see section 5 for more details).

As [START_REF] Backes | Signatures with flexible public key: Introducing equivalence classes for public keys[END_REF][START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF], our construction departs from the SEP framework and heavily relies on the randomizability of its components. However, contrarily to those works that assemble different building blocks (digital signature, NIZK, etc.) and so achieve some level of genericity, we are here interested in optimizing the combination to avoid NIZK proofs in the signature, so as to get the best possible efficiency.

Our work results from the observation that the equivalence-class signature of Fuchsbauer, Hanser and Slamanig (FHS) [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF] nicely interacts with the Pointcheval and Sanders (PS) signature scheme [START_REF] Pointcheval | Short randomizable signatures[END_REF]. More specifically, assuming very slight modifications of the FHS public key and of the PS signatures, we are able to merge the verification equations of FHS signatures with the one of PS signatures. Such a merge is crucial for our construction: it indeed means that it is no longer necessary to provide a NIZK proof that the signatures are valid and related. Thus, verifying our group signatures is essentially verifying FHS signatures.

Intuitively, we modify the PS signature scheme in such a way that each signature is of the form (g r , g y•r X r/hm ) where g y is the user's secret key, r is a random scalar, h m is a public element that depends on the message m to be signed and X is a public element. Leaving out the term in X, one can note that each signature contains a different representative of the same projective equivalence class as (g, g y ) and so it is quite easy, given a FHS signature on this pair, to prove that the PS signature was generated using certified keys.

Our group signature thus only consists of a PS signature and a FHS one which are both re-randomizable, leading to an anonymity proof under the DDH assumption. Moreover, we can prove that a non-registered user cannot generate a valid group signature unless he is able to forge FHS signatures. We only pay the price for our tailored construction in the proof of non-frameability, where we want to prove that no one can issue a forged group signature that can be traced back to an honest user. Indeed, we would like to directly rely on the security of PS signatures but this is impossible due to the modifications we introduced: a PS signature is not enough to answer adversary queries in our security proof. However, we show that we can tweak the original assumption underlying the security of PS signatures to suit our construction and so that we can rely on similar arguments to prove non-frameability.

While being non-generic, our construction remains flexible enough to comply with different group signature models. Interestingly, the different variants we consider achieve the same efficiency with respect to the group signature but mostly differ in the registration procedure. This concretely means that the most suitable setting can be chosen without any impact on the group signature itself. This also allows us in Table 4 to fairly compare our construction with the most relevant ones of the state-of-the-art and so to highlight the benefits of our group signature in all cases.

Organisation. We describe in section 2 the building blocks that we need to construct our group signature. The section 3 recalls the standard security model of group signatures. We describe our construction in section 4 and compare it with the most relevant alternatives of the state-of-the-art in section 5.

Preliminaries

Notations. The identity element of a group G is denoted 1 G and G * means G\{1 G }. If the group G is of order p, then we may say interchangeably that a ∈ Z/pZ or that a is a scalar. For a finite set X, the notation x $ ← X means that x is an element of X uniformly sampled.

Bilinear Groups

Definition 1. Bilinear groups are a set of three groups G 1 , G 2 , and G T of order p along with a map, called pairing, e :

G 1 × G 2 → G T that is -bilinear: for any g ∈ G 1 , g ∈ G 2 ,
and a, b ∈ Z/pZ, e(g a , g b ) = e(g, g) ab ; non-degenerate: for any g ∈ G *

1 and g ∈ G * 2 , e(g, g) = 1 G T ; efficient: for any g ∈ G 1 and g ∈ G 2 , e(g, g) can be efficiently computed.

We will only consider bilinear groups of prime order with type-3 pairings, i.e. there is no efficiently computable homomorphism between G 1 and G 2 . We stress that this yields the most efficient parameters [START_REF] Guillevic | Comparing the pairing efficiency over composite-order and prime-order elliptic curves[END_REF]. To highlight the differences between G 1 and G 2 , we will denote elements of the latter with a tilde (e.g. g).

Digital Signature

A digital signature scheme Σ is defined by four algorithms:

-Setup(1 λ ): Outputs public parameters pp for security parameter λ.

-Keygen(pp): On input pp, outputs signing and verification keys (sk, pk).

-Sign(sk, m): Outputs a signature σ of message m under signing key sk.

-Verify(pk, m, σ): On input verification key pk, message m and its alleged signature σ, outputs 1 if σ is a valid signature on m under pk, and 0 otherwise.

The standard security notion for a signature scheme is existential unforgeability under chosen message attacks (EUF-CMA) [START_REF] Goldwasser | A digital signature scheme secure against adaptive chosen-message attacks[END_REF]: it means that it is hard, even given access to a signing oracle, to output a valid pair (m, σ) for a message m never asked to the signing oracle.

PS Signature In [START_REF] Pointcheval | Short randomizable signatures[END_REF], Pointcheval and Sanders propose a randomizable signature scheme, i.e. a scheme enabling to derive re-randomized versions σ of any valid signature σ. An interesting feature of their signatures is that one cannot link σ and σ without knowing the corresponding message. They describe several versions of their signature scheme, offering different features. In this work we will use their variant supporting aggregation because it enables to decrease the size of the public key but we will not use this aggregation feature.

-Setup(1 λ ): Outputs the parameters pp containing the description of type-3 bilinear groups (G 1 , G 2 , G T , e) along with a set of generators (g, g) ∈ G 1 ×G 2 and a pair (X, X) ← (g x , g x ) for some random scalar x. -Keygen(pp): Generates a random scalar y and sets (sk, pk) as (g y , Y = g y ).

-Sign(sk, m): On message m, generates a signature (σ 1 , σ 2 ) ← (g r , X r •g r•y•m ) for some random scalar r. -Verify(pk, m, (σ 1 , σ 2 )): Accepts signature (σ 1 , σ 2 ) on m if the following equality holds: e(σ 1 , X • Y m ) = e(σ 2 , g).

One can note that anyone can re-randomize a signature by raising σ 1 and σ 2 to the same power t. The PS signature scheme is proven EUF-CMA-secure under a LRSW assumption customized for type-3 pairing, that we recall in subsection 2.3.

FHS Signature

In [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF], Fuchsbauer, Hanser and Slamanig introduce a signature on equivalence-class for the following equivalence relation on tuples in G n 1 : (M 1 , . . . , M n ) is in the same equivalence class as (N 1 , . . . , N n ) if there exists a scalar a such that N i = M a i for all i ∈ [1, n]. In this paper, we will only consider the case n = 2.

-Setup(1 λ ): Outputs parameters pp containing the description of type-3 bilinear groups (G 1 , G 2 , G T , e), with generators (g, g) ∈ G 1 × G 2 . -Keygen(pp): Generates two random scalars α 1 and α 2 and sets sk as (α 1 , α 2 ) and pk as ( A 1 , A 2 ) = ( g α1 , g α2 ).

-Sign(sk, (M 1 , M 2 )): Selects a random scalar t and computes the signature

(τ 1 , τ 2 , τ ) ← ((M α1 1 M α2 2 ) t , g 1/t , g 1/t ) on the representative (M 1 , M 2 ) ∈ G 2 1 . -Verify(pk, (M 1 , M 2 ), (τ 1 , τ 2 , τ )): Accepts (τ 1 , τ 2 , τ ) ∈ G 2 1 × G 2 , a signature on (M 1 , M 2 ), if e(τ 1 , τ ) = e(M 1 , A 1 ) • e(M 2 , A 2
) and e(τ 2 , g) = e(g, τ ) hold.

We note that the signature (τ 1 , τ 2 , τ ) is only valid on the representative (M 1 , M 2 ). However, we can easily derive a signature on other representatives (M r 1 , M r 2 ) of the same equivalence class, while re-randomizing the signature, by generating a random scalar t and computing (τ r•t 1 , τ

1/t 2
, τ 1/t ).

Computational Assumptions

SXDH assumption. For i ∈ {1, 2}, the DDH problem is hard in G i if, given (g, g x , g y , g z ) ∈ G 4 i , it is hard to distinguish whether z = x • y or z is random. The SXDH assumption holds if DDH is hard in both G 1 and G 2 .

PS assumption. Pointcheval and Sanders [START_REF] Pointcheval | Short randomizable signatures[END_REF] introduce "Assumption 1", here referred to as PS assumption, to prove the security of their construction.

PS Assumption: Let (p, G 1 , G 2 , G T , e) be a bilinear group setting of type-3, with g (resp. g) a generator of G 1 (resp. G 2 ). For ( X = g x , Y = g y ), where x and y are random scalars, we define the oracle O(m) on input m ∈ Z/pZ that chooses a random r ∈ Z/pZ and outputs the pair P = (g r , g r(x+m•y) ). Given (g, g y , g, X, Y ) and unlimited access to this oracle, no adversary can efficiently generate (m * , g r , g r(x+m * •y) ), with r = 0, for a new scalar m * , not asked to O.

MPS assumption. As we explain in the introduction, we would like to directly rely on the PS assumption but this is not possible. In particular, in our group signature construction, the user incorporates parts of the group signature in the message to be signed. This is done by using a suitable map h that must be taken into account by the assumption. We therefore introduce a variant of the PS assumption that we call MPS assumption (M stands for modified).

MPS Assumption: Let (p, G 1 , G 2 , G T , e) a bilinear group setting of type-3, with g (resp. g) a generator of G 1 (resp. G 2 ), and h : {0, 1} * → Z/pZ a function. For random scalars x, y and z, we define the oracle O(m) on input m ∈ Z/pZ that picks random r, s ∈ Z/pZ and outputs the tuple P = (s, g r•s , g r , g r•z , g r(x+t•y) ) with t = h( g r•s ||g r ||m). Given (g, g y , g z , g z•x , g, X, Y ) and unlimited access to this oracle, no adversary can efficiently generate (t * , g r , g r(x+t * •y) ) with r = 0 and a value t * different from those involved in the answers from O.

The validity of the output can easily be checked thanks to the pairing e: e(g r(x+t * •y) , g) ?

= e(g r , X • Y t * ). We note that the adversary's goal is still to output a valid PS signature but it now has access to additional elements that do not seem helpful to create forgeries, as we discuss below. A proof that the MPS assumption holds in the generic group model is given in the full version [START_REF] Clarisse | Group Signature without Random Oracles from Randomizable Signatures (full version of this work)[END_REF].

Remark 1. -Our new oracle still returns a PS signature (g r , g r(x+ty) ) but on a scalar t = h( g r•s ||g r ||m) instead of m. However, we define much harder success conditions for the adversary: it can only win if the scalar t used in its forgery is different from the ones used by O (in particular a forgery on a new message m * is not valid if it leads to an already used t). Intuitively, this rules out any strategy based on the properties of h (such as collisions).

We will therefore assume (and prove in the generic group model) that the MPS assumption holds for any3 function h : {0, 1} * → Z/pZ. From the security point of view, this therefore does not change anything compared to an assumption where O would return (g r , g r(x+my) ). -This slight modification induces another one: we now need to provide the pair (g z , g z•x ), for some random scalar z, in the assumption. In [START_REF] Pointcheval | Short randomizable signatures[END_REF], this pair is exactly a signature on 0 and so is directly generated by the reduction in the security proof by running O on 0. This is no longer possible here, and we then need to explicitly add these elements in the definition of the assumption. In any case, this does not provide more power to the adversary than in the PS assumption. -The element g r•z is the only one involving the secret z in P . It seems therefore useless to combine it with the other elements of P to derive a new valid tuple. -The last difference with the PS assumption is the pair (s, g r•s ) that must be added to the oracle answers. However, we note that g r•s is an element of G 2 and so is intuitively useless to forge a PS signature (g r , g r(x+ty

) ) ∈ G 2 1 ,
thanks to the asymmetry of the pairing. The same holds true for s that is not one of the secret values used to compute the PS signature.

Group Signature

For completeness, we recall here the security model for dynamic group signature from the BSZ model [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF]. We introduce some minor syntactic changes and discuss popular variants of the original security notions introduced by Bellare et al. [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF].

A reader familiar with group signature can safely jump to Remark 2.

Syntax. A group signature scheme is defined by the following algorithms that involve three types of entities: a group manager, an opening authority and users. Each of the latter is identified by a public index i ∈ N * .

-Setup(1 λ ): Outputs public parameters pp for security parameter λ.

-UKeygen(pp): Returns a user's key pair (sk, pk) on public parameter pp. We assume that pk is public and anyone can get an authentic copy of it. -OKeygen(pp): Returns the opening authority's key pair (osk, opk) under pp.

-GKeygen(pp): Returns the group manager's key pair (gsk, gpk) along with a public register Reg, on public parameters pp. -Join: This is a two-party interactive protocol between the group manager and a user i who wants to join the group. The input of the former is (gsk, Reg, opk, pk i ) whereas the user takes as input (gpk, opk, sk i ). If the protocol does not fail, then the user gets a group signing key usk i whereas the group manager updates Reg. Else, both parties return ⊥. -Sign(usk i , m): Returns a group signature σ of m under signing key usk i .

-Verify(gpk, σ, m): On input the group manager's public key, a group signature σ and a message m, returns a bit b ∈ {0, 1}. -Open(osk, gpk, Reg, σ, m): On input the opening authority's secret key, the group manager's public key, the register Reg, a group signature σ and a message m, returns either 0, ⊥ or an index i ∈ N * along with a proof π. -Judge(gpk, Reg, σ, m, i, π): On input the group manager's public key, the register Reg, a group signature σ, a message m, an index i ∈ N * and a proof π, returns a bit b ∈ {0, 1}.

Security Model. A group signature should achieve correctness, anonymity, traceability and non-frameability. We refer to [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] for a formal definition of correctness, but informally it means that any user who has joined the group should be able to produce valid signatures σ (i.e. one for which Verify outputs 1) on any message m. Moreover, it should be possible to open such signatures, i.e. to recover the identity i of the signer, and to produce publicly verifiable proofs that user i has indeed issued these signatures. Anonymity requires that group signatures should be anonymous, except for the opening authority. Traceability requires that no one can produced a valid signature that cannot be traced back to some user through the Open procedure.

Exp an A (1 λ ) -Anonymity Security Game 1. pp ← Setup(1 λ ) 2. (osk, opk) ← OKeygen(pp) 3. (gsk, gpk) ← GKeygen(pp) 4. b $ ← {0, 1}, O ← {OAdd, OJU , OCor, OSign, OOpen, OCh b } 5. b * ← A O (gsk, opk) 6. If OOpen is queried on the output of OCh b , then return 0 7. Return (b = b * ) Exp nf A (1 λ ) -NF Security Game 1. pp ← Setup(1 λ ) 2. (osk, opk) ← OKeygen(pp) 3. (gsk, gpk) ← GKeygen(pp) 4. (σ, m, i, π)
← A OAdd,OJ U ,OCor,OSign (gsk, osk) 5. If OSign returned σ, then return 0 6. If i is corrupt, then return 0 7. Return Judge(gpk, Reg, σ, m, i, π)

Exp tra A (1 λ ) -Traceability Security Game 1. pp ← Setup(1 λ ) 2. (osk, opk) ← OKeygen(pp) 3. (gsk, gpk) ← GKeygen(pp) 4. (σ, m) ← A OAdd,OJ GM ,OCor,OSign (gpk, osk) 5. If ⊥← Open(osk, gpk, Reg, σ, m), then return 1 6. If (i, π) ← Open(osk, gpk, Reg, σ, m)
and 0 ← Judge(gpk, Reg, σ, m, i, π), then return 1 7. Return 0 Fig. 1. Security Games for Group Signature Finally, non-frameability means that no one can be falsely accused of having produced a signature. The corresponding security games, outlined in Figure 1, make use of the following oracles:

-OAdd(i) is an oracle that can be used to add a new user i. It then runs UKeygen(pp) to get (sk i , pk i ) and returns pk i . If i has already been used in a previous query, then it returns ⊥. -OJ U (i) is an oracle that plays the user's side of the Join protocol. It can be used by an adversary A playing the role of a corrupt group manager. It returns ⊥ if i has already joined the group or if user i does not exist. -OCor(i) is an oracle that returns all the secret keys of the user i. The user i is then said to be corrupt. Any non-corrupt user is considered honest. -OJ GM () is the counterpart of the OJ U oracle that can be used by a corrupt user to join the group. -OSign(i, m) is an oracle that returns Sign(usk i , m), provided that i is an honest user that has already joined the group. -OOpen(σ, m) is an oracle that returns Open(osk, gpk, Reg, σ, m).

-OCh b (i 0 , i 1 , m) is an oracle that takes as inputs the index of two honest users and returns Sign(usk i b , m).

Let A be a probabilistic polynomial adversary. A group signature scheme is

-anonymous if Adv an (A) = | Pr[Exp an A (1 λ ) = 1] -1/2| is negligible for any A; -traceable if Adv tra (A) = Pr[Exp tra A (1 λ ) = 1] is negligible for any A; -non-frameable if Adv nf (A) = Pr[Exp nf A (1 λ ) = 1] is negligible for any A.
The security model introduced by Bellare, Shi and Zhang [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] places no restriction on the OCor queries in the anonymity experiment. This means that the adversary is allowed to corrupt the "challenge" users (i.e. those that are involved in OCh queries). This corresponds to the strongest notion of anonymity, sometimes called full anonymity or CCA-2 anonymity (see e.g. [START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF]), where anonymity holds even if the users' secret keys are leaked.

Remark 2. The BSZ model [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] defines strong security properties that are sufficient in most contexts. However, it may be possible in some situations to relax some of them, usually leading to more efficient constructions. This is particularly true for the anonymity property for which popular variants exist, such as CPA anonymity [START_REF] Boneh | Short group signatures[END_REF][START_REF] Boyen | Compact group signatures without random oracles[END_REF] or selfless anonymity [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Boneh | Group signatures with verifier-local revocation[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF]. The former removes the oracle OOpen in the anonymity game but the users remain anonymous even if their secret keys leak. Contrarily, selfless anonymity allows OOpen queries but users are no longer anonymous when their secret keys leak. These two notions are incomparable and so fit different contexts. The construction we describe in the next section achieves both of them. Interestingly, it also achieves full anonymity in the model introduced by Bellare, Micciancio and Warinschi [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF] (BMW model), where the group manager is also the opening authority.

Our Group Signature

The Construction

Intuition. A group signature usually contains two kinds of digital signatures that we will denote by σ and τ . The first one is issued on the message to be signed by the user using his own key pair (usk, upk). Intuitively, the unforgeability of the digital signature ensures that no adversary is able to produce a forged group signature which can be traced back to upk (non-frameability). The second one is issued by the group manager on usk (or upk) to differentiate key pairs of group members from those of unregistered users. Here, unforgeability ensures that only users that have joined the group can issue group signature, which is necessary to achieve traceability.

If non-frameability and traceability were the only two conditions expected from a group signature, then the latter would simply be (τ, σ, upk, m). However, this cannot work when anonymity is also required so the standard practice has been to encrypt/commit at least τ and upk and then provide zero-knowledge proofs that these elements are well-formed.

The work of Bichsel et al [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF] has shown that we can do better when τ is randomizable. Indeed, in such a case there is no need to encrypt τ , the latter can simply be re-randomized and sent unencrypted, leading to significant gains in efficiency. Their group signature can only achieve a weaker selfless anonymity notion in the ROM, but it seems a reasonable price to pay in view of the benefits.

Despite its novelty, [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF] still shares commonalities with the standard framework of the BSZ model [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF]. There is indeed still a modular composition of two signatures τ and σ with a proof of knowledge. The latter two can be merged (leading to a signature of knowledge) using the Fiat-Shamir heuristic [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] in the ROM, but the spirit remains the same. Modular systems are interesting since they can leverage any advance in the construction of their building blocks. For example, the scheme of [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF] can straightforwardly be improved by using PS signatures [START_REF] Pointcheval | Short randomizable signatures[END_REF] to instantiate τ , instead of Camenisch-Lysyanskaya signatures [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF] in the original construction. Unfortunately, the complexity of a modular construction is the sum of all its parts, so a natural question is whether it is possible to improve efficiency by optimizing the combination of the different building blocks for some specific instantiations.

In this section we construct the most efficient group signature without random oracles by noticing that FHS equivalence-class signatures [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF] nicely interact with PS signatures [START_REF] Pointcheval | Short randomizable signatures[END_REF]. Indeed let us recall the latter, and more specifically its variant designed to support aggregation. A (non-aggregated) signature on a message m in this case is given by (σ 1 , σ 2 ) = (g r , X r (g y•m ) r ) where r is some random scalar, X = g x is a public element and y is the signer's secret key. One can note that we can alternatively define σ 2 as σ 1/m 2 = X r/m (g y ) r : any adversary able to forge such a signature can trivially be converted into an adversary against the original PS-signature scheme.

Therefore, any signature issued by a user will be of the form (σ 1 , σ 2 ) = (g r , X r/m (g y ) r ). If we applied the standard methodology here, we would provide a signature τ on y (or g y ) and then prove in a zero-knowledge way that τ is valid on the key that has been used to generate (σ 1 , σ 2 ). However, we can do better if we directly use the FHS-signature scheme [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF].

Indeed, for all r, if we discard the term X r/m in σ 2 , it only remains (g r , g y•r ) which are different representatives of the same equivalent class. Thus, if we provide a FHS signature on (g r , g r•y ) one can directly check that (σ 1 , σ 2 ) was generated using a certified key, without any proof of knowledge. Anonymity of the resulting construction simply follows from the ability to re-randomize FHS signature while changing the representative of the class.

It then only remains to explain how to remove X r/m . Recall that a FHS signature on (g r , g r•y ) is a tuple (τ 1 , τ 2 , τ ) such that e(τ 1 , τ ) = e(g r , A 1 ) • e(g r•y , A 2 ) and e(τ 2 , g) = e(g, τ ), where ( A 1 , A 2 ) = ( g α1 , g α2 ) is the public key. Assume that we add B = X α2 to this public key ( X = g x is a part of the public key of the PS-signature scheme).

Then, e(σ

1 , A 1 ) • e(σ 2 , A 2 ) • e(σ 1 , B -1/m ) = e(g r , A 1 ) • e(g y•r , A 2 ) = e(τ 1 , τ ),
and the second equation remains unchanged. This means that we can check the validity of both FHS and PS signatures at essentially the cost of verifying a FHS signature. Moreover, the fact that we merge the verification of these signatures makes zero-knowledge proofs unnecessary. Concretely, this means that our group signature only consists of (σ 1 , σ 2 , τ 1 , τ 2 , τ ), i.e. four elements of G 1 and one element of G 2 , and can be verified with merely two pairing equations. Interestingly, the fact that we avoid the classical signature of knowledge of y allows to achieve both CPA anonymity and selfless anonymity. Indeed, schemes based on randomizable signatures (see e.g. [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF]) are usually proven anonymous under the DDH assumption in G 1 . Therefore, to enable opening, they usually force the users to provide some "trapdoor" g y ∈ G 2 that allows the opening authority to break DDH on their specific signatures. When y is part of the user's signing key usk (which is necessary for a signature of knowledge of y), leakage of the latter means that the adversary can recover y and thus g y . Anonymity can then no longer hold in this case leading to the selfless anonymity notion.

In our case, we note that g y ∈ G 1 is enough to issue group signatures, meaning that users can discard y after generating their keys. In case usk leaks, the adversary now recovers g y , which is useless to break DDH. We can thus retain some level of anonymity (at least CPA anonymity) in this case.

The Protocol. We now formalize the previous intuition by describing the algorithms constituting our scheme. As we explain above, we manage to avoid NIZK proofs and explicit encryption in our signature. However, we still need such primitives for some algorithms such as Join and Open. Fortunately, the latter are in practice subject to less constraints that Sign as they have less impact on the user's experience (in particular because they are run far less often than Sign). Our construction therefore also makes use of a public key encryption scheme Γ and of a NIZK proof system. The latter will concretely be the Groth-Sahai proof system [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] that allows to prove most common relations in bilinear groups by using a common reference string crs. Additional details on these two primitives are provided in the full version [START_REF] Clarisse | Group Signature without Random Oracles from Randomizable Signatures (full version of this work)[END_REF].

-Setup(1 λ ): Let (G 1 , G 2 , G T , e) be the description of type-3 bilinear groups of prime order p, this algorithm first selects g $ ← G * 1 and g $ ← G * 2 , and then computes (X, X) ← (g x , g x ) for some random scalar x. It also generates the public parameters pp Σ for a digital signature scheme4 Σ and selects a hash function h : {0, 1} * → Z/pZ. Finally, it generates a common reference string crs for the Groth-Sahai proof system [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] in the SXDH setting and then sets the public parameters as pp = (G 1 , G 2 , G T , e, g, g, X, X, crs, pp Σ , h).

-UKeygen(pp): The user defines his own key pair as (sk, pk) ← Σ.Keygen(pp Σ ).

-OKeygen(pp): The opening authority generates a key pair (osk, opk) for a public key encryption scheme Γ . -GKeygen(pp): The group manager selects two random scalars α 1 and α 2 and then computes ( A 1 , A 2 , B) ← ( g α1 , g α2 , X α2 ). He then initializes a public register Reg and returns (gsk, gpk) ← ((α 1 , α 2 ), ( A 1 , A 2 , B)). -Join: To join the group, a user i first selects two random scalars, u and y, and computes (g u , g u•y ) along with C ← Γ.Encrypt(opk, g y ). He then generates a NIZK proof π that C encrypts an element g y ∈ G 2 such that e(g u , g y ) = e(g u•y , g). Finally, he generates µ ← Σ.Sign(sk i , (g u ||g u•y ||C||π)) and sends it, along with (g u , g u•y , C, π), to the group manager. Upon receiving these elements, the group manager checks the validity of the proof π and that Σ.Verify(pk i , µ, (g u ||g u•y ||C||π)) = 1. If π and µ are both valid, then he stores (g u , g u•y , C, π, pk i , µ) in Reg[i], generates a t $ ← Z/pZ and returns τ 1 ← ((g u ) α1 (g u•y ) α2 ) t , τ 2 ← g 1/t and τ ← g 1/t . Finally, the user computes τ 1 ← (τ 1 ) 1/u and sets usk i = (τ 1 , τ 2 , τ , g y ).

-Sign(usk i , m): To sign a message m, the user first selects two random scalars r and s, and generates the following elements:

τ 1 ← τ r•s 1 , (τ 2 , τ ) ← (τ 1/s 2 , τ 1/s ), (σ 1 , σ 2 ) ← (g r , X r/h( τ ||σ1||m) • (g y ) r ).
The group signature σ on m is then defined as σ = (τ 1 , τ 2 , τ , σ 1 , σ 2 ). -Verify(gpk, σ, m): To verify a group signature σ on m, one checks that none of its elements is 1 G1 or 1 G2 and that the following equalities hold:

e(σ 1 , A 1 B -1/h( τ ||σ1||m) ) • e(σ 2 , A 2 ) = e(τ 1 , τ
) and e(τ 2 , g) = e(g, τ ), in which case one outputs 1. Otherwise, one returns 0. -Open(osk, gpk, σ, m): Before opening a signature, the opening authority first checks that it is valid. Otherwise, he returns 0. By using its secret key osk, the opening authority has the ability to decrypt any ciphertext C i stored in Reg[i] and thus recover the elements g yi ∈ G 2 for all registered users. He can then check, for each of them, whether the following equality holds:

e(σ 2 , g) • e(σ 1 , X -1/h( τ ||σ1||m) ) = e(σ 1 , g yi ).
If there is no match, then the opening authority returns ⊥. Otherwise, let j be the corresponding user. The opening authority recovers the data (g uj , g uj •yj , C j , π j , pk j , µ j ) stored in Reg[j], commits to g yj and then outputs j along with a Groth-Sahai proof π that: e(σ 2 , g) • e(σ 1 , X -1/h( τ ||σ1||m) ) = e(σ 1 , g yj ) and e(g uj •yj , g) = e(g uj , g yj ).

-Judge(gpk, σ, m, i, π): To verify an opening, one checks that π is valid, Verify(gpk, σ, m) = 1 and Σ.Verify(pk i , µ i , (g ui ||g ui•yi ||C i ||π i )) = 1. If all conditions are satisfied, then one returns 1. Otherwise, one returns 0.

Correctness. First note that at the end of the Join protocol, the user gets a FHS equivalence-class signature [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF] on the representative (g, g y ). Indeed, (τ 1 , τ 2 , τ ) = ((g α1 g y•α2 ) t , g 1/t , g 1/t ). To issue a group signature on m, the user first re-randomizes (τ 1 , τ 2 , τ ) using s while updating the representative to (g r , g r•y ). The resulting tuple (τ

1 , τ 2 , τ ) is ((g r•α1 g r•y•α2 ) t•s , g 1/(t•s) , g 1/(t•s)
) and is still a FHS signature on the same equivalent class. He then generates a pair (σ 1 , σ 2 ) where (σ 1 , σ m 2 ) is a PS signature [START_REF] Pointcheval | Short randomizable signatures[END_REF] on m = h( τ ||σ 1 ||m) using the same randomness r. Therefore, such a group signature satisfies:

e σ 1 , A 1 B -1/m • e(σ 2 , A 2 ) = e g r , g α1-x•α 2 m • e g r( x m +y) , g α2 , = e(g, g) r(α1+y•α2) = e(τ 1 , τ ),
and e(τ 2 , g) = e(g 1/(t•s) , g) = e(g, g 1/(t•s) ) = e(g, τ ).

Remark 3. Group signatures following the classical Sign-Encrypt-Prove framework usually provide an efficient opening procedure. Indeed, the opening authority knows the corresponding decryption key and so can decrypt the ciphertext included in the group signature and then identify the signer. Unfortunately, there is no equivalent for constructions without encryption and in particular there is no longer a "master" key that the opening authority can use to break anonymity. Constructions based on randomizable signatures [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF] circumvent this issue by forcing each user to provide to the opening authority a way to open their signatures. Concretely, during the Join protocol, each user must transmit some elements depending on their secret keys to this authority. Unfortunately this requirement does not fit the BSZ model [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] where Join is a two-party protocol between the user and the group manager. There are then two ways to solve this problem. Either we add the opening authority as an acting party in Join or we require that the user sends these elements to the group manager. The first solution is conceptually the simplest but modifies the original BSZ model. The second one does not but requires additional primitives to ensure security. Indeed, the user cannot transmit such elements in clear (otherwise the group manager could break anonymity) so he must send them encrypted and prove (in a zero-knowledge way) that the resulting ciphertext is well-formed.

In this paper we choose to describe the most complex (second) solution since one can easily derive from it a group signature scheme complying with the first option. We will then need an IND-CCA2 secure public key encryption scheme that is compatible with NIZK proofs. In practice, one can choose for instance [START_REF] Libert | Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures[END_REF] that nicely interacts with Groth-Sahai proofs [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]. We note that efficiency is not really a concern here since this step of the Join protocol has no impact on the group signatures themselves. Remark 4. We note that the security model of Bellare et al [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] already assumes a trusted Setup phase, so our construction perfectly fits this model on this point. However, this does not explain how to generate the public parameters in real-world conditions. In practice, it would be natural that the opening authority generates them. Regarding security, it would only be problematic for non-frameability if corruption of this entity occurred before Setup, but this is excluded by the model of [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF]. We can also mitigate the risks by relying on a cooperative generation of the parameters, as in [START_REF] Canard | Divisible E-cash made practical[END_REF].

Security Results.

Theorem 1. Our group signature is:

traceable under the EUF-CMA security of the FHS signature scheme; non-frameable under the MPS assumption, the collision-resistance of the function h and the EUF-CMA security of Σ; -CPA anonymous under the SXDH assumption and the IND-CCA2 of Γ ; selfless anonymous if it is non-frameable, if Γ is IND-CCA2 secure and if the SXDH assumption holds;

fully anonymous, with merged opening authority and group manager, if it is traceable and if the SXDH assumption holds.

Theorem 1 shows that our scheme retains some security properties (namely CPA security) even when users' secret keys are leaked, contrarily to the ones of [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF]. The fact that selfless anonymity depends on the non-frameability may seem surprising but this is due to the special opening process that the reduction R uses in our security proof. Informally, R is able to open all signatures but the ones generated by the "challenge" user. To circumvent this problem R stores all the signatures it has produced on behalf of this user so that it will be able to recognize them if they are later submitted to the OOpen oracle. However, this works as long as the adversary is unable to forge signatures for this user, hence the non-frameability requirement.

The last statement of the theorem shows that we can achieve the strongest notion of anonymity if we additionally assume that the opening authority is also the group manager, as in the model of Bellare, Micciancio and Warinschi [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF].

The theorem is proved below, except the part regarding non-frameability that we only provide in the full version of this work [START_REF] Clarisse | Group Signature without Random Oracles from Randomizable Signatures (full version of this work)[END_REF] due to space limitation.

Proof of Anonymity. Our proofs of CPA anonymity and selfless anonymity are very similar and only differ by one game. We will then consider an adversary against "anonymity" without specifying which property we consider except in Game 5 where the distinction is necessary. We discuss the case of full anonymity in Remark 5.

Let A be an adversary against the anonymity of our construction succeeding with probability ε. We define a sequence of games to show that this advantage is negligible. For each Game i we define Adv i = |Pr(S i ) -1/2|, where S i is the event "A succeeds in Game i". We additionally define Adv SXDH as the advantage against the SXDH problem.

Game 1. Our first game is exactly the one of anonymity of Figure 1 where the reduction R generates normally all the secret values and so is able to answer any oracle query. By definition, we have Adv 1 = ε. Game 2. In our second game, R selects a random index i * ∈ [1, q A ], where q A is a bound on the number of OAdd queries. R proceeds as usual but aborts if A queries (i 0 , i 1 , m) to the OCh oracle with i b = i * . The advantage of A in this new game is then at least ε q A . Game 3. In the third game, R generates a simulated common reference string crs and simulates all the zero-knowledge proofs. Any change in the behaviour of A can then be used against the zero-knowledge property of these proofs, which rely on SXDH in our setting. Therefore, Adv 3 ≥ Adv 2 -Adv SXDH . Game 4. In the fourth game, R sets opk as the public key of a IND-CCA 2 experiment. It then uses the decryption oracle to decrypt the ciphertext C i stored in Reg[i] for all users i and so can answer any query as usual. However, upon receiving the OJ U query on i * (this query necessarily occurs because of Game 2), it proceeds normally except that it generates C as an encryption of a random element of G 2 and simulates the proof. A change in the behaviour of A would imply an attack against the IND-CCA2 security of Γ , so we get Adv 4 ≥ Adv 3 -Adv IND-CCA2 . Game 5. In the fifth game, R stores every signature it generates on behalf of i * in some register Sig. Upon receiving a Open query for some pair (σ, m), it first checks whether σ ∈ Sig in which case it returns i * along with a simulated proof. Otherwise, it returns Open(σ, m).

We note that Game 5 is the same as Game 4 when we consider CPA anonymity since there is no OOpen query in this case. For selfless anonymity, a difference only occurs when the adversary manages to submit a forged signature that can be traced back to i * . However, such an adversary can straightforwardly be converted into an adversary against non-frameability. We then have Adv 5 ≥ Adv 4 -Adv nf . Game 6. In the sixth game, R proceeds as in the previous game except that it answers to the OCh query by returning a signature generated using a random key. The advantage of A can then only be 0. We prove below that the Games 5 and 6 cannot be distinguished under the SXDH assumption and we then have Adv 6 ≥ Adv 5 -Adv SXDH .

Proof (of indistinguishability between anonymity Games 5 and 6). R receives a DDH challenge (g, g a , g b , g z ) in G 1 and must then decide whether z = a•b. It will then act as if y = a for the secret key usk i * of user i * . This is not a problem since g a is sufficient to issue group signatures and to join the group since Game 4. Moreover Game 5 ensures R is able to answer any OOpen query, even without knowing g a .

To answer the OCh query for a message m, it selects a random scalar t and computes a group signature σ as follows:

• τ 1 ← ((g b ) α1 • (g z ) α2 ) t ; • (τ 2 , τ ) ← (g 1/t , g 1/t ); • (σ 1 , σ 2 ) ← (g b , (g b ) x/h( τ ||σ1||m) • (g z )).
In any case, σ is a valid group signature on m, i.e. Verify(gpk, σ, m) outputs the bit 1. If z = a • b, then σ s a valid signature issued by user i * and A is still playing Game 5. Else, σ is a signature issued with a random key, independent of a and A is playing Game 6. Any change of behavior of A between these two games can then be used against the DDH assumption in G 1 and so against the SXDH assumption.

We get the following result, which proves both CPA anonymity and selfless anonymity of our construction:

• ε/q A ≤ 2 Adv SXDH + Adv IND-CCA2 for any adversary succeeding against CPA anonymity with probability ε; • ε/q A ≤ 2 Adv SXDH +Adv IND-CCA2 +Adv nf for any adversary succeeding against selfless anonymity with probability ε.

Remark 5. Let us now consider the case where the group manager and the opening authority are merged, as in the BMW model [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF]. As explained in Remark 3, the use of IND-CCA2 encryption during the Join protocol is only necessary when the opening authority is not involved in this process, which is no longer the case here. We can then discard Γ and remove Game 4 in the security proof. In Game 5, R proceeds as follows. It still stores the signatures generated on behalf of i * in Sig but now answers OOpen queries on (σ, m) as follows:

if σ ∈ Sig, then it returns i * along with a simulated proof π; if Open(σ, m) returns (i, π) or 0, then it forwards this answer to the adversary; if Open(σ, m) returns ⊥, then it returns i * along with a simulated proof π.

We note that a problem only occurs in the third case if the adversary managed to submit a group signature that cannot be traced back to a registered user. However, this would mean that A is a valid adversary against traceability, which is unlikely. All the other games remain unchanged so ε/q A ≤ 2 Adv SXDH +Adv tra for any adversary succeeding against full anonymity with probability ε in BMW [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF].

Proof of Traceability. We prove that any untraceable group signature can be used to construct a forgery against the FHS equivalence-class signature scheme. More specifically, let A be an adversary against traceability succeeding with probability ε, then A can be converted into an adversary succeeding against the EUF-CMA security of FHS signature with the same probability.

Technically, A can succeed by returning a valid signature σ on m that either foils the opening process or that can be opened but for which it is impossible to produce a valid proof of opening. We can exclude the latter in our construction because of the correctness and of the soundness of Groth-Sahai proofs.

Our reduction R generates the public parameters as usual except that it does not discard x after generating X and X. It then gets the public key A 1 and A 2 from the EUF-CMA challenger and sets gpk as ( A 1 , A 2 , A x 2 ). By using its signing oracle, it is able to handle Join query so the simulation is perfect. At the end of the game, A then outputs with probability ε an untraceable group signature σ on m. If we parse σ as (τ 1 , τ 2 , τ , σ 1 , σ 2 ), this means that:

(1.) e σ 1 , A 1 B -1/h( τ ||σ1||m) • e(σ 2 , A 2 ) = e(τ 1 , τ ); (2.) e(τ 2 , g) = e(g, τ ); (3.) e(σ 2 , g) • e σ 1 , X -1/h( τ ||σ1||m) = e(σ 1 , g yi ) for all g yi stored (encrypted). Equation (1.) is equivalent to: e(σ 1 , A 1 ) • e σ 2 • σ -x/h( τ ||σ1||m) 1 , A 2 = e(τ 1 , τ ), which means (together with equation (2.)) that (τ 1 , τ 2 , τ ) is a valid FHS signature on σ 1 , σ 2 • σ -x/h( τ ||σ1||m) 1
. However, (τ 1 , τ 2 , τ ) will be considered as a valid forgery only if

σ 1 , σ 2 • σ -x/h( τ ||σ1||m) 1
does not belong to the equivalence class of a message submitted to the signing oracle.

Let S = {(h i , h yi i )} q i=1 , for h i ∈ G 1 be the set of queried messages. All these messages were involved in a Join query during which the group manager received (and stored) g yi (encrypted). Therefore, if (µ 1 , µ 2 ) belongs to the equivalent class of an element of S, then there exists i ∈ [1, q] such that e(µ 1 , g yi ) = e(µ 2 , g).

Let us then assume that σ

1 , σ 2 • σ -x/h( τ ||σ1||m) 1
satisfies the previous condition, i.e. that there is i such that: e(σ 1 , g yi ) = e σ 2 • σ -x/h( τ ||σ1||m) 1 , g . We then have e(σ 1 , g yi ) = e(σ 2 , g) • e σ -x/h( τ ||σ1||m) 1

, g = e(σ 2 , g) • e σ 1 , X -1/h( τ ||σ1||m) , which contradicts equation (3.). The pair σ 1 , σ 2 • σ -x/h( τ ||σ1||m) 1 has then never been signed, nor any representative of the same equivalence class, which means that (τ 1 , τ 2 , τ ) along with σ

1 , σ 2 • σ -x/h( τ ||σ1||m) 1
is a valid forgery against the EUF-CMA security of the FHS scheme.

Efficiency comparison

We compare the signing algorithm of our scheme with the ones of other constructions of the state-of-the-art. All of them are proven under interactive assumptions (or directly in the generic group model) so we do not take this point into account in our comparison. In Table 4, we enumerate the number of expensive operations, i.e. exponentiations in G 1 , G 2 and G T (denoted by e 1 , e 2 and e T respectively). Regarding signing cost, our scheme is the most efficient one whenever computing 3e 1 + 1e 2 is cheaper than computing 1e T .

To compare these operations, we choose a common metric. We aim at the 128bit security. Following the incentive of Barbulescu and Duquesne [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF], we select Barreto-Lynn-Scott curves with k = 12 that now seem more appropriate than Barreto-Naehrig ones, considering the recent attacks on pairings [START_REF] Kim | Extended tower number field sieve: A new complexity for the medium prime case[END_REF]. Moreover, they are getting involved in more implementations, e.g. in Zexe [START_REF] Bowe | Zexe: Enabling decentralized private computation[END_REF], a ledgerbased system, and in ZCash [START_REF] Bowe | BLS12-381: New zk-SNARK Elliptic Curve Construction[END_REF] for zk-SNARKs.

Like in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF], we select a prime q ≡ 3 (mod 4) and construct the tower of fields:

F q 2 = F q [U ] (U 2 + 1) , F q 6 = F q 2 [V ] (V 3 -U -1)
and

F q 12 = F q 6 [W ] (W 2 -V ) .
This choice yields the costs in Table 1, where m is the cost of one multiplication in F q (we make the rough assumption that squaring is the same cost as multiplying in F q ). The last line of Table 1 represents costs in the so-called cyclotomic subgroup G Φ12(q) ⊂ F q 12 of order Φ 12 (q) (where Φ 12 (q) is the 12 th cyclotomic polynomial evaluated at q, see [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]). This is of interest to us since G T ⊂ G Φ12(q) and squaring in G Φ12(q) are twice faster.

Field Mult. (M ) Squaring (S) Fq m m F q 2 3m 2m F q 12 54m 36m G Φ 12 (q)
54m 18m Table 1. Costs of arithmetic operations in the tower extension as in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] For simplicity, we take our BLS12 curve in the short Weierstrass model, that is y 2 = x 3 + b with b ∈ F q , and use the Jacobian coordinate system: representing (x, y) as (X, Y, Z) and satisfying the equations x = X/Z 2 and y = Y /Z 3 . This is the most efficient for pairings, without changing models (see [START_REF] Bos | Exponentiating in pairing groups[END_REF]): it takes 11 field multiplications and 5 field squarings to add two distinct points and 2 field multiplications and 5 field squarings to double a point. After converting squarings to multiplications (see Table 1), we end up with Table 2. Note that a point in G 2 is on the degree-6 twist curve, i.e. over F q 2 .

Group

Addition Doubling 11M + 5S 2M + 5S G1 16m 7m G2 43m 16m Table 2. Costs of arithmetic operations in the pairing groups G1/Fq and G2/F q 2 , when modeling the curve with a short Weierstrass equation and using Jacobian coordinates Now, to compare exponentiation, let n be a positive integer. Think of n as one of the random scalars in our Sign procedure. A double-and-add algorithm will, on average, double log 2 n times and add (log 2 n)/2 times. It means, for instance, that an exponentiation by n in G 1 costs 15(log 2 n) field multiplications. In the following, we bound n by p (the order of G 1 , G 2 and G T ) and so get Table 3, where k = log 2 p. 3. Upper-bounded cost of one group exponentiation Using BLS12 curves leads to a 256-bit representation of scalars and at least 384-bit (resp. 768-bit) for the elements of G 1 (resp. G 2 ). We summarize our comparison in Table 4, indicating if the constructions follow the BMW model [START_REF] Bellare | Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[END_REF] or the BSZ one [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] (see section 3). We note that [START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF] also considers outlying properties, such as opening soundness, that have no impact on the group signature itself. The last line of the table corresponds to our construction where the opening authority and the group manager are merged, which impacts security but not efficiency. 4. Efficiency and security comparisons using BLS12 curves (m represents the cost of one multiplication in the base field of the curve and k = log 2 p ) If we focus on constructions without random oracles, our group signature outperforms the recent construction of [START_REF] Backes | Signatures with flexible public key: Introducing equivalence classes for public keys[END_REF]: it halves both the signature size and the signature cost. We also note that it is competitive against the most efficient construction [START_REF] Pointcheval | Short randomizable signatures[END_REF] in the random oracle model (ROM). Indeed, while the signature size remains larger (double the size), the computational cost is quite similar and, more importantly, our signer no longer needs to perform operation in G T and so, does not need to implement the arithmetic in F q 12 , which is noticeable.

Group G1 G2 GT Cost 15k • m 38k • m 45k • m Table
We would like to add that this comparison was made targeting the 128-bit security level. At higher security levels, BLS12 curves might not be relevant anymore. For instance, at 256 bits of security, the authors from [START_REF] Bos | Exponentiating in pairing groups[END_REF] choose a BLS24 curve and different curve models for G 1 and G 2 , thus satisfying the condition 3e 1 + 1e 2 < 1e T . In that case, our group signature scheme is computationally the most efficient, even compared to the best alternative in the ROM [START_REF] Pointcheval | Short randomizable signatures[END_REF].

Conclusion

In this paper, we have introduced the most efficient group signature scheme proved secure without random oracles. Our construction is based on a tailored combination of the PS signature scheme and the FHS equivalence-class signature scheme, leading to a group signature consisting only of four elements in G 1 and one in G 2 . Its security mostly relies on the one of these signature schemes which have been widely used in cryptographic protocols, although we need to adapt the proof of PS signature to fit our construction.

Our scheme halves both the size and the computational cost compared to the most efficient alternative in the same model. It also significantly closes the gap with constructions in the ROM, showing that we can avoid this model without dramatically increasing complexity.

We nevertheless note that the hardness of the corresponding problem depends on the function h. For example, if h is constant then no adversary can succeed as soon as it makes (at least) one query to O.

Any EUF-CMA signature scheme can be selected here, without any impact on the complexity of the group signatures.

Acknowledgements

The authors are grateful for the support of the ANR through project ANR-16-CE39-0014 PERSOCLOUD and project ANR-18-CE-39-0019-02 MobiS5.