Groth-Sahai Olivier Blazy

Georg Fuchsbauer

Malika Izabachène

Amandine Jambert

Hervé Sibert

Damien Vergnaud

Batch

Keywords: Pairing-based cryptography, Batch verification, Groth-Sahai proof system

In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zeroknowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to a number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and manage to improve significantly the complexity of proof verification. We give explicit batch verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) and also for specific popular protocols relying on their methodology (namely Groth's group signatures and Belenkiy-Chase-Kohlweiss-Lysyanskaya's P-signatures).

Introduction

In a zero-knowledge proof system, a prover convinces a verifier via an interactive protocol that a mathematical statement is true, without revealing anything else than the validity of the assertion. In 1988, Blum, Feldman, and Micali [START_REF] Blum | Proving security against chosen cyphertext attacks[END_REF] showed that the use of a common random string shared between the prover and the verifier permits to design a zero-knowledge proof system for all NP-languages without requiring interaction. These proofs, called non-interactive zero-knowledge (NIZK), turned out to be a particularly useful tool in constructing cryptographic primitives. Unfortunately, their work (as well as subsequent results) did not yield efficient proofs. Until recently, the only way to construct efficient proofs was to rely on the random-oracle model (ROM) [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF], which has been subject to a series of criticisms starting with [START_REF] Canetti | The random oracle methodology, revisited (preliminary version)[END_REF].

In 2008, Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] proposed a way to produce efficient and practical NIZK and noninteractive witness-indistinguishable (NIWI) proofs for (algebraic) statements related to groups equipped with a bilinear map. In particular, they give proofs for the simultaneous satisfiability of a set of equations. They proposed three instantiations of their system based on different (mild) computational assumptions: the subgroup decision problem (SD), the symmetric external Diffie-Hellman problem (SXDH) and the decision linear problem (DLIN). Each one of these has already given rise to many applications (e.g. [BW06,BW07,CGS07,Gro07,GL07,BCKL08,BCC + 09]). While much more efficient than all previous proposals, their proof system still lacks in practicality compared to the ROM, since the verification of a single equation requires the computation of dozens of bilinear map evaluations by the verifier.

The aim of this paper is to optimize the verification procedure at the expense of slightly weakening the soundness of the proof system.

Prior Work. In the last twenty years, there has been a lot of work in cryptography in which expensive tasks are processed in batch rather than individually to achieve better efficiency. Batch cryptography was first introduced by Fiat [START_REF] Fiat | Batch RSA[END_REF], who proposed an algorithm to compute several private RSA key operations (with different exponents) through one full exponentiation and several small exponentiations. Batch cryptography is particularly relevant in settings where many exponentiations need to be verified together: many schemes were proposed to achieve batch verification of digital signatures (e.g. [ for DSA signatures) and it seems natural to apply such techniques to the verification of Groth-Sahai proofs, which require expensive evaluations of pairings. In 1998, Bellare, Garay and Rabin [START_REF] Bellare | Fast batch verification for modular exponentiation and digital signatures[END_REF] took the first systematic look at batch verification and described several techniques for conducting batch verification of exponentiations with high confidence. They proposed three generic methods called the random subset test, the small exponents test and the bucket test. More recently, Ferrara, Green, Hohenberger and Pedersen [START_REF] Ferrara | Practical short signature batch verification[END_REF], presented a detailed study on how to securely batch verify a set of pairing-based equations and some applications on existing signatures schemes.

Our Results. The main result of the paper is a significant reduction of the cost of Groth-Sahai proof systems by using batch verification techniques. In particular, we give efficient explicit verification procedures for the three1 instantiations proposed in [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]. The essence of our approach is a trade-off between soundness and efficiency: if the verification algorithm returns valid, the verifier is assured that all proved statements are indeed valid with overwhelming probability. The best improvements are for the proofs based on SXDH and DLIN, which are the ones with most practical relevance (see Sections 5 and 6). Table 1 summarizes the number of (dominant) pairing operations required to verify the different algebraic statements in Groth-Sahai terminology (see Section 3 for details).

In [START_REF] Camenisch | Batch verification of short signatures[END_REF], Camenisch et al. explicitly mentioned as an "exciting" open problem the development of fast batching schemes for various forms of anonymous authentication (such as group signatures and anonymous credentials). This paper is the first to address this issue in the standard security model by considering two schemes based on Groth-Sahai's methodology.

The first scheme we consider was proposed by Groth in 2007 [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF]. It is a constant-size group signature scheme whose security can be proved in the standard model (i.e. without relying on the random oracle heuristic). For illustrative purposes, we concentrate on the (simpler) variant of the scheme that provides CPA anonymity only. Even this variant does not achieve satisfactory efficiency-the verification of a signature requires the computation of 68 expensive pairing operations. In Section 7, we propose an improved verification procedure in which the total number of bilinear map evaluations drops to 11. In addition, if n ≥ 2 signatures (for the same group) have to be verified at once, we manage to decrease this number from 11 n to 4 n + 7.

In Section 8, we study the P-signature scheme2 proposed by Belenkiy, Chase, Kohlweiss and Lysyanskaya [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF]. Since anonymous credentials are an immediate consequence of P-signatures, we thereby apply our techniques to privacy-preserving authentication mechanisms. Belenkiy et al. proposed two instantiations of their protocol (based on SXDH and DLIN). They evaluated that the verification of the proof of possession of a signature would involve respectively 68 and 128 pairing evaluations. We show that this can be reduced to 15 and 12, respectively. Moreover, the number of pairing operations required to verify n ≥ 2 signatures is reduced to 2 n + 13 and 3 n + 9, respectively, by using our techniques 2 Preliminaries

Bilinear Groups

Since Groth-Sahai proof systems are for group-dependent languages, we summarize the basics of bilinear groups and pairing-based assumptions. In the sequel, we consider an algorithm G that, on input a security parameter λ, outputs a tuple (N, G 1 , G 2 , G T , e, g 1 , g 2 ), where G 1 , G 2 , G T are cyclic groups of order N , g 1 and g 2 generate G 1 and G 2 respectively, and e is an admissible bilinear map e : G 1 × G 2 → G T , which means that it is efficiently computable, e(g 1 , g 2 ) generates G T , and that e(u a , v b ) = e(u, v) ab holds for all u ∈ G 1 , v ∈ G 2 and a, b ∈ Z N .

Definition 1. Let G be a cyclic group of order N . The decisional Diffie-Hellman (DDH) assumption states that the distributions of (u, u x , u y , u z ) and (u, u x , u y , u x•y ) are computationally indistinguishable for a random group element u ∈ G and random scalars x, y, z ∈ Z N .

Definition 2. Consider a bilinear group (N, G, G T , e, g), where N = p • q is the product of two primes (and we have G 1 = G 2 = G). The subgroup decision (SD) assumption [START_REF] Boneh | Evaluating 2-DNF formulas on ciphertexts[END_REF] in G states that given a random element u ∈ G, it is computationally hard to decide whether u is in a subgroup of G.

Definition 3. Consider a bilinear group (p, G 1 , G 2 , G T , e, g 1 , g 2 ), where p is prime, output by G(λ). The symmetric external decision Diffie-Hellman (SXDH) assumption [START_REF] Ateniese | Practical group signatures without random oracles[END_REF] states that the DDH assumption holds in both G 1 and G 2 . Definition 4. Consider a bilinear group (p, G, G T , e, g), where p is prime (and we have

G 1 = G 2 = G).
The decision linear (DLIN) assumption [START_REF] Boneh | Short group signatures[END_REF] states that the two distributions (u, v, w, u a , v b , w c ) and (u, v, w, u a , v b , w a+b ) are computationally indistinguishable for random group elements u, v, w ∈ G and random scalars a, b, c ∈ Z p .

Notation

We let "•" denote the product of two elements either in Z N , in G or in G T . For equal-dimension vectors or matrices A and B of group elements, A B stands for their entry-wise product (i.e. it denotes their Hadamard product). For a vector or a matrix A = a i,j i,j of group elements and an integer x, we denote by A x the matrix a x i,j i,j . We will use •, • for bilinear products between vectors of either scalars or group elements. Let a, b ∈ Z n N and A, B ∈ G n . We define

a, b := n i=1 a i • b i a, B := n i=1 B a i i A, B := n i=1 e(A i , B i )
We employ Groth and Sahai's notation of a bilinear product

• : G n×k 1 × G n×k 2 → G k×k T (for k = 2, 3) defined as follows: c • d :=    n i=1 e(ci,1, di,1) • • • n i=1 e(ci,1, d i,k ) . . . . . . n i=1 e(c i,k , di,1) • • • n i=1 e(c i,k , d i,k )   
For the case G 1 = G 2 and k = 3 we define a symmetric variant

3 s • : G n×3 × G n×3 → G 3×3 T c s • d :=    n i=1 e(ci,1, di,1) n i=1 e(ci,1, di,2)
1 2 e(ci,2, di,1)

1 2
n i=1 e(ci,1, di,3)

1 2 e(ci,3, di,1)

1 2 n i=1 e(ci,2, di,1)
1 2 e(ci,1, di,2)

1 2 n i=1 e(ci,2, di,2) n i=1 e(ci,2, di,3) 1 2 e(ci,3, di,2) 1 2
n i=1 e(ci,3, di,1)

1 2 e(ci,1, di,3)

1 2 n i=1 e(ci,3, di,2)
1 2 e(ci,2, di,3)

1 2 n i=1 e(ci,3, di,3)    3 Groth-Sahai Proof Systems
We sketch the results of Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] on proofs of satisfiability of sets of equations over a bilinear group (N, G 1 , G 2 , G T , e, g 1 , g 2 ). Due to the complexity of their methodology, we merely give what is needed for our results and refer to the full version of [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] for any additional details. The three types of equations are the following:

A pairing-product equation over variables

X = (X 1 , . . . , X m ) ∈ G 1 and Y = (Y 1 , . . . , Y n ) ∈ G 2 is of the form A, Y • X , B • X , Γ Y = t T , (1)
defined by constants A ∈ G n 1 , B ∈ G m 2 , Γ = (γ i,j ) 1≤i≤m 1≤j≤n ∈ Z m×n N and t T ∈ G T .
A multi-scalar multiplication equation over variables

y ∈ Z n N and X ∈ G m 1 is of the form y, A • b, X • y, Γ X = T, (2)
defined by the constants

A ∈ G n 1 , b ∈ Z m N , Γ ∈ Z m×n N and T ∈ G 1 . A multi-scalar multiplication equation in group G 2 is defined analogously. A quadratic equation in Z N over variables x ∈ Z m N and y ∈ Z n N is of the form a, y + x, b + x, Γ y = t, (3)
defined by the constants a

∈ Z n N , b ∈ Z m N , Γ ∈ Z m×n N and t ∈ Z N .
The common reference string for the proof system is a key to make commitments to the variables of the different types. A proof of satisfiability is constructed by first committing to the variables of the respective equation and then constructing a "proof" for each equation. The latter proves that the committed values indeed satisfy the equation.

There are three instantiations based on the SD, the SXDH and the DLIN assumption, respectively. We present the last two (the instantiation based on the subgroup decision assumption is deferred to the appendix.

SXDH. The language is over a bilinear group (p, G 1 , G 2 , G T , e, g 1 , g 2 ) with p being prime. The commitment key consists of

u 1 = (u 1,1 , u 1,2 ) , u 2 = (u 2,1 , u 2,2 ) ∈ G 2 1 and v 1 = (v 1,1 , v 1,2 ) , v 2 = (v 2,1 , v 2,2 ) ∈ G 2 2 ; we write u = u 1 u 2 = u 1,1 u 1,2 u 2,1 u 2,2 and v = v 1 v 2 = v 1,1 v 1,2 v 2,1 v 2,2 . Let X ∈ G 1 , Y ∈ G 2 and x ∈ Z p . We define ι 1 (X) := (1, X), ι 2 (Y ) := (1, Y ), ι 1 (x) := (u x 2,1 , (u 2,2 g 1 ) x ) and ι 2 (x) := (v x 2,1 , (v 2,2 g 2 ) x ). To commit to X ∈ G 1 , one chooses randomness s 1 , s 2 ∈ Z p and sets c X := ι 1 (X) u s 1 1 u s 2 2 , a commitment to Y ∈ G 2 is defined as d Y := ι 2 (Y ) v s 1 1 v s 2 2 . To make a commitment to x ∈ Z p , which is in G 2 1 one chooses s ∈ Z p and sets c x := ι 1 (x) u s 1 , a commitment in G 2 2 is defined as d x := ι 2 (x) v s 1 .
To show satisfiability of a set of equations of the form (1), (2) or (3), one first makes commitments to a satisfying witness (i.e., an assignment to the variables of each equation) and then adds a "proof" per equation. Groth and Sahai describe how to construct these; for Type (1), they are in

G 2×2 2 × G 2×2 1 , for Type (2) they are in G 2×2 2 × G 2
1 and for Type (3) in G 2 2 × G 2 1 . The verification relations for the proofs are given in Section 5, where we also discuss how to optimize them. For convenience we define some notations. Let

t ∈ Z p , T 1 ∈ G 1 , T 2 ∈ G 2 and t T ∈ G T . Then we let 4 ι T (t T ) := 1 1 1 t T , ιT (T 1 ) := 1 1 e(T 1 , v 2,1 ) e(T 1 , v 2,2 g 2 )
, ιT (T 2 ) := 1 e(u 2,1 , T 2 ) 1 e(u 2,2 g 1 , T 2 ) ,

and ι T (t) := (u 2,1 , u 2,2 g 1 ) • (v 2,1 , v 2,2 g 2 ) t = e(u 2,1 , v 2,1 ) t e(u 2,1 , v 2,2 g 2 ) t e(u 2,2 g 1 , v 2,1
) t e(u 2,2 g 1 , v 2,2 g 2 ) t . For the sake of consistency with [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF],

for c ∈ G 1×2 1 and d ∈ G 1×2 2 we denote F (c, d) := [c • d].
4 We use the rectifications of ιT and ι T by [START_REF] Ghadafi | Groth-sahai proofs revisited[END_REF].

DLIN. In this instantiation, the language is over a bilinear group (p, G, G T , e, g) with p being prime. The commitment key u ∈ G 3×3 is of the form u 1 = (u 1,1 , 1, g), u 2 = (1, u 2,1 , g), u 3 = (u 3,1 , u 3,2 , u 3,3 ). Let X ∈ G and x ∈ Z p . We define ι(X) := (1, 1, X) and ι (x) := (u x 3,1 , u x 3,2 , (u 3,3 g) x ). To commit to X ∈ G, one chooses randomness s 1 , s 2 , s 3 ∈ Z p and sets c X := ι(X) u s 1 1 u s 2 2 u s 3 3 . To commit to x ∈ Z p , one chooses s 1 , s 2 ∈ Z p and computes c x := ι (x) u s 1 1 u s 2 3 . Due to the fact that G 1 = G 2 = G in this setting, the equations (1), (2) and (3) simplify to the following equations respectively:

A, Y • Y, Γ Y = t T (1 ) a, Y • x, B • x, Γ Y = T (2 ) x, b + x, Γ x = t (3 )
Groth and Sahai show how to construct "proofs" for each type of equation, where for Types (1') and (2'), the proof is in G 3×3 , whereas for Type (3') it is in G 2×3 . The verification relations for the proofs are given in Section 6.

We define the following notations. Let t ∈ Z p , T ∈ G and t T ∈ G T . Then we let5

ι T (t T ) :=   1 1 1 1 1 1 1 1 t T   , ιT (T ) :=    1 1 e(u 3,1 , T ) 1 2
1 1 e(u 3,2 , T )

1 2 e(u 3,1 , T )

1 2 e(u 3,2 , T )

1 2 e(u 3,3 g, T )    , and ι T (t) := (u 3,1 , u 3,1 , u 3,3 g) s • (u 3,1 , u 3,1 , u 3,3 g) t =
  e(u 3,1 , u 3,1 ) t e(u 3,1 , u 3,2 ) t e(u 3,1 , u 3,3 g) t e(u 3,2 , u 3,1 ) t e(u 3,2 , u 3,2 ) t e(u 3,2 , u 3,3 g) t e(u 3,3 g, u 3,1 ) t e(u 3,3 g, u 3,2 ) t e(u 3,3 g, u 3,3 g) t   .

Batch Verification of Pairing Equations

We address the problem to securely batch the verification of (potentially many) Groth-Sahai proofs.

We achieve a trade-off between soundness and efficiency: if the verification algorithm returns valid, the verifier is assured that all proved statements are indeed valid with overwhelming probability. Ferrara, Green, Hohenberger and Pedersen [START_REF] Ferrara | Practical short signature batch verification[END_REF] presented a detailed study on how to securely batch-verify a set of pairing-based equations, which we briefly recall here (see the full version of [START_REF] Ferrara | Practical short signature batch verification[END_REF] for any additional details).

Given a bilinear structure (N,

G 1 , G 2 , G T , e, g 1 , g 2 ), a pairing-based verification equation is a Boolean relation of the form: k i=1 e(f i , h i ) c i ? = A for k ∈ N, (f i , h i , c i ) ∈ G 1 × G 2 × Z N for i ∈ {1, . .

. , k} and A ∈ G T . A pairing-based verifier is an algorithm which given a pairing-based verification equation outputs yes if the Boolean relation holds, and no otherwise (except with negligible probability).

In order to design a pairing-based verifier for m pairing-based verification equations, one has to find a way to combine all equations. The technique proposed in [START_REF] Ferrara | Practical short signature batch verification[END_REF] consists in using the small exponents test proposed by Bellare et al. [START_REF] Bellare | Fast batch verification for modular exponentiation and digital signatures[END_REF], which here amounts to pick small random exponents δ 1 , . . . , δ m and checking whether m j=1 k j i=1 e(f i,j , h i,j ) c i,j δ j = m j=1 A δ j j holds. In order to further reduce the computational needs, three main techniques may be used:

1. Move the exponent into the pairing: Since, in practice, exponentiation in G T is more expensive than in G 1 and G 26 , this gives a first speed up. As we are working on pairings, we can also do the opposite if it allows another technique to apply:

e(f i , h i ) δ i → e(f δ i i , h i ) 2.
Move the product into the pairing: When two pairings have a common element, they can be combined to reduce the number of pairing computations: m j=1 e(f

δ j j , h i ) → e m j=1 f δ j j , h i 3.
Switch two products: Sometimes improvements can be made by moving a product from the first to the second component of a pairing (or vice-versa). k i=1 e m j=1 f

δ i,j j , h i ↔ m j=1 e f j , k i=1 h δ i,j i
The soundness of the pairing-based verifier based on the small exponents test is quantified in the following theorem [FGHP09, Theorem 3.2]: Theorem 1. Given m pairing-based verification equation, the small-exponents verifier described above with random exponents δ 1 , . . . , δ m of bit is a pairing-based batch verifier that accepts an invalid batch with probability at most 2 -.

Handling Invalid Proofs. In the case of verification of multiple proofs (as in Sections 7 and 8) if there is an invalid proof in the batch, then the verifier will reject the entire batch with high probability. A simple technique for finding invalid proofs in a batch consists in using a recursive divide-and-conquer approach [START_REF] Pastuszak | Identification of bad signatures in batches[END_REF]. Recently, more efficient techniques were proposed for pairing-based signatures (see e.g. [START_REF] Matt | Identification of multiple invalid signatures in pairing-based batched signatures[END_REF] and references therein) and they apply as well to our setting.

Instantiation 2: SXDH

Pairing-Product Equation

A proof ( c, d, π, θ) ∈ G m×2 1 × G n×2 2 × G 2×2 2 × G 2×2 1
of satisfiability of an equation of Type (1) is verified by checking the following equation.

ι 1 ( A) • d c • ι 2 ( B) c • Γ d = ι T (t T ) u • π θ • v . Let us denote u = u 1 u 2 = u 1,1 u 1,2 u 2,1 u 2,2 , v = v 1 v 2 = v 1,1 v 1,2 v 2,1 v 2,2 , A = (A j ) 1≤j≤n ∈ G n×1 1 , B = (B i ) 1≤i≤m ∈ G m×1 2 , c = (c i,k ) 1≤i≤m 1≤k≤2 ∈ G m×2 1 , d = (d j,k ) 1≤j≤n 1≤k≤2 ∈ G n×2 2 , and Γ = (γ i,j ) 1≤i≤m 1≤j≤n ∈ Z m×n p .
Plugging in the definitions from Section 3, the left hand side is equal to

      m i=1 e ci,1, n j=1 d γ i,j j,1 m i=1 e ci,1, Bi n j=1 d γ i,j j,2 n j=1 e Aj m i=1 c γ i,j i,2 , dj,1 n j=1 e(Aj, dj,2) m i=1 e ci,2, Bi n j=1 d γ i,j j,2       . While, if we denote π = π 1,1 π 1,2 π 2,1 π 2,2 , θ = θ 1,1 θ 1,2 θ 2,1 θ 2,2
, the right hand side is equal to e(u1,1, π1,1)e(u2,1, π2,1)e(θ1,1, v1,1)e(θ2,1, v2,1) e(u1,1, π1,2)e(u2,1, π2,2)e(θ1,1, v1,2)e(θ2,1, v2,2) e(u1,2, π1,1)e(u2,2, π2,1)e(θ1,2, v1,1)e(θ2,2, v2,1) tT e(u1,2, π1,2)e(u2,2, π2,2)e(θ1,2, v1,2)e(θ2,2, v2,2) .

By grouping pairings, we reduced the number of pairings on the left-hand side of the equation from 5m + 3n to 3m + 2n, while the right-hand side remains at 16 pairings. Using the techniques explained in Section 4, i.e., taking each element M i,j of the equation to a random power r i,j , multiplying all the components, and regrouping pairings, we get the following equation:

n j=1 e m i=1 c γ i,j i,1 r 1,1 Aj m i=1 c γ i,j i,2 r 2,1 , dj,1 n j=1 e m i=1 c γ i,j i,1 r 1,2 Aj m i=1 c γ i,j i,2 r 2,2 , dj,2 • m i=1 e c r 1,2 i,1 c r 2,2 i,2 , Bi = e(u r 1,1 1,1 u r 2,1 1,2 , π1,1)e(u r 1,1 2,1 u r 2,1 2,2 , π2,1)e(θ r 1,1 1,1 θ r 2,1 1,2 , v1,1)e(θ r 1,1 2,1 θ r 2,1 2,2 , v2,1) (4)
• e(u e Aj, d

r 1,2 1,1 u r 2,2 1,2 , π1,2)e(u r 1,2 2,1 u r 2,2 2,2 , π2,2)e(θ r 1,2 1,1 θ r 2,2 1,2 , v1,2)e(θ r 1,2 2,1 θ r 2,2 2,2 , v2,2) • t
r 2,1 j,1 d r 2,2 j,2 • m i=1 e ci,1, n j=1 d γ i,j j,1 r 1,1 Bi n j=1 d γ i,j j,2 r 1,2 • m i=1 e ci,2, n j=1 d γ i,j j,1 r 2,1 Bi n j=1 d γ i,j j,2 r 2,2
for the left side of the equation requires 2m + n pairings and 2mn + 4m + 2n exponentiations in G 2 .

Multi-Scalar Multiplication Equation in G 1

Here, we consider equations of Type (2) in G 1 (the case of equations in G 2 , which work analogously, is treated in Appendix B). The verification of a proof ( c, d , π, θ)

∈ G m×2 1 × G n×2 2 × G 2×2 2 × G 1×2
1 consists in checking the following:

ι 1 ( A) • d c • ι 2 ( b) c • Γ d = ιT (T 1 ) u • π F (θ, v 1 ) Let us denote A = (A j ) 1≤j≤n ∈ G n×1 1 , d = (d j,k ) 1≤j≤n 1≤k≤2 ∈ G n×2 2 , c = (c i,k ) 1≤i≤m 1≤k≤2 ∈ G m×2 1 , b = (b i ) 1≤i≤m ∈ Z m×1 p and Γ = (γ i,j ) 1≤i≤m 1≤j≤n
. The left hand-side is equal to

      m i=1 e(ci,1, v b i 2,1 n j=1 d j,1 γ i,j ) m i=1 e(ci,1, (v2,2g2) b i n j=1 d j,2 γ i,j ) m i=1 e(ci,2, v b i 2,1 n j=1 d j,1 γ i,j ) n j=1 e(Aj, d j,1 ) m i=1 e(ci,2, (v2,2g2) b i n j=1 d j,2 γ i,j ) n j=1 e(Aj, d j,2 )      
while the right-hand side is equal to e(θ1, v1,1)e(u1,1, π1,1)e(u2,1, π2,1) e(θ1, v1,2)e(u1,1, π1,2)e(u2,1, π2,2) e(θ2, v1,1)e(u1,2, π1,1)e(u2,2, π2,1)e(T1, v2,1) e(θ2, v1,2)e(u1,2, π1,2)e(u2,2, π2,2)e(T1, g2v2,2) By grouping the pairings, the number of pairings on the left-hand side member of the equation has already been reduced from 8m + 2n to 4m + 2n. Now, by using the batch technique, i.e., multiplying each member by a random value and multiplying all the members, we obtain on the left-hand side

n j=1 e m i=1 c γ i,j i,1 r 1,1 Aj m i=1 c γ i,j i,2 r 2,1 , d j,1 • n j=1 e m i=1 c γ i,j i,1 r 1,2 Aj m i=1 c γ i,j i,2 r 2,2 , d j,2 •e ( m i=1 c b i i,1 ) r 1,1 ( m i=1 c b i i,2 ) r 2,1 , v2,1 • e ( m i=1 c b i i,1 ) r 1,2 ( m i=1 c b i i,2 ) r 2,2 , v2,2g2
which requires 2mn+2m+4n+4 exponentiations in G 1 and 2n+2 pairing computations. The alternative expression

n j=1 e Aj, d j,1 r 2,1 d j,2 r 2,2 • m i=1 e ci,1, v b i 2,1 n j=1 d j,1 γ i,j r 1,1 (v2,2g2) b i n j=1 d j,2 γ i,j r 1,2 • m i=1 e ci,2, v b i 2,1 n j=1 d j,1 γ i,j r 2,1 (v2,2g2) b i n j=1 d j,2 γ i,j r 2,2
for the left side of the equation requires 2mn + 6m + 2n exponentiations in G 2 and 2m + n pairing computations.

On the right-hand side, the same technique achieves a reduction from 14 to 7 pairings:

e(θ r 1,1 1 θ r 2,1 2 , v1,1)e(θ r 2,1 1 θ r 2,2 2 , v1,2)e(u r 1,1 1,1 u r 2,1 1,2 , π1,1)e(u r 1,1 2,1 u r 2,1 2,2 , π2,1)e(u r 1,2 2,1 u r 2,2 2,2 , π1,2)e(u r 2,1 2,1 u r 2,2 2,2 , π2,2)e(T1, v r 2,1 2,1 (g2v2,2) r 2,2 )

Quadratic Equation

The verification of ( c

, d , π, θ) ∈ G m×2 1 × G n×2 2 × G 1×2 2 × G 1×2 1 for an equation of Type (3) consists in checking ι 1 ( a) • d c • ι 2 ( b) c • Γ d = ι T (t) F (u 1 , π) F (θ, v 1 ) . Let a = (a j ) 1≤j≤n ∈ Z n×1 p , b = (b i ) 1≤i≤m ∈ Z m×1 p , c = (c i,k ) 1≤i≤m 1≤k≤2 ∈ G n×2 1 , d = (d j,k ) 1≤j≤n 1≤k≤2 ∈ G n×2 2 , and Γ = (γ i,j ) 1≤i≤m 1≤j≤n ∈ Z m×n p . The left hand side is equal to       n j=1 e(u a j 2,1 , d j,1 ) m i=1 e(c i,1 , v2,1) b i n j=1 e(u a j 2,1 , d j,2 ) m i=1 e(c i,1 , v2,2g2) b i n j=1 e((u2,2g1) a j , d j,1 ) m i=1 e(c i,2 , v2,1) b i n j=1 e((u2,2g1) a j , d j,2 ) m i=1 e(c i,2 , v2,2g2) b i             n j=1 e m i=1 c i,1 γ i,j , d j,1 n j=1 e m i=1 c i,1 γ i,j , d j,2 n j=1 e m i=1 c i,2 γ i,j , d j,1 n j=1 e m i=1 c i,2 γ i,j , d j,2       =       m i=1 e(c i,1 , v b i 2,1 ) n j=1 e u a j 2,1 m i=1 c i,1 γ i,j , d j,1 m i=1 e(c i,1, (v2,2g2) b i ) n j=1 e u a j 2,1 m i=1 c i,1 γ i,j , d j,2 m i=1 e(c i,2, v b i 2,1 ) n j=1 e (u2,2g1) a j m i=1 c i,2 γ i,j , d j,1 m i=1 e(c i,2 , (v2,2g2) b i ) n j=1 e (u2,2g1) a j m i=1 c i,2 γ i,j , d j,2      
Denoting π = (π 1 , π 2 ) and θ = (θ 1 , θ 2 ), for the right-hand side we have

ι T (t) F (u 1 , π) F (θ, v 1 ) = e(u 1,1 , π 1 )e(θ 1 , v 1,1 )e(u 2,1 , v 2,1 ) t e(u 1,1 , π 2 )e(θ 1 , v 1,2 )e(u 2,1 , v 2,2 g 2 ) t e(u 1,2 , π 1 )e(θ 2 , v 1,1 )e(u 2,2 g 1 , v 2,1 ) t e(u 1,2 , π 2 )e(θ 2 , v 1,2 )e(u 2,2 g 1 , v 2,2 g 2 ) t
and therefore

      m i=1 e(c i,1 , v b i 2,1 ) n j=1 e u a j 2,1 m i=1 c i,1 γ i,j , d j,1 m i=1 e(c i,1, (v2,2g2) b i ) n j=1 e u a j 2,1 m i=1 c i,1 γ i,j , d j,2 m i=1 e(c i,2, v b i 2,1 ) n j=1 e (u2,2g1) a j m i=1 c i,2 γ i,j , d j,1 m i=1 e(c i,2 , (v2,2g2) b i ) n j=1 e (u2,2g1) a j m i=1 c i,2 γ i,j , d j,2      
= e(u1,1, π1)e(θ1, v1,1)e(u2,1, v2,1) t e(u1,1, π2)e(θ1, v1,2)e(u2,1, v2,2g2) t e(u1,2, π1)e(θ2, v1,1)e(u2,2g1, v2,1) t e(u1,2, π2)e(θ2, v1,2)e(u2,2g1, v2,2g2) t Optimizing the verification. By grouping the pairings, the number of pairings on the left-hand side member of the equation has been reduced from 8m + 8n to 4m + 4n. By using the batch technique, i.e., multiplying each member by a random value and multiplying all the members, we obtain on the left-hand side:

e m i=1 c i,1 b i r 1,1 m i=1 c i,2 b i r 2,1 , v2,1 • e m i=1 c i,1 b i r 1,2 m i=1 c i,2 b i r 2,2
, v2,2g2

• n j=1 e u a j 2,1 m i=1 c i,1 γ i,j r 1,1 (u2,2g1) a j m i=1 c i,2 γ i,j r 2,1 , d j,1 • n j=1 e u a j 2,1 m i=1 c i,1 γ i,j r 1,2 (u2,2g1) a j m i=1 c i,2 γ i,j r 2,2 , d j,2
which requires 2mn + 2m + 6n + 4 exponentiations in G 1 and 2n + 2 pairing computations. Alternatively, the left-hand side is also equal to e u2,1,

n j=1 d j,1 a j r 1,1 n j=1 d j,2 a j r 1,2 • e u2,2g2, n j=1 d j,1 a j r 2,1 n j=1 d j,2 a j r 2,2 • m i=1 e c i,1 , v b i 2,1 n j=1 d j,1 γ i,j r 1,1 (v2,2g2) b i n j=1 d j,2 γ i,j r 1,2 • m i=1 e c i,2 , v b i 2,1 n j=1 d j,1 γ i,j r 2,1 (v2,2g2) b i n j=1 d j,2 γ i,j r 2,2
which requires 2mn + 6m + 2n + 4 exponentiations in G 2 and 2m + 2 pairing computations. On the right-hand side, the same technique achieves a reduction from 12 to 6 pairings:

e(u r 1,1 1,1 u r 2,1 1,2 , π 1 )e(u r 1,2 1,1 u r 2,2 1,2 , π 2 )e(θ r 1,1 1 θ r 2,1 2 , v 1,1 )e(θ r 1,2 1 θ r 2,2 2 , v 1,2 ) e(u r 1,1 t 2,1 (u 2,2 g 1 ) r 2,1 t , v 2,1 )e(u r 1,2 t 2,1 (u 2,2 g 1 ) r 2,2 t , v 2,2 g 2 )
6 Instantiation 3: DLIN

Pairing-Product Equation

The verification relation of a proof ( d, φ) ∈ G n×3 × G 3×3 for equation Type (1 ) is the following:

ι( A) s • d d s • Γ d = ι T (t T ) u s • φ
For simplicity, we consider the squares of all G T elements in both sides of the equation. Writing Γ d as

n k=1 d γ i,k k,j 1≤i≤n 1≤j≤3
and replacing the bilinear product s

• by its definition, we get for the left-hand side

           n i=1 e(di,1, d γ i,k k,1 ) 2 n i=1 e(di,1, d γ i,k k,2 )e(di,2, d γ i,k k,1 ) n i=1
e(Ai, di,1)e(di,1, d

γ i,k k,3 )e(di,3, d γ i,k k,1 ) n i=1 e(di,2, d γ i,k k,1 )e(di,1, d γ i,k k,2 ) n i=1 e(di,2, d γ i,k k,2 ) 2 n i=1 e(Ai, di,2)e(di,2, d γ i,k k,3 )e(di,3, d γ i,k k,2 ) n i=1
e(Ai, di,1)e(di,3, d

γ i,k k,1 ) n i=1
e(Ai, di,2)e(di,3, d

γ i,k k,2 ) n i=1
e(Ai, di,3) 2 e(di,3, d

γ i,k k,3 ) 2 •e(di,1, d γ i,k k,3 ) •e(di,2, d γ i,k k,3 )           
and for the right-hand side:

           3 i=1 e(u i1 , φ i1 ) 2 3 i=1 e(u i1 , φ i2 )e(u i2 , φ i1 ) 3 i=1 e(u i1 , φ i3 )e(u i3 , φ i1 ) 3 i=1 e(u i2 , φ i1 )e(u i1 , φ i2 ) 3 i=1 e(u i2 , φ i2 ) 2 3 i=1 e(u i2 , φ i3 )e(u i3 , φ i2 ) 3 i=1 e(u i3 , φ i1 )e(u i1 , φ i3 ) 3 i=1 e(u i3 , φ i2 )e(u i2 , φ i3 ) t 2 T 3 i=1 e(u i3 , φ i3 ) 2           
Taking each element M i,j of the equation to the power of r i,j , multiplying everything, and regrouping pairings, we get the following for the left-hand side:

n i=1 e d i,1 , A r 1,3 +r 3,1 i d γ i,k 2•r 1,1 k,1 d γ i,k (r 1,2 +r 2,1 ) k,2 d γ i,k (r 1,3 +r 3,1 ) k,3 • e d i,2 , A r 2,3 +r 3,2 i d γ i,k (r 1,2 +r 2,1 ) k,1 d γ i,k 2•r 2,2 k,2 d γ i,k (r 2,3 +r 3,2 ) k,3 • e d i,3 , A 2•r 3,3 i d γ i,k (r 1,3 +r 3,1 ) k,1 d γ i,k (r 2,3 +r 3,2 ) k,2 d γ i,k 2r 3,3 k,3 (5)
and for the right-hand side:

3 i=1 e u i,1 , φ 2•r 1,1 i,1 φ r 1,2 +r 2,1 i,2 φ r 1,3 +r 3,1 i,3 • e u i,2 , φ r 1,2 +r 2,1 i,1 φ 2•r 2,2 i,2 φ r 2,3 +r 3,2 i,3
• e u i,3 , φ

r 1,3 +r 3,1 i,1 φ r 2,3 +r 3,2 i,2 φ 2•r 3,3 i,3 • t 2r 3,3 T
Due to the fact that u 1,2 = u 2,1 = 1, and u 1,3 = u 2,3 this simplifies to:

e u 1,1 , φ 2•r 1,1 1,1 φ r 1,2 +r 2,1 1,2 φ r 1,3 +r 3,1 1,3 • e u 1,3 , (φ 1,1 φ 2,1 ) r 1,3 +r 3,1 (φ 1,2 φ 2,2 ) r 2,3 +r 3,2 (φ 1,3 φ 2,3 ) 2•r 3,3 e u 2,2 , φ r 1,2 +r 2,1 2,1 φ 2•r 2,2 2,2 φ r 2,3 +r 3,2 2,3 • e u 3,1 , φ 2•r 1,1 3,1 φ r 1,2 +r 2,1 3,2 φ r 1,3 +r 3,1 3,3 • e u 3,2 , φ r 1,2 +r 2,1 3,1 φ 2•r 2,2 3,2 φ r 2,3 +r 3,2 3,3 • e u 3,3 , φ r 1,3 +r 3,1 3,1 φ r 2,3 +r 3,2 3,2 φ 2•r 3,3 3,3 • t 2r 3,3 T
In total we reduced the number of pairings from 12n + 27 to 3n + 6 pairings at the expense of adding 9n 2 + 3n exponentiations in G and one exponentiation in G T .

Multi-Scalar Multiplication Equation

The verification equation of a proof ( c, d, φ), with φ ∈ G 3×3 , of an equation of Type (2 ) is the following:

ι ( a) s • d c s • ι( B) c s • Γ d = ιT (T ) u s • φ Γ d can be written as n k=1 d γ i,k k,j 1≤i≤m 1≤j≤3
. The left-hand side of the equation is thus

u a i 3,1 , u a i 3,2 , (u 3,3 g) a i 1≤i≤n s • d i,1 , d i,2 , d i,3 g 1≤i≤n c i,1 , c i,2 , c i,3 1≤i≤m s • 1, 1, B i 1≤i≤m c i,1 , c i,2 , c i,3 1≤i≤m s • (Γ d) i,1 , (Γ d) i,2 , (Γ d) i,3 1≤i≤m
Considering the squares of all matrix elements, this is written out as

    n i=1 e u a i 3,1 , di,1 2 n i=1 e u a i 3,1 , di,2 e u a i 3,2 , di,1 n i=1 e u a i 3,1 , di,3 e (u3,3g) a i , di,1g n i=1 e u a i 3,2 , di,1 e u a i 3,1 , di,2 n i=1 e u a i 3,2 , di,2 2 n i=1 e u a i 3,2 , di,3 e (u3,3g) a i , di,2g n i=1 e (u3,3g) a i , di,1 e u a i 3,1 , di,3 n i=1 e (u3,3g) a i , di,2 e u a i 3,2 , di,3 n i=1 e (u3,3g) a i , di,3g 2        1 1 m i=1 e(ci,1, Bi) 1 1 m i=1 e(ci,2, Bi) m i=1 e(ci,1, Bi) m i=1 e(ci,2, Bi) m i=1 e(ci,3, Bi)        m i=1 e(ci,1, d γ i,k k,1 ) 2 m i=1 e(ci,1, d γ i,k k,2 )e(ci,2, d γ i,k k,1 ) m i=1 e(ci,1, d γ i,k k,3 )e(ci,3, d γ i,k k,1 ) m i=1 e(ci,2, d γ i,k k,1 )e(ci,1, d γ i,k k,2 ) m i=1 e(ci,2, d γ i,k k,2 ) 2 m i=1 e(ci,2, d γ i,k k,3 )e(ci,3, d γ i,k k,2 ) m i=1 e(ci,3, d γ i,k k,1 )e(ci,1, d γ i,k k,3 ) m i=1 e(ci,3, d γ i,k k,2 )e(ci,2, d γ i,k k,3 ) m i=1 e(ci,3, d γ i,k k,3 ) 2    
Using the batching technique, we get the following left-hand side:

n i=1 e u 2a i r 1,1 3,1 u a i (r 1,2 +r 2,1 ) 3,2
(u 3,3 g) a i •(r 1,3 +r 3,1 ) , d i,1 ) • e u a i (r 1,2 +r 2,1 ) 3,1

u 2a i r 2,2 3,2
(u 3,3 g) a i •(r 2,3 +r 3,2 ) , d i,2 )

• e u a i (r 1,3 +r 3,1 ) 3,1

u a i (r 2,3 +r 3,2 ) 3,2 (u 3,3 g) a i •2r 3,3 , d i,3 • m i=1 e c i,1 , B r 1,3 +r 3,1 i ( d γ i,k k,1 ) 2r 1,1 ( d γ i,k k,2 ) r 1,2 +r 2,1 ( d γ i,k k,3 ) r 1,3 +r 3,1 • e c i,2 , B r 2,3 +r 3,2 i ( d γ i,k k,1 ) r 1,2 +r 2,1 ( d γ i,k k,2 ) 2r 2,2 ( d γ i,k k,3 ) r 2,3 +r 3,2 • e c i,3 , B 2r 3,3 i ( d γ i,k k,1 ) r 3,1 +r 1,3 ( d γ i,k k,2 ) r 3,2 +r 2,3 ( d γ i,k k,1 ) 2r 3,3 ,
The right-hand side is similar to Section 6.1: e(g, T ) 2r 3,3 e u1,1, φ

2•r 1,1 1,1 φ r 1,2 +r 2,1 1,2 φ r 1,3 +r 3,1 1,3
• e u1,3, (φ1,1φ2,1) r 1,3 +r 3,1 (φ1,2φ2,2) r 2,3 +r 3,2 (φ1,3φ2,3) 2•r 3,3 e u2,2, φ

r 1,2 +r 2,1 2,1 φ 2•r 2,2 2,2 φ r 2,3 +r 3,2 2,3 • e u3,1, φ 2•r 1,1 3,1 φ r 1,2 +r 2,1 3,2 (φ3,3T ) r 1,3 +r 3,1 • e u3,2, φ r 1,2 +r 2,1 3,1 φ 2•r 2,2 3,2 (φ3,3T ) r 2,3 +r 3,2 • e u3,3, φ r 1,3 +r 3,1 3,1 φ r 2,3 +r 3,2 3,2 (φ3,3T ) 2•r 3,3
In total, we reduced from 9n + 12m + 27 to 3n + 3m + 6 pairings.

Quadratic Equation

The verification of a proof ( c, φ) ∈ G n×3 × G 2×3 for an equation of Type (3 ) consists in checking the following:

c s • (ι ( b)) c s • Γ c = ι T (t) v s • φ ,
where the commitment key (u 1 , u 2 , u 3 ) defines the function ι as ι (b) = (u b 3,1 , u b 3,2 , (u 3,3 g) b ) and v as (u 1 , u 2 ). We develop the left-hand side of the equation:

c i,1 , c i,2 , c i,3 1≤i≤n s • u b i 3,1 , u b i 3,2 , u 3,3 g b i 1≤i≤n c i,1 , c i,2 , c i,3 1≤i≤n s • (Γ c) i,1 , (Γ c) i,2 , (Γ c) i,3 1≤i≤n
which is written out as

     n i=1 e(ci,1, u b i 3,1 ) 2 n i=1 e(ci,1, u b i 3,2 )e(ci,2, u b i 3,1 ) n i=1 e(ci,1, (u3,3g) b i )e(ci,3, u b i 3,1 ) n i=1 e(ci,2, u b i 3,1 )e(ci,1, u b i 3,2 ) n i=1 e(ci,2, u b i 3,2 ) 2 n i=1 e(ci,2, (u3,3g) b i )e(ci,3, u b i 3,2 ) n i=1 e(ci,3, u b i 3,1 )e(ci,1, (u3,3g) b i ) n i=1 e(ci,3, u b i 3,2 )e(ci,2, (u3,3g) b i ) n i=1 e(ci,3, (u3,3g) b i ) 2      1 2      n i=1 e(ci,1, c γ i,k k,1 ) 2 n i=1 e(ci,1, c γ i,k k,2 )e(ci,2, c γ i,k k,1 ) n i=1 e(ci,1, c γ i,k k,3 )e(ci,3, c γ i,k k,1 ) n i=1 e(ci,2, c γ i,k k,1 )e(ci,1, c γ i,k k,2 ) n i=1 e(ci,2, c γ i,k k,2 ) 2 n i=1 e(ci,2, c γ i,k k,3 )e(ci,3, c γ i,k k,2 ) n i=1 e(ci,3, c γ i,k k,1 )e(ci,1, c γ i,k k,3 ) n i=1 e(ci,3, c γ i,k k,2 )e(ci,2, c γ i,k k,3 ) n i=1 e(ci,3, c γ i,k k,3 ) 2      1 2
Multiplying all matrix elements after taking them to a random power (and squaring everything for simplicity), we obtain the following batched version:

n i=1 e ci,1, u b i •2r 1,1 3,1 u b i •(r 1,2 +r 2,1 ) 3,2 (u3,3g) b i •(r 1,3 +r 3,1 ) c γ i,k •2r 1,1 k,1 c γ i,k •(r 1,2 +r 2,1 ) k,2 c γ i,k •(r 1,3 +r 3,1 ) k,3 e ci,2, u b i •(r 1,2 +r 2,1 ) 3,1 u b i •2r 2,2 • 3,2 (u3,3g) b i •(r 2,3 +r 3,2 ) c γ i,k •(r 1,2 +r 2,1 ) k,1 c γ i,k •2r 2,2 k,2 c γ i,k •(r 2,3 +r 3,2 ) k,3 e ci,3, u b i •(r 1,3 +r 3,1 ) 3,1 u b i •(r 2,3 +r 3,2 ) 3,2 (u3,3g) b i •2r 3,3 c γ i,k •(r 1,3 +r 3,1 ) k,1 c γ i,k •(r 2,3 +r 3,2 ) k,2 c γ i,k •2r 3,3 k,3
On the right hand side we have that ι T (t) v which batches to e u1,1, φ

2•r 1,1 1,1 φ r 1,2 +r 2,1 1,2 φ r 1,3 +r 3,1 1,3 • e u2,2, φ r 1,2 +r 2,1 2,1 φ 2•r 2,2 2,2 φ r 2,3 +r 3,2 2,3
• e u1,3, (φ1,1φ2,1) r 1,3 +r 3,1 (φ1,2φ2,2) r 2,3 +r 3,2 (φ1,3φ2,3) 2•r 3,3

• e(u3,1, u

2tr 1,1 3,1 u 2tr 1,2 3,2 (u3,3g) 2tr 1,3 )e(u3,2, u 2tr 2,1 3,1 u 2tr 2,2 3,2
(u3,3g) 2tr 2,3 )e(u3,3g, u

2tr 3,1 3,1 u 2tr 3,2 3,2 (u3,3g) 2tr 3,3 ).
which means a reduction from 18n + 24 pairings to 3n + 6 pairings.

7 Application 1: Groth's Group Signatures

Description

We demonstrate our techniques by applying them to one of the most practical group signature schemes in the standard model to date: Groth's construction [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF]. Groth proposed a methodology of transforming certified signatures [BFPW07] that respect a certain structure into group signatures using Groth-Sahai NIWI proofs:

a member picks keys for a certified signature scheme and asks the issuer to certify her public verification key for the signature scheme; to produce a group signature, the member will make a certified signature, encrypt it and then use NIWI proofs to demonstrate that the ciphertext contains a valid certified signature.

Groth proposed an efficient certified signature scheme based on the so called q-U assumption (see [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF] for details). In the CPA-anonymous version7 of the scheme, the issuer's public key is a triple

(f, h, T ) ∈ G 2 × G T (
The fact that a is given in the clear is not a problem since the certificate is malleable, so the group member can unlinkably re-randomize it each time she signs a message. A group signature is thus of the form (a, d b , d v , d σ , ψ, φ), where ψ and φ denote the Groth-Sahai proofs for the two equations in (6), respectively. We first instantiate our generic batch construction to verify a single signature more efficiently and then show how to verify multiple signatures at once. The first equation is of a particular form that allows for more efficient proofs and verification. We describe the verification relations and the batch verification in the next section.

Batching Linear Pairing-Product Equations

We consider a special case of pairing-product equations for which Γ = 0, called linear equations, i.e., the equation is of the following form: A, Y = t T , that is n i=1 e(A i , Y i ) = t T . In this case, the proof simplifies to three group elements and is verified as follows (taking into account that u 1,2 = u 2,1 = 1, and u 1,3 = u 2,3 ): Ai,d s 1 i,1 d s 2 i,2 d s 3 i,3 ) = t s 3 T e(u11, ψ s 1 1 ) e(u13, (ψ1ψ2) s 3 ) e(u22, ψ s 2 2 ) e(u31, ψ s 1 3 ) e(u32, ψ s 2 3 ) e(u33, ψ s 3 3 ) .

n i=1 e(A i , d i,1 ) = e(u 11 , ψ 1 ) e(u 31 , ψ 3 ) n i=1 e(A i , d i,2 ) = e(u 22 , ψ 2 ) e(u 32 , ψ 3 ) n i=1 e(A i , d i,3 ) = t T e(u 13 , ψ 1 ψ 2 ) e(u
(7)

7.3 Batching the Equations for One Group Signature 1st Equation. Instantiating (7) for first equation in (6), we get, after some more optimization (shifting e(a, h -1 )) s 3 to the left-hand side of the equation) Multiplying the two equations we get a single verification relation of the following form: Analysis. With no use of batching techniques, the verification of a single signature takes for the first equation 13 pairings and for the second 20 pairings for the left-hand side and 35 for its right-hand side. This is an overall of 68 pairing evaluations, compared to 11 for the batched verification.

e(d s 1 v,1 d s 2 v,2 (d v,3 h) s 3 , a) e(d s 1 b,1 d s 2 b,2 d s 3 b,3 , f ) = = T s 3 e(u 11 , ψ s 1 1 ) e(u 13 , (ψ 1 ψ 2 ) s 3 ) e(u 22 , ψ s 2 2 ) e(u 31 , ψ s 1 3 ) e(u 32 , ψ s 2 3 ) e(u 33 , ψ s 3 3 ) 2nd Equation. Setting A := g m 1 , Y := σ v , Γ := 0 1 0 0 , t T := e(g,
e(d s 1 v,1 d s 2 v,2 (dv,3h) s 3 , a) e(d s 1 b,1 d s 2 b,2 d s 3 b,3 , f )e

Batching Several Group Signatures

Consider the situation where we want to verify multiple group signatures at once. That is given a group public key (f, h, T, u 11 , u 13 , u 22 , u 31 , u 32 , u 33 ) and n group signatures

a (k) , d (k) b , d (k) v , d (k) σ , (ψ (k) i ) 1≤i≤3 , (φ (k) ij ) 1≤i,j≤3 .
Using the same technique of taking each of the (new) equations to the power of some randomness and multiplying them, we can unify the pairings e(•, f ) on the left-hand side and all pairings (which are of the form e(u ij , •)) on the right-hand side. Instead of 11n pairings needed when checking each equation, the batched version only requires 4n+7 pairings.

8 Application 2: Belenkiy-Chase-Kohlweiss-Lysyanskaya's P-signatures

Description

Belenkiy et al. formalized in [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF] digital signature schemes with an additional non-interactive proof of signature possession that they called P-signature schemes. They proposed two constructions9 : the first one relies on the weak Boneh-Boyen signature scheme [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF] while the second one is inspired by its full version.

Since Belenkiy et al.'s first scheme relies on a rather strong assumption, we consider only their second proposal: a signature σ on a message m ∈ Z p is a triple σ g,h) and e(f, C 2 ) = e(C 3 , w), where f , g are (public) generators of G 1 , h is a (public) generator of G 2 and v, w ∈ G 2 are parts of the signer's public key. To prove the possession of such a signature, a prover forms the Groth-Sahai commitments c 1 , c 2 and c 3 for the group elements C 1 , M 1 = f m , C 3 in G 1 and d 1 and d 2 for the group elements M 2 = h m and C 2 in G 2 (respectively) and provides a proof that they satisfy:

= (C 1 , C 2 , C 3 ) ∈ G 1 × G 2 × G 1 such that e(C 1 , vh m C 2 ) = e(
e(C 1 , vM 2 C 2 ) = e(g, h), e(f, C 2 ) = e(C 3 , w) and e(f, M 2 ) = e(M 1 , h) (8)

SXDH Instantiation

In [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], the authors evaluated that the verification of the proof in the SXDH instantiation requires the computation of 68 pairings. In Appendix C we show that it can be reduced to 15.

DLIN Instantiation

As in Section 7, the last two pairing-product equations from (8) are actually linear pairing-product equations. We denote the Groth-Sahai commitments for the group elements

C 1 , C 2 , C 3 , M 1 = f m , M 2 = h m in G by d 1 ,d 2 , d 3
, d 4 and d 5 (respectively) and φ, ψ and θ the proofs that they satisfy the first, the second and the third equation (respectively).

For the first equation, setting and substituting

A =   v 1 1   , d =   d 1 d 2 d 5   , Γ =   0 1 1 0 0 0 0 0 0   and t T = e(g, g)
in (5), we get: e d1,1, (v d2,3 d5,3) r 1,3 +r 3,1 (d2,1 d5,1) 2r 1,1 (d2,2 d5,2) (r 1,2 +r 2,1 ) e d1,2, (v d2,3 d5,3) r 2,3 +r 3,2 (d2,1 d5,1) r 1,2 +r 2,1 (d2,2 d5,2) 2r 2,2

• e d1,3, (v d2,3 d5,3) 2r 3,3 (d2,1 d5,1) r 1,3 +r 3,1 (d2,2 d5,2) r 2,3 +r 3,2 = e u1,1, φ

2•r 1,1 1,1 φ r 1,2 +r 2,1 1,2 φ r 1,3 +r 3,1 1,3
• e u1,3, (φ1,1φ2,1) r 1,3 +r 3,1 (φ1,2φ2,2) r 2,3 +r 3,2 (φ1,3φ2,3) 2•r 3,3 e u2,2, φ

r 1,2 +r 2,1 2,1 φ 2•r 2,2 2,2 φ r 2,3 +r 3,2 2,3
• e u3,1, φ

2•r 1,1 3,1 φ r 1,2 +r 2,1 3,2 φ r 1,3 +r 3,1 3,3 • e u3,2, φ r 1,2 +r 2,1 3,1 φ 2•r 2,2 3,2 φ r 2,3 +r 3,2 3,3 • e u3,3, φ r 1,3 +r 3,1 3,1 φ r 2,3 +r 3,2 3,2 φ 2•r 3,3 3,3
• e(g, g) 2r 3,3

With the substitution

A = f w -1 , d = d 2 d 3
, and t T = 1 and

A = f h -1 , d = d 5 d 4
, and t T = 1 (respectively) in (7), we obtain the second and third equation. Once the three equations multiplied, we obtain:

e d1,1, (v d2,3 d5,3) r 1,3 +r 3,1 (d2,1 d5,1) 2r 1,1 (d2,2 d5,2) (r 1,2 +r 2,1 ) e d1,2, (v d2,3 d5,3) r 2,3 +r 3,2 (d2,1 d5,1) r 1,2 +r 2,1 (d2,2 d5,2) 2r 2,2 e d1,3, (v d2,3 d5,3) 2r 3,3 (d2,1 d5,1) r 1,3 +r 3,1 (d2,2 d5,2) r 2,3 +r 3,2 e(f, d s 1 2,1 d s 2 2,2 d s 3 2,3 d t 1 5,1 d t 2 5,2 d t 3 5,3 )e(w -1 , d

s 1 3,1 d s 2 3,2 d s 3 3,3 )e(h -1 , d t 1 4,1 d t 2 4,2 d t 3 4,3 ) = e u1,1, φ 2•r 1,1 1,1 φ r 1,2 +r 2,1 1,2 φ r 1,3 +r 3,1 1,3 ψ s 1 1 θ t 1 1
• e u1,3, (φ1,1φ2,1) r 1,3 +r 3,1 (φ1,2φ2,2) r 2,3 +r 3,2 (φ1,3φ2,3) 2•r 3,3 (ψ1ψ2) s 3 (θ1θ2) t 3

• e u2,2, φ

r 1,2 +r 2,1 2,1 φ 2•r 2,2 2,2 φ r 2,3 +r 3,2 2,3 ψ s 2 2 θ t 2 2 e u3,1, φ 2•r 1,1 3,1 φ r 1,2 +r 2,1 3,2 φ r 1,3 +r 3,1 3,3 ψ s 1 3 θ t 1 3 • e u3,2, φ r 1,2 +r 2,1 3,1 φ 2•r 2,2 3,2 φ r 2,3 +r 3,2 3,3 ψ s 2 3 θ t 2 3 e u3,3, φ r 1,3 +r 3,1 3,1 φ r 2,3 +r 3,2 3,2 φ 2•r 3,3 3,3
ψ s 3 3 θ t 3 3 e(g, g) 2r 3,3

In [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], the authors evaluated that the verification of the proof in the DLIN instantiation requires the computation of 126 pairings. With our result, we prove it can be reduced to 12.

Batching Several P-Signatures. As in the previous section, in the situation where we want to verify multiple P-signatures at once, we can unify the pairings containing f, h and w on the left-hand side and all pairings (which are of the form e(u i,j , •)) on the right-hand side. Instead of 15n (resp. 12n) pairings needed when checking each equation, the batched version only requires 2n + 13 (resp. 3n + 9) pairings.

Conclusion

In this paper, we presented efficiency improvements for the verification of Groth-Sahai non-interactive (zero-knowledge and witness-indistinguishable) proofs and two privacy-preserving authentication schemes (with an improvement in efficiency of up to 90% for the number of (dominant) pairing operations). These results can be combined with known methods to compute the product of many pairing evaluations efficiently [START_REF] Granger | On Computing Products of Pairings[END_REF]. Our results notably provide the first algorithm to batch-verify a group signature scheme in the standard model (an open problem raised in [START_REF] Ferrara | Practical short signature batch verification[END_REF]) and (surprisingly) demonstrate that thanks to batch verification techniques, the DLIN instantiation of the Groth-Sahai proof system may be the most efficient implementation for the verification of a single signature.

A Instantiation 1: Subgroup Membership

A.1 Description of Groth-Sahai Proof System

For the Subgroup Decision instantiation, the language is over a bilinear group (N, G, G T , e, g) where N = pq is a product of two primes and with generator g. The commitment key consists of one element u in G, chosen to either generate G itself or to generate G q , its subgroup of order q. Under the SD assumption, the two choices are indistinguishable.

Let X ∈ G and x ∈ Z N . We define ι(X) = X and ι (x) = g x . To commit to X ∈ G, one chooses randomness r ∈ Z N and sets c X := ι(X) • u r . To make a commitment to x ∈ Z N , one chooses r ∈ Z p and sets c x := ι (x) • u r .

To show satisfiability of a set of equations of the form (1 ), (2 ) or (3 ), one first makes commitments to a satisfying witness (i.e., an assignment to the variables of each equation) and then adds a "proof" per equation. Groth and Sahai describe how to construct these; for all equations, they are a single element in G. The verification relations for the proofs are given in the rest of the section, where we also discuss how to optimize them.

A.2 Pairing-Product Equation

A pairing-product equation is of the form

A, Y • Y, Γ Y = t T , that is n i=1 e(A i , Y i ) • n i=1 • n j=1 e(Y i , Y j ) γ ij = t T (9)
Given a vector of commitments D, a proof φ ∈ G is verified by the following equation:

n i=1 e(A i , D i ) n i=1 n j=1 e(D i , D j ) γ ij = t T • e(u, φ)
By applying the different techniques explained in 4, it becomes:

n i=1 e(A i , D i ) n i=1 n j=1 e(D i , D j ) γ ij = n i=1   e(D i , A i ) e(D i , n j=1 D γ ij j )   n i=1 e(D i , A i n j=1 D γ ij j ) = t T e(U, φ) A.3 Multi-Scalar Multiplication A multi-scalar multiplication is of the form a, Y • x, B • x, Γ Y = T . A proof φ ∈ G is verified by n j=1 e(g a i , D j ) • m i=1 e(C i , B i ) • m i=1 n j=1 e(C i , D j ) γ ij = e(g, T )e(u, φ)
By applying the different techniques to batch computation, we obtain:

e(g, n j=1 D a j j ) • m i=1 e(C i , B i • n j=1 D γ i,j j ) = e (g, T ) e (u, φ) A.4 Quadratic Equation A quadratic equation is of the form x, b + x, Γ x = t. A proof φ ∈ G is verified by m i=1 e(C i , g b i ) • m i=1 m j=1 e(C i , C j ) γ ij = e(g, g) t e(u, φ)
By applying the different techniques to batch computation:

m i=1 e(C i , g b i • m j=1 C γ ij j
) = e(g, g) t e(u, φ)

A.5 Batching in Composite Groups

When based on the SXDH or on the DLIN assumption, GS proof systems are instantiated in primeorder bilinear groups. In such groups, the small exponents test result can be trusted as the probability of accepting an invalid input is 2 -, with being the bit length of the random exponents [START_REF] Ferrara | Practical short signature batch verification[END_REF]. However, in the case of the subgroup decision assumption, the setup is a bilinear group of composite order N = pq. Even though the verification equations for relations consist of a single equation per relation, the small exponent test can be used to verify several relations at once, or to perform a batch verification of the equations for a given relation for several executions of a protocol.

If one wants to verify the validity of multiple Groth-Sahai proofs, it is thus necessary to evaluate how much the small exponent test can be trusted in this setup: e(f i j , h i j ) c i j δ j = m j=1 A δ j j accepts an invalid set of claims with probability at most max(p, q) • 2 -. Proof. For every j in [1, m], one can write A j = e(g 1 , g 2 ) a(j) and k j i=1 e(f i j , h i j ) c i j = e(g 1 , g 2 ) c(j) . With these notations, the batch equation becomes m j=1 e(g 1 , g 2 ) δ j (c(j)-a(j)) = 1 .

Theorem 2. Let PSetup(1 k ) → (N, g 1 , g 2 , G 1 , G 2 , G T ,
The batch equation yields a correct verification if and only if c(j) -a(j) = 0 for all j. Suppose now that verification succeeds with c(1) -a(1) non-zero. Then, we have

δ 1 (c(1) -a(1)) = - m j=2 δ j (c(j) -a(j)) mod n.
If c(1) -a(1) and n are coprime then c(1) -a(1) is invertible in Z n , so there exists a single value of δ 1 that satisfies the equation. Suppose now that c(1) -a(1) and n are not coprime. This is the case if and only if c(1) -a(1) is a multiple of p or q. Suppose for instance that c(1) -a(1) is a multiple of p. Similarly, if c(1) -a(1) is a multiple of q then either the batch equation has no solution in δ 1 , or it has q solutions. Depending on his role and capacities, an adversary may ensure that all the c(j) -a(j) are multiples of p, with p being the biggest prime factor of n. In this worst case, the probability that the verification succeeds with wrong input is P ≤ p • 2 -, which yields the result.

Then, the batch equation has a solution if and only if -

B Multi-Scalar Multiplication Equation in G 2

We consider equations of Type (2) in G 2 . For each such multiplication, the verification of (π, θ) ∈ G 1×2 2 × G 2×2 1 consists in checking the following:

ι 1 ( a) • d c • ι 2 ( B) c • Γ d = ιT (T 2 ) F (u 1 , π) θ • v . We denote a = (a j ) 1≤j≤n ∈ Z n×1 p , c = c i,k 1≤i≤m 1≤k≤2 ∈ G m×2 1 , d = (d j,k ) 1≤j≤n 1≤k≤2 ∈ G n×2 2 , B = (B i ) 1≤i≤m ∈ G m×1 2 and Γ = (γ i,j ) 1≤i≤m 1≤j≤n ∈ Z n×n p . The left hand side is equal to       n j=1 e u a j 2,1 m i=1 c γ i,j i,1 , d j,1 m i=1 e(c i,1 , B i ) n j=1 e u a j 2,1 c γ i,j i,1 , d j,2 n j=1 e (u 2,2 g 1 ) a j m i=1 c γ i,j i,2 , d j,1 m i=1 e(c i,2 , B i ) n j=1 e (u 2,2 g 1 ) a j c γ i,j i,2 , d j,2       If we denote π = (π 1 , π 2 ), θ = θ 1,1 θ 1,2 θ 2,1 θ 2,2
, we have:

ιT (T 2 ) F (u 1 , π) θ • v = e(u 2,1 , π 1 )e(θ 1,1 , v 1,1
)e(θ 2,1 , v 2,1 ) e(u 2,1 , π 2 )e(θ 1,1 , v 1,2 )e(θ 2,1 , v 2,2 )e(u 2,1 , T 2 ) e((u 2,2 g 1 ), π 1 )e(θ 1,2 , v 1,1 )e(θ 2,2 , v 2,1 ) e((u 2,2 g 1 ), π 2 )e(θ 1,2 , v 1,2 )e(θ 2,2 , v 2,2 )e(u 2,2 g 1 , T 2 ) and therefore

      n j=1 e u a j 2,1 m i=1 (c i,1 ) γ i,j , d j,1 m i=1 e(c i,1 , B i ) n j=1 e u a j 2,1 c γ i,j i,1 , d j,2 n j=1 e (u 2,1 g 1 ) a j m i=1 c γ i,j i,2 , d j,1 m i=1 e(c i,2 , B i ) n j=1 e (u 2,1 g 1 ) a j c γ j,i i,2 , d j,2      
= e(u 2,1 , π 1 )e(θ 1,1 , v 1,1 )e(θ 2,1 , v 2,1 ) e(u 2,1 , π 2 )e(θ 1,1 , v 1,2 )e(θ 2,1 , v 2,2 )e(u 2,1 , T 2 ) e((u 2,2 g 1 ), π 1 )e(θ 1,2 , v 1,1 )e(θ 2,2 , v 2,1 ) e((u 2,2 g 1 ), π 2 )e(θ 1,2 , v 1,2 )e(θ 2,2 , v 2,2 )e(u 2,2 g 1 , T 2 ) Optimizing the verification. By grouping the pairings, the number of pairings on the left-hand side member of the equation is already reduced to 4n + 2m instead of 8n + 2m. Now, by using the batch technique, i.e. multiplying each member by a random value and multiplying all the members, we obtain on the left-hand side 2,1 (u 2,2 g 1 ) r 2,1 , π 1 )e(u r 1,2

2,1 (u 2,2 g 1 ) r 2,2 , π 2 )e(θ Multiplying the three equations we get a single verification relation of the following form: e(c1,1, (v d1,2 d2,2) r 1,2 (d1,1 d2,1) r 1,1 )e(c1,2, (v d1,2 d2,2) r 2,2 (d1,1 d1,1) r 2,1 )e(c3,1, w -s 1,2 )e(c3,2, w -s 2,2 )

• e f, d s 2,1 2,1 d s 2,2 2,2 d t 2,1 1,1 d t 2,2 1,2
e(c2,1, h -t 1,2 )e(c2,2, h -t 2,2 ) = e(g, h) r 2,2 e(u1,1, π In [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], the authors evaluated that the verification of the proof in the SXDH instantiation requires the computation of 68 pairings. With our result, we prove it can be reduced to 15.

r 2, 2 T

 2 which requires m + 2n pairings and 2mn + 2m + 4n exponentiations in G 1 for the left part and 8 pairing computations and 16 exponentiations in G 1 and one exponentiation in G T for the right side of the equation. The alternative expression n j=1

s

  • φ . Taking the square of each entry we get   e(u3,1, u3,1) 2t e(u3,1, u3,2) 2t e(u3,1, u3,3g) 2t e(u3,2, u3,1) 2t e(u3,2, u3,2) 2t e(u3,2, u3,3g) 2t e(u3,3g, u3,1) 2t e(u3,3g, u3,2) 2t e(u3,3g, u3,3g) 2t

  and its private key is z ∈ G such that e(f, z) = T ) and the certificate of a group member with public key v = g x ∈ G is a pair (a, b) satisfying e(a, vh) e(f, b) = T . To sign a message m ∈ Z p , the group member first computes a weak Boneh-Boyen signature [BB08] σ = g 1/(x+m) using her private key x; then she forms Groth-Sahai commitments d v , d b and d σ to the group elements v, b and σ, resp., and makes a proof that they satisfy the following: e(a, vh) e(f, b) = T and e(σ, g m v) = e(g, g)

  33 , ψ 3 ) which can be batch-verified by checking 8 n i=1 e(

  g), d 1 := d σ and d 2 := d v and substituting in (5), we get e dσ1, (g m dv3) (r 13 +r 31 ) d 2•r 11 v1 d (r 12 +r 21 ) v2 e dσ2, (g m dv3) (r 23 +r 32 ) d (r 12 +r 21 ) v1 d 2•r 22 v2 • e dσ3, (g m dv3) 2•r 33 d (r 13 +r 31 ) v1 d (r 23 +r 32 ) v2 = = e u11, φ 2•r 11 11 φ r 12 +r 21 12 φ r 13 +r 31 13 e u13, (φ11φ21) r 13 +r 31 (φ12φ22) r 23 +r 32 (φ13φ23) 2•r 33 • e u22, φ r 12 +r 21 21 φ 2•r 22 22 φ r 23 +r 32 23 e u31, φ 2•r 11 31 φ r 12 +r 21 32 φ r 13 +r 31 33 • e u32, φ r 12 +r 21 31 φ 2•r 22 32 φ r 23 +r 32 33 e u33, φ r 13 +r 31 31 φ r 23 +r 32 32 φ 2•r 33 33 e(g, g 2r 33 ) .

φ r 12 +r 21 12 φ r 13 +r 31 13 ψ s 1 1 eT

 121 dσ1, (g m dv3) (r 13 +r 31 ) d 2•r 11 v1 d (r 12 +r 21 ) v2 • e dσ2, (g m dv3) (r 23 +r 32 ) d (r 12 +r 21 ) v1 d 2•r 22 v2 e dσ3, (g m dv3) 2•r 33 d (r 13 +r 31 ) v1 d (r 23 +r 32 ) v2 = = e u11, φ 2•r 1111 u13, (φ11φ21) r 13 +r 31 (φ12φ22) r 23 +r 32 (φ13φ23) 2•r 33 (ψ1ψ2) s 3• e u22, φ r 12 +r 21 s 3 e(g, g 2r 33 )

  e), with N = pq composite. Consider a set of m pairing-based claims, with m ∈ poly(k), written as k j i=1 e(f i j , h i j ) c i j = A j in G T , for j ∈ [1, m]. For any random vector ∆ = (δ 1 , . . . , δ m ) of -bit elements in Z n , a batch pairing-based verifier which tests the equation

  m j=2 δ j (c(j) -a(j)) is a multiple of p, in which case p different values of δ 1 = ∆ + µq, µ = 0, . . . , p -1 verify the equation.

  (g 1 u 2,2 ) r 2,2 , T 2 )C SXDH Instantiation of Belenkiy-Chase-Kohlweiss-Lysyanskaya's P-signatures t T = e(g, h) in (4), we get for the first equation:e(c 1,1 , (v d 1,2 d 2,2 ) r 1,2 (d 1,1 d 2,1 ) r 1,1 )e(c 1,2 , (v d 1,2 d 2,2 ) r 2,2 (d 1,1 d 2,1 ) r 2,1 ) , v 2,2 ) e(g r 2,2 , h)For the second and the third equation, setting and substituting in (4)A = f , d = d 2 , c = c 3 , B = w -1, Γ = 0 and t T = 1, andA = f , d = d 1 , c = c 2 , B = h -1 , Γ = 0 and t T = 1we get: e(c 3,1 , w -s 1,2 )e(c 3,2 , w -s 2,2 )e f, d , φ 2,1 )e(ψ s 1,1

Table 1 .

 1 NMVR94] Number of pairings per proof verification, where n and m stand for the number of different types of variables.

		Naive computation	Batch computation
	SXDH
	Pairing-product equation	5m + 3n + 16	m + 2n + 8
	Multi-scalar multiplication equation in G1	8m + 2n + 14	min(2n + 9, 2m + n + 7)
	Multi-scalar multiplication equation in G2	8n + 2m + 14	min(2m + 9, 2n + m + 7)
	Quadratic equation	8m + 8n + 12	2 min(m, n) + 8
	DLIN
	Pairing-product equation	12n + 27	3n + 6
	Multi-scalar multiplication equation	9n + 12m + 27	3n + 3m + 6
	Quadratic equation	18n + 24	3n + 6

  which requires 2mn + 2m + 6n exponentiations in G 1 and m + 2n pairing computations.An alternative expression of the left hand-side of the equation,

	m	e c i,1 ,	n j=1 d j,1	γ i,j	r 1,1	B i	n j=1 d j,2	γ i,j	r 1,2	•	m	e c i,2 ,	n j=1 d j,1	γ i,j	r 2,1	B i	n j=1 d j,2	γ i,j	r 2,2
	i=1														i=1
		•e u 2,1 ,		n j=1 d j,1	a j	r 1,1	n j=1 d j,2	a j	r 1,2		• e u 2,2 g 1 ,	n j=1 d j,1	a j	r 2,1	n j=1 d j,2	a j	r 2,2	,
	requires 2mn + 4m + 2n + 4 exponentiations in G 2 and 2m + 2 pairing computations.
		On the right-hand side, the same technique achieves a reduction from 14 to 7 pairings:
			e(u r 1,1
		m	e c i,1	r 1,2 c i,2	r 2,2 , B i •	n	e u a j 2,1	m i=1 c i,1	γ i,j		r 1,1	(u 2,2 g 1 ) a j m i=1 c i,2	γ i,j	r 2,1	, d j,1
		i=1							j=1
									•	n	e u a j 2,1	m i=1 c i,1	γ i,j	r 1,2
										j=1

(u 2,2 g 1 ) a j m i=1 c i,2 γ i,j r 2,2 , d j,2

  , h -t 1,2 )e(c 2,2 , h -t 2,2 )e f, d

							1,1 • ψ	s 2,1 1,2 , v 1,1 )
			•e(ψ 2,1 ψ s 1,1 2,2 , v 2,1 )e(u s 2,1 s 1,2 1,1 u s 2,2 1,2 , φ 1,2 ) e(u s 1,2 2,1 u s 2,2 2,2 , φ 2,2 )e(ψ	s 1,2 1,1 ψ 1,2 , v 1,2 ) e(ψ s 2,2 2,1 ψ s 1,2	s 2,2 2,2 , v 2,2 )
	and
			e(c 2,1 t 2,1 1,1 d t 2,2 1,2	= e(u t 1,1 1,1 u t 2,1 1,2 , ξ 1,1 ) e(u t 1,1 2,1 u t 2,1 2,2 , ξ 2,1 )
	•e(ζ	t 1,1 1,1 ζ	t 2,1 1,2 , v 1,1 ) e(ζ 2,1 ζ t 1,1 2,2 , v 2,1 ) • e(u t 2,1 t 1,2 1,1 u t 2,2 1,2 , ξ 1,2 ) e(u t 1,2 2,1 u t 2,2 2,2 , ξ 2,2 )e(ζ	t 1,2 1,1 ζ	t 2,2 1,2 , v 1,2 ) e(ζ	t 1,2 2,1 ζ	t 2,2 2,2 , v 2,2 )

The results for the (least practical) instantiation based on the subgroup decision problem are postponed to Appendix A.

A P-signature scheme is a digital signature scheme with an additional non-interactive proof of signature possession.

Note that in their DLIN instantiation, Groth and Sahai use • for the asymmetric map and • for the symmetric variant.

We use the rectifications of ιT and ι T by[START_REF] Ghadafi | Groth-sahai proofs revisited[END_REF].

Note that, for Type 2 pairings, exponentiation in G2 is more expensive than in GT (see[START_REF] Galbraith | Pairings for cryptographers[END_REF] for details).

Groth also proposes group signatures achieving CCA-anonymity[START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF], but for illustrative purposes we restrict ourselves to the basic CPA-anonymous scheme in this paper.

If we considered a single set of equations then it would be more efficient to order the right-hand side by the ψi's and save 3 pairings. We order by the uij though, since this enables us to batch with other equations containing pairings of these constants.

An extended version of their scheme was recently proposed[START_REF] Belenkiy | Compact e-cash and simulatable VRFs revisited[END_REF] but in this paper, for illustrative purposes, we restrict ourselves to the basic schemes from[START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF].

Acknowledgments

This work was supported by the French ANR-07-TCOM-013-04 PACE Project, by the European Commission through the IST Program under Contract ICT-2007-216646 ECRYPT II and by EADS.