Aurore Guillevic

Damien Vergnaud

Algorithms for Outsourcing Pairing Computation

We address the question of how a computationally limited device may outsource pairing computation in cryptography to another, potentially malicious, but much more computationally powerful device. We introduce two new efficient protocols for securely outsourcing pairing computations to an untrusted helper. The first generic scheme is proven computationally secure (and can be proven statistically secure at the expense of worse performance). It allows various communication-efficiency trade-offs. The second specific scheme -for optimal Ate pairing on a Barreto-Naehrig curve -is unconditionally secure, and do not rely on any hardness assumptions. Both protocols are more efficient than the actual computation of the pairing by the restricted device and in particular they are more efficient than all previous proposals.

Introduction

Pairings (or bilinear maps) were introduced in cryptography in 2000 by Joux [START_REF] Joux | A one round protocol for tripartite diffie-hellman[END_REF] and Boneh-Franklin [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF]. A pairing is a bilinear, non-degenerate and computable map e : G 1 × G 2 → G T . In practice, the first two groups G 1 and G 2 are prime-order r subgroups of the group of points E(F q ) of an elliptic curve E defined over a finite field F q . The so-called target group G T is the order r subgroup of a finite field extension F q k . Bilinear pairings proved to be an amazingly flexible and useful tool for the construction of cryptosystems with unique features (e.g. efficient identity based cryptography or short signatures). However, the pairing computation is more resource consuming compared to a scalar multiplication on the elliptic curve E(F q ).

In the last decade, several papers [START_REF] Girault | Server-aided verification: Theory and practice[END_REF][START_REF]Secure delegation of elliptic-curve pairing[END_REF][START_REF] Canard | Delegating a pairing can be both secure and efficient[END_REF] studied the question of how a computationally limited device may outsource pairing computation to another, potentially malicious, but much more computationally powerful device. In this setting, one wants to efficiently delegate the computation of a pairing e(SK 1 , SK 2 ) of two secret keys, or a pairing e(SK, PP) of a secret key and some public parameter. Obviously, one needs to ensure that this malicious device does not learn anything about what it is actually computing (secrecy) and sometimes one also needs to, when possible, detect any failures (verifiability, also called correctness).

As mentioned in [START_REF]Secure delegation of elliptic-curve pairing[END_REF][START_REF] Canard | Delegating a pairing can be both secure and efficient[END_REF], a delegation protocol that does not ensure verifiability may cause severe security problems (in particular if the pairing computation occurs in the verification algorithm of some authentication protocol). Unfortunately, the different proposals for verifiable pairing delegation are very inefficient and it is actually better in practice to directly embed the pairing computation inside the restricted device than using these solutions. The main interest is then to save of area that is required to implement a pairing in the restricted device such as smart card.

However, if verifiability is mandatory in authentication protocols, this is not necessarily the case in scenarios where the delegated pairing value is used in an encryption scheme as a session key. In this case, one can indeed use additional cryptographic techniques to ensure that the values returned by the powerful device are correct (e.g. by adding a MAC or other redundancy to the ciphertext). One can even consider settings where the powerful device actually learns the pairing value. For instance, in a pay-TV scenario, the set-up box (provided by the pay-TV company) needs to know the (onetime) session key K used to decipher the content (e.g. movie, football match) but it does not know the secret key SK securely stored in the smartcard. If the smartcard delegates the pairing computation to the set-up box there is no harm to let it know the session key K since it will learn it anyway.

In 2005, Girault and Lefranc [START_REF] Girault | Server-aided verification: Theory and practice[END_REF] introduced the first secure pairing delegation protocol through the Server-Aided Verification notion which consists in speeding up the verification step of an authentication/ signature scheme. Their pairing delegation protocol only achieves secrecy with unconditional security (and the verifiability is achieved via a different mean). Chevallier-Mames, Coron, McCullagh, Naccache and Scott introduced in 2005 the security notions for pairing delegation [START_REF] Benoit Chevallier-Mames | Secure delegation of elliptic-curve pairing[END_REF][START_REF]Secure delegation of elliptic-curve pairing[END_REF] and they provided a verifiable delegation protocol for pairing computation. Their protocols are much more resource consuming for the restricted device than directly computing the pairing.

Recently, Canard, Devigne and Sanders proposed a more efficient protocol for verifiable pairing delegation. The authors showed that their proposal is more efficient than the computation of the pairing for optimal ate pairing on a so-called KSS-18 curve [START_REF] Ezekiel | Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field[END_REF]. Unfortunately, we will show in this paper that this is not the case for state-of-the-art optimal Ate pairing on a Barreto-Naehrig curve [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF].

Contributions of the paper. We propose two new efficient protocols for secret pairing delegation. Our protocols are not verifiable but as explained above, this is not really an issue for encryption primitives where verifiability can be achieved by other means. In particular, our typical usecases are Pay-TV where a smartcard delegates a pairing computation to the set-up box and encrypted GSM communication where the sim-card delegates a pairing computation to the smartphone processor (e.g. an ARM or Intel processor with high competitive performances). In these scenarios, one can even assume that the set-up box or the smartphone actually learns the pairing value (but of course not the secret information stored by the smartcard or the sim-card). Both methods enable to delegate the computation of a pairing e(SK, PP) of a secret key SK and some public parameter PP. They achieve better efficiency than actual computation of the pairing by the restricted device and in particular they are more efficient than all previous proposals.

We first present a (generalized) knapsack-based approach which uses different endomorphisms on the groups G 1 , G 2 , G T to speed-up the method. Instead of masking the secret point SK by a scalar multiplication with a random secret exponent, it is masked by adding to it a sum of (small) multiple of random points that are also send to the powerful device. It computes several pairings of these points with the public parameter PP and the restricted device combines them to get the actual value. The method is generic and can be applied to any pairing instantiation. The method increases the communication complexity between the two devices but one can propose different communication-efficiency trade-off.

In our second approach, we present a way to delegate only the non-critical steps in the pairing algorithm, looking carefully at each instruction in Miller algorithm. The powerful device does not learn any information on the secret point SK except the actual value of the pairing e(SK, PP) (which is perfectly suitable in our usecases). The technique can be applied to any instantiation of pairings but we concentrate on the state-of-the-art optimal Ate pairing on a Barreto-Naehrig curve [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF]. We obtain a 65% improvement (for a 128-bit security level) for the restricted device compared to the computation of the pairing.

Preliminaries

Timing Estimates using the Relic Library. To illustrate the algorithms presented in this paper, we estimate the various costs of scalar multiplication, exponentiations and pairings. We choose as a practical example a Barreto-Naehrig (BN) curve [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF] at the 128-bit security level with the implementation provided in Relic library of Aranha [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF].

This library is at the state of the art for pairing computation [START_REF] Aranha | The realm of the pairings[END_REF] and is freely available for research purpose. We assume that scalar multiplications [a]P and exponentiations z a are performed with a binary signed representation of a. So it requires roughly log a doublings (resp. squarings) and log a/3 additions (resp. multiplications). A doubling on a BN curve (with a 4 = 0) costs 2M p + 5S p (multiplications and squarings in a finite field F p ) and a mixed addition costs 7M p + 4S p [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF]. We assume that M p = S p first because it is the case for Relic library and secondly to simplify (but the estimation S p = 0.9M p would also be accurate for another implementation). We obtain a total cost of ≈ 256 Dbl E(Fp) + 86 Add E(Fp) ≈ 2738M p for a scalar multiplication on G 1 , 2.4 times this cost: ≈ 6590M p for a scalar multiplication in G 2 and ≈ 256S p 12 +86M p 12 ≈ 9252M p for an exponentiation in G T . We note that checking that an element is in G T is much more expensive than performing an exponentiation in G T . Indeed G T is an orderr subgroup in a large finite field F p k . G T has particular properties permitting very fast squaring that F p k does not. We summarize these estimates in Tab. 1 (which may be of independent interest).

Optimal Ate pairing on a Barreto-Naehrig Curve A pairing is computed in two steps (see Alg. 1): a Miller function f ← f r,Q (P ) (Alg. 1, lines 1-15) followed by a final powering f p k -1 r (Alg. 1, lines 16-27) to obtain a unique value in G T , the subgroup of order r of F * p k . There are several papers on pairing computation on BN curves. We present in Alg. 1 all the steps for an optimal ate pairing computation on a BN curve. Our global estimate is 16 336 M p (multiplications in F p ) for one pairing. The Miller loop takes 8425 M p (52 %) and the exponentation 7911 M p (48 %). From Relic benchmarks on an Intel Xeon CPU E5-1603 0 at 2.8 GHz, we obtain one pairing in 3.241 ms, the Miller loop in 1.776 ms (55 %) and the exponentiation in 1.465 ms (45 %). Security Model for Pairing Delegation In this subsection, we provide an informal description of the security model for pairing delegation protocol and refer the reader to the papers [START_REF]Secure delegation of elliptic-curve pairing[END_REF][START_REF] Canard | Delegating a pairing can be both secure and efficient[END_REF] for more details. We consider only protocols for delegation of a pairing e(SK, PP) of a secret key SK and some public parameter PP. The security notions defined in [START_REF]Secure delegation of elliptic-curve pairing[END_REF][START_REF] Canard | Delegating a pairing can be both secure and efficient[END_REF] are the following:

Secrecy requires that the powerful device cannot learn any information on SK.

Algorithm 1: Optimal Ate Pairing e OptAte (P, Q) on a BN curve

Input: E(Fp) : y 2 = x 3 + b, P (xP , yP ) ∈ E(Fp)[r], Q(xQ, yQ) ∈ E (F p 2 )[r], t trace, x curve parameter Output: e OptAte (P, Q) ∈ GT ⊂ F * p 12 1 R(XR : YR : ZR) ← (xQ : yQ : 1) 2 f ← 1 3 s ← 6x + 2 4 for m ← log 2 (s) -1, . . . , 0 do 5 R ← [2]R; ← R,R(P ) 3M p 2 + 7S p 2 + 4Mp = 27Mp 6 f ← f 2 • S p 12 + 13M p 2 = 36 + 39 = 75Mp 7 if sm = 1 or sm = -1 then 8 R ← R ± Q; ← R,±Q(P ) 11M p 2 + 2S p 2 + 4Mp = 41Mp 9 f ← f • 13M p 2 = 39Mp total Miller function:log s • 102Mp + log s/3 • 80Mp Miller function (e.g. log 2 s = 64): 6528 + 1760 = 8288Mp Q1 ← πp(Q) M p 2 = 3Mp R ← R + Q1; ← R,Q 1 (P ) 3M p 2 + 7S p 2 + 4Mp = 27Mp f ← f • 13M p 2 = 39Mp Q2 ← π p 2 (Q) 2Mp R ← R -Q2; ← R,-Q 2 (P ) 3M p 2 + 7S p 2 + 4Mp = 27Mp f ← f • 13M p 2 = 39Mp total: 137Mp total Miller Loop: 137 + 8288 = 8425Mp f ← f p 6 -1 3M p 6 + 2S p 6 + 10M p 2 + 3S p 2 + 2Mp + 2Sp + Ip = 118Mp + Ip f ← f p 2 +1 10Mp + M p 12 = 64Mp if x < 0 then a ← f 6|x|-5 else (f p 6 = f -1 ) a ← (f p 6 ) 6x+5 log p 4 S Φ 6 (p 2 ) + log p 12 M p 12 = 64 • 18 + 22 • 54Mp = (1152 + 1188)Mp = 2340Mp b ← a p 5M p 2 = 15Mp b ← ab M p 12 = 54Mp Compute f p , f p 2 and f p 3 5M p 2 + 10Mp + 5M p 2 = 40Mp c ← b • (f p ) 2 • f p 2 S Φ 6 (p 2 ) + 2M p 12 = 126Mp c ← c 6x 2 +1 log p 2 S Φ 6 (p 2 ) + log p 6 M p 12 = 128 • 18 + 43 • 54Mp = 2304 + 2322 = 4626Mp f ← f p 3 • c • b • (f p • f ) 9 • a • f 4 7M p 12 + 5S Φ 6 (p 2 ) = 468Mp Exponentiation f ← f (p 6 -1)(p 2 +1)(p 4 -p 2 +1)/r : 7851Mp + Ip ≈ 7911Mp return f Pairing: 16336Mp
Verifiability requires that the restricted device, even interacting with a dishonest powerful device, will not output a wrong value for e(SK, PP).

The formal security game for secrecy is similar to the indistinguishability security notion for encryption schemes. The adversary chooses two secret points SK 0 and SK 1 and runs the delegation protocol with the restricted device for the secret point SK b for some bit b. The scheme achieves secrecy if the probability that a (polynomial-time) adversary guesses the bit b is negligibly close to 1/2. The formal security game for verifiability ensures that at the end of the delegation protocol, the restricted device obtains the actual value e(SK, PP) or knows that the powerful device cheated in the protocol.

As mentioned above, in some cases, the secrecy property is too strong if the powerful device is allowed to learn the value e(SK, PP) afterwards. Indeed this value reveals some information on SK and the complete protocol does not achieve the secrecy property. Therefore, we propose the following notion which is weaker than the secrecy notion but well-suited for our usecases of Pay-TV and encrypted GSM communication:

Weak Secrecy requires that the powerful device cannot learn any information about

SK except what can be deduced from the value e(SK, PP)

Let us assume that we use a pairing delegation protocol for the decryption in a pairingbased scheme (such as the well-known Boneh-Franklin identity-based encryption [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF]).

If the delegation protocol achieves only Weak Secrecy, a malicious powerful device can mount a lunch-time attack (or CCA1) against the encryption scheme (using the restricted device in the delegation protocol as a decryption oracle). However, since it does not learn any information about SK (except from the one-time session keys e(SK, PP i ) for several public parameters PP i 's), it is not able to decrypt any ciphertext if the restricted device is no longer active (e.g. after revocation of the decryption rights in the Pay-TV scenario).

3 Review of Previous Proposals

Girault-Lefranc Pairing Delegation Protocol

In this subsection, we present Girault-Lefranc protocol for server-aided signature verification [12, §4.1] in Alg. 2 with a performance estimation on a BN curve at a 128-bit security level (log r = log p = 256) using the Relic library described above.

Our cost estimation concludes that the delegation of e(SK, SP) with secret SK, SP costs ≈ 18640M p which is more than a pairing computation at the state of the art (we estimate this for 16336M p in Relic library).

Note that if pre-computation is possible, then the computation of [a]SK in the first step of Alg. 2 can actually be done off-line. If moreover, the point SP is public, then the complexity of the delegation protocol falls down to 9252 M p (i.e. 0.6 pairing). This basic scheme (with pre-computation) is the most efficient pairing delegation protocol (without verifiability) of a pairing e(SK, PP) of a secret key SK and some public parameter PP.

In Girault-Lefranc delegation, as f is a pairing output, we can use the optimized squaring formula of Granger and Scott [START_REF] Granger | Faster squaring in the cyclotomic subgroup of sixth degree extensions[END_REF] when computing f (ab) -1

, hence S p 12 = 18M p instead of 36M p . The computations over the group G 1 might be available on the restricted device such as a smartcard. More precisely, we need multiplication (M p ), addition -subtraction (A p ) and inversion I p in F p . Finite field operations are implemented Algorithm 2: Girault-Lefranc Secure pairing delegation [START_REF] Girault | Server-aided verification: Theory and practice[END_REF]. [a]SK on E(Fp):

≈ 256 Dbl E(Fp) + 86 Add E(Fp) ≈ 256 • (2Mp + 5Sp) + 86 • (7Mp + 4Sp) ≈ 2738Mp [b]SP on E (F p 2 ): ≈ 256Dbl E (F p 2 ) + 86 Add E (F p 2 ) ≈ 6590Mp
If SP is public we can set b = 1 2 Send I, J to the server. on a smartcard e.g. for ECDSA but the arithmetic operations are not available for the user. We can use the RSA primitives to simulate F p arithmetic. We set no padding, the exponent to 2 and the "RSA modulus" to p to get squares mod p, then simulate multiplications through 2xy = (x + y) 2 -x 2 -y 2 . Computations in the group G T are not available and must be implemented. If a BN curve [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF] is used, G T ⊂ F * p 12 hence a complicated arithmetic must be implemented.

Remark 1 (Lightening the Girault-Lefranc scheme). If the session key K can be known by the untrusted helper (i.e. if one only needs weak secrecy), we note that a variant of the protocol may be used in some cases. We propose to ask the external resource to compute e([α]SK, [α -1 ]SP) = e(SK, SP) = K with α taken at random. The output will be exactly K. This solution is not very efficient as it costs 9388/16336 = 0.6 pairing. To improve it slightly in practice, we can swap SK and PP, i.e. put SK in E (F p 2 ) and PP ∈ E(F p ). In this way, [α]SK is the costly part and can be computed offline. Note that this delegation procedure reveals some information on the secret key SK and it is necessary to reprove the security of the underlying scheme if it is used to improve its efficiency.

Chevallier-Mames et al. Pairing Delegation Protocol

Another pairing delegation protocol was introduced by Chevallier-Mames, Coron, Mc-Cullagh, Naccache and Scott in 2005 [START_REF] Benoit Chevallier-Mames | Secure delegation of elliptic-curve pairing[END_REF][START_REF]Secure delegation of elliptic-curve pairing[END_REF]. Contrary to Girault-Lefranc's protocol, the protocol proposed by Chevallier-Mames et al. achieves secrecy (unconditionnally) and verifiability. Unfortunately, the protocol is very inefficient since the overall cost for the restricted device is 3.5 times the cost for computing the pairing (3.3 if pre-computation is possible). The main advantage of the scheme is to save of area that is required to implement a pairing in the restricted device such a smart card. However, as mentioned above, even if we can use tricks, computations in the group G T are usually not available and must be implemented (i.e. complex arithmetic in G T ⊂ F * p 12 for a BN curve).

Canard-Devigne-Sanders Pairing Delegation Protocol

We present in Alg. 3 the pairing delegation protocol proposed recently by Canard, Devigne and Sanders [START_REF] Canard | Delegating a pairing can be both secure and efficient[END_REF]. The protocol is more efficient than the previous one. It also achieves secrecy (unconditionnally) and verifiability. Canard et al. actually showed that their proposal is in fact more efficient than the computation of the pairing for optimal ate pairing on a so-called KSS-18 curve [START_REF] Ezekiel | Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field[END_REF]. Unfortunately, as shown by the precise complexity of Alg. 3, this is not the case for state-of-the-art optimal Ate pairing on a BN curve [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF]. More precisely, we show that the overall cost for the restricted device is 2.8 times the cost for computing the pairing (1.6 if pre-computation is possible). [c]SK on E(Fp):

≈ 2738Mp 6 Compute J1 = [b -1 ]J0 + I1. [b -1 ]J0 on E(Fp): ≈ 2738Mp 7 Compute J2 = [a -1 ]PP + I2.
[a -1 ]PP on E(Fp): ≈ 2738Mp 8 Send J1, J2, PP to the server. 9 Ask for α1 = e(J1, J2)(e(G1, PP)e(J0, G2)) -1 , α2 = e(J0, PP) delegated:

≈ 4 • 16336Mp = 65344Mp 10 Receive α1, α2 11 Check that α2 ∈ GT : compute α r 2 4675Mp 12 if α r 2 = 1 then 13
outputs ⊥ and halt. We present in this section a new approach to perform pairing delegation (without verifiability) of a pairing e(SK, PP) of a secret key SK and some public parameter PP. The restricted device (e.g. a smartcard) generates random points and sends them to the powerful device to compute several pairings. The smartcard receives the pairings and combines some of them to get the actual value e(SK, PP). The basic idea is to mask the secret value SK by a linear combination of those random points with "small" coefficients to improve efficiency. A similar approach has been used successfully in the setting of server-aided exponentiation [START_REF] Boyko | Speeding up discrete log and factoring based schemes via precomputations[END_REF][START_REF] Phong | Distribution of modular sums and the security of the server aided exponentiation[END_REF].

14 Compute χ = χ • α (ab) -1 2 1 exp. in GT ≈ 9216Mp 15 if χ = α1 then 16 compute (c) -1 mod r Ip ≈ 60Mp

Security Analysis

Let G be a cyclic group of order p denoted additively. We consider the two following distributions:

U n = {(P 1 , P 2 , . . . , P n , Q) R ← -G n+1 } and K n,A =      (P 1 , P 2 , . . . , P n , Q), s.t. (P 1 , P 2 , . . . , P n ) R ← -G n Q ← [a 1 ]P 1 + • • • + [a n ]P n where (a 1 , . . . , a n ) R ← -[[0, A -1]] n      .
U n is the uniform distribution on G n+1 and K n,A outputs (n + 1)-tuples where the first n components are picked uniformly at random in G while the last component is a linear combination of those elements with exponents picked uniformly at random in the interval [[0, A -1]]. In a basic version of our delegation protocol, the restricted device sends the elements (P 1 , . . . , P n ) and P n+1 = (SK -Q) to the powerful device. It replies by sending back the pairings e(P i , PP) for i ∈ {1, . . . , n + 1}. The restricted device finally gets e(SK, PP) as e(P n+1 , PP) • n i=1 e(g i , PP) ai . If the two distributions U n and K n,A are indistinguishable, the protocol will readily achieve the secrecy property.

-Perfect indistinguishability. It is straightforward to see that if A = p, then the two distributions are identical (even if n = 1) and the delegation scheme as outlined above achieves unconditional secrecy. Unfortunately, as we will see in the next paragraph, the efficiency of our schemes depends crucially on the size of A and one wants to use smaller A in practice. -Statistical indistinguishability. By using classical results on the distribution of modular sums [START_REF] Phong | Distribution of modular sums and the security of the server aided exponentiation[END_REF], one can prove that if A n = Ω(p 2 ), then the two distributions U n and K n,A are statistically indistinguishable (see [START_REF] Phong | Distribution of modular sums and the security of the server aided exponentiation[END_REF][START_REF] Coron | Fast generation of pairs (k, [k]P ) for Koblitz elliptic curves[END_REF] for details). For these parameters, the delegation protocol achieves statistical (and therefore computational) secrecy. For cryptographic purposes, the order p of G needs to be of 2k-bit size to achieve a k-bit security level. Therefore, to achieve statistical indistinguishability, we need to have A n = Ω(2 4k ) and the resulting delegation protocol is not really efficient.

-Computational indistinguishability. For smaller parameters (i.e. A n = o(p 2 )), we cannot prove that the U n and K n,A are statistically indistinguishable. However, it may be possible to prove that they are computationally indistinguishable. Using a variant of Shanks "baby-step giant-step" algorithm, one can see easily that it is possible to find the scalars (a 1 , . . . , a n )

(if they exist) such that Q = [a 1 ]P 1 + • • • + [a n ]P n in O(A n/2
) group operations in G (i.e. to solve the generalized knapsack problem in G). Therefore, to achieve computational indistinguishability for a k-bit security parameter, one needs to have at least A n = Ω(2 2k ) = Ω(p).

To conclude this paragraph, we will prove that the two distributions U n and K n,A are computationally indistinguishable in the generic group model when A n = Ω(2 2k ) = Ω(p). Our delegation protocol therefore achieves secrecy in the generic group model when A n = Ω(2 2k ) = Ω(p). This model was introduced by Shoup [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] for measuring the exact difficulty of solving discrete logarithm problems. Algorithms in generic groups do not exploit any properties of the encodings of group elements. They can access group elements only via a random encoding algorithm that encodes group elements as random bit-strings.

Let A be a generic group adversary. As usual, the generic group model is implemented by choosing a random encoding σ : G -→ {0, 1} m . Instead of working directly with group elements, A takes as input their image under σ. This way, all A can test is string equality. A is also given access to an oracle computing group addition and subtraction: taking σ(R 1 ) and σ(R 2 ) and returning σ(R 1 + R 2 ), similarly for subtraction. Finally, we can assume that A submits to the oracle only encodings of elements it had previously received. This is because we can choose m large enough so that the probability of choosing a string that is also in the image of σ is negligible. Theorem 1. Let A be a generic algorithm that distinguishes the two distributions U n and K n,A that makes at most τ group oracle queries, then A's advantage in distinguishing the two distributions is upper-bounded by O(τ 2 /A n ).

To prove this theorem, we consider the following distributions in a product group

G 1 × • • • × G n
where each G i is cyclic group of prime order p (for i ∈ {1, . . . , n}).

U n = {(P 1 , P 2 , . . . , P n , Q) R ← -G 1 × G 2 × • • • × G n × (G 1 × G 2 × • • • × G n )} and K n,A =      (P 1 , P 2 , . . . , P n , Q), s.t. (P 1 , P 2 , . . . , P n ) R ← -G 1 × G 2 × • • • × G n Q ← [a 1 ]P 1 + • • • + [a n ]P n where (a 1 , . . . , a n ) R ← -[[0, A -1]] n     
It is worth mentioning that the use of these product groups in cryptography is not interesting since even if their order is p n , the complexity of discrete logarithm computation in them is not much harder than in cyclic groups of order p. We will only use them as a tool in order to prove our Theorem 1. Following Shoup's technique [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF], it is easy to prove that a generic algorithm in the product group G 1 × • • • × G n (or equivalently in Z n p ) has a negligible advantage in distinguishing the two distributions U n and K n,A if it makes a polynomial number of group oracle queries. More precisely, we can prove the following proposition: Proposition 1. Let A be a generic algorithm that distinguishes the two distributions U n and K n,A and makes at most τ group oracle queries, then A's advantage in distinguishing the two distributions is upper-bounded by O(τ 2 /A n ).

Proof. We consider an algorithm B playing the following game with A. Algorithm B chooses n + 1 bit strings σ 1 , . . . , σ n , σ n+1 uniformly in {0, 1} m . Internally, B keeps track of the encoded elements using elements in the ring

Z p [X 1 ] × • • • × Z p [X n ].
To maintain consistency with the bit strings given to A, B creates a lists L of pairs (F, σ) where F is a polynomial vector in the ring

Z p [X 1 ] × • • • × Z p [X n ]
and σ ∈ {0, 1} m is the encoding of a group element. The polynomial vector F represents the exponent of the encoded element in the group

G 1 × • • • × G n . Initially, L is set to {((1
, 0, . . . , 0), σ 1 ), ((0, 1, . . . , 0), σ 2 ), . . . , ((0, 0, . . . , 1), σ n ), ((X 1 , . . . , X n ), σ n+1 )} Algorithm B starts the game providing A with σ 1 , . . . , σ n , σ n+1 . The simulation of the group operations oracle goes as follows:

Group operation: Given two encodings σ i and σ j in L, B recovers the corresponding vectors F i and F j and computes

F i + F j (or F i -F j ) termwise. If F i + F j (or F i -F j ) is already in L, B returns to A the corresponding bit string; otherwise it returns a uniform element σ R ← -{0, 1} m and stores (F i + F j , σ) (or (F i -F j , σ)) in L.
After A queried the oracles, it outputs a bit b. At this point, B chooses a random bit b * ∈ {0, 1} and uniform values x 1 , . . . ,

x n ∈ Z p if b * = 0 or uniform values x 1 , . . . , x n ∈ [[0, A -1]] if b * = 1. The algorithm B sets X i = x i for i ∈ {1, . . . , n}.
If the simulation provided by B is consistent, it reveals nothing about b. This means that the probability of A guessing the correct value for b * is 1/2. The only way in which the simulation could be inconsistent is if, after we choose value for x 1 , . . . , x n , two different polynomial vectors in L happen to produce the same value. First, note that A is unable to cause such a collision on its own. Indeed, notice that L is initially populated with polynomials of degree at most one in each coordinate and that both the group addition and subtraction oracle do not increase the degree of the polynomial. Thus, all polynomials contained in L have degree at most one. This is enough to conclude that A cannot purposely produce a collision.

It remains to prove that the probability of a collision happening due to a unlucky choice of values is negligible. In other words, we have to bound the probability that two distinct F i , F j in L evaluate to the same value after the substitution, namely F i (x 1 , . . . , x n )-F j (x 1 , . . . , x n ) = 0. This reduces to bound the probability of hitting a zero of F i -F j . By the simulation, this happens only if F i -F j is a non-constant polynomial vector and in this case, each coordinate is a degree one polynomial in one X i 's.

Recall that the Schwartz-Zippel lemma says that, if

F is a degree d polynomial in Z p [X 1 , . . . , X n ] and S ⊆ Z p then Pr[F (x 1 , . . . , x n ) = 0] ≤ d |S|
where x 1 , . . . , x n are chosen uniformly from S. Going back to our case, we obtain by applying the Schwartz-Zippel lemma to each coordinate:

Pr[(F i -F j )(x 1 , . . . , x n ) = 0 ∈ Z n p ] ≤ 1/p n if b * = 0 1/A n if b * = 1
Therefore, the probability that the simulation provided by B is inconsistent is upperbounded by τ (τ -1)/A n .

We will now prove that, provided m is large enough, a generic algorithm is not able to decide whether it is given as inputs n generators (P 1 , . . . , P n ) in a cyclic group G of prime order p or n order-p elements

(P 1 , 1 G2 , . . . , 1 Gn ), (1 G1 , P 2 , . . . , 1 Gn ), . . . , (1 G1 , 1 G2 , . . . , P n ) in a product group G 1 × • • • × G n
where each G i is cyclic group of prime order p. Note that the groups G and G 1 × • • • × G n are not of the same order and in practice, it will probably be easy to distinguish them. We only claim that this is difficult for a generic algorithm.

Proposition 2. Let A be a generic algorithm that distinguishes these two settings and makes at most τ group oracle queries, then A's advantage in distinguishing the two distributions is upper-bounded by O(τ 2 /p).

Proof. We consider an algorithm B playing the following game with A. To maintain consistency with the bit strings given to A, B creates a lists L of pairs (F, σ) where F is a polynomial in the ring Z p [X 1 , . . . , X n ] and σ ∈ {0, 1} m is the encoding of a group element. The polynomial F represents the exponent of the encoded element in the group G. Initially, L is set to

{(X 1 , σ 1 ), (X 2 , σ 2 ), . . . , (X n , σ n )} -If b * = 1, B chooses also n bit strings σ 1 , . . . , σ n uniformly in {0, 1} m . Internally,
B keeps track of the encoded elements using elements in the ring

Z p [X 1 ] × • • • × Z p [X n ].
To maintain consistency with the bit strings given to A, B creates a lists L of pairs (F, σ) where F is a polynomial vector in the ring

Z p [X 1 ] × • • • × Z p [X n ]
and σ ∈ {0, 1} m is the encoding of a group element. The polynomial vector F represents the exponent of the encoded element in the group G 1 ו • •×G n . Initially, L is set to {((X 1 , 0, 0, . . . , 0), σ 1 ), ((0, X 2 , 0, . . . , 0), σ 2 ), . . . , ((0, 0, . . . , 0, X n ), σ n )}

In each cases, algorithm B starts the game providing A with σ 1 , . . . , σ n . The simulation of the group operations oracle goes as follows:

Group operation: Given two encodings σ i and σ j in L, B recovers the corresponding polynomials (or polynomial vectors, depending on b * ) F i and F j and computes F i +F j (or F i -F j ) termwise. If F i +F j (or F i -F j ) is already in L, B returns to A the corresponding bit string; otherwise it returns a uniform element σ R ← -{0, 1} m and stores (F i + F j , σ) (or (F i -F j , σ)) in L.

After A queried the oracles, it outputs a bit b. At this point, B chooses uniform values x 1 , . . . , x n ∈ Z p . The algorithm B sets X i = x i for i ∈ {1, . . . , n}.

If the simulation provided by B is consistent, it reveals nothing about b. This means that the probability of A guessing the correct value for b * is 1/2. The only way in which the simulation could be inconsistent is if, after we choose value for x 1 , . . . , x n , two different polynomial vectors in L happen to produce the same value. First, note that A is unable to cause such a collision on its own. Indeed, notice that L is initially populated with polynomials of degree at most one in each coordinate and that both the group addition and subtraction oracle do not increase the degree of the polynomial. Thus, all polynomials contained in L have degree at most one. This is enough to conclude that A cannot purposely produce a collision.

It remains to prove that the probability of a collision happening due to a unlucky choice of values is negligible. If b * = 1, the probability of a collision happening is equal to 0. If b * = 0, we have to bound the probability that two distinct F i , F j in L evaluate to the same value after the substitution, namely F i (x 1 , . . . , x n ) -F j (x 1 , . . . , x n ) = 0. This reduces to bound the probability of hitting a zero of F i -F j .

Applying the Schwartz-Zippel lemma, we obtain

Pr[(F i -F j )(x 1 , . . . , x n ) = 0 ∈ Z p ] ≤ 1/p
Therefore, the probability that the simulation provided by B is inconsistent is upperbounded by τ (τ -1)/p.

To prove Theorem 1, it is then enough to prove that if there exists a generic algorithm that distinguishes the two distributions U n and K n,A that makes at most τ group oracle queries with an advantage larger than Ω(τ 2 /A n ), it gives an adversary able to distinguish the cyclic group setting from the product group setting making at most τ group oracle queries and with advantage Ω(τ 2 /A n ) (due to Proposition 1) and this result contradicts Proposition 2.

Description of Our Protocol

In the previous subsection, we provided a description of a basic version of our protocol. In this subsection, we consider an improved version of it on elliptic curves equipped with efficient endomorphisms. In this improved scheme, instead of masking SK with

[a 1 ]P 1 + • • • + [a n-1 ]P n-1 with (a 1 , . . . , a n-1 ) R ← -[[0, A -1]] n-1 , we will masked it with [a 1 ]Q 1 + • • • + [a n-1 ]Q n-1 with (a 1 , . . . , a n-1 ) R ← -[[0, A -1]] n-1
where the Q i 's are images of the P i under one of the efficient endomorphisms defined on the curve. If we denote S the set of efficient endomorphisms on the curve (that can also be efficiently evaluated in the group G T ), we obtained a scheme with generic security Ω(#S n-1 • A n-1/2 ).

Setup (could be offline). In the following, the smartcard has to generate several random points on an elliptic curve E(F p ). Fouque and Tibouchi [START_REF] Fouque | Indifferentiable hashing to Barreto-Naehrig curves[END_REF] proposed an efficient method to do it on a BN curve.

1. Let I a set of small integers, I = {0, 1, 2, 3, 4, 5, . . . , 2 -1} with #I = 2 = A. 2. The smartcard generates n-1 random points P 1 , P 2 , . . . , P n-1 on the elliptic curve E(F p ). 3. The smartcard chooses an endomorphism σ i ∈ S to apply to P i and sets Q i = σ i (P i ). 4. For each point Q i , the smartcard takes at random α i ∈ I and sets

P n = SK -([α 1 ]Q 1 + [α 2 ]Q 2 + . . . + [α n-1 ]Q n-1 = SK - n-1 i=1 [α i ]Q i .
Delegation 5. The smartcard sends P 1 , P 2 , . . . , P n to the server. 6. The server computes the n pairings f i = e(Q i , PP) and sends them back to the smartcard.

Session key computation

7. The smartcard computes (f σ1 1 ) α1 • (f σ2 2 ) α2 • • • (f σn-1 n-1 ) αn-1 • f n = K.
The σ i are also almost free. Thanks to the bilinearity property,

e(SK, PP) = e(α 1 Q 1 + α 2 Q 2 . . . + α n-1 Q n-1 + P n , PP) = e(α 1 Q 1 , PP)e(α 2 Q 2 , PP) • • • e(α n-1 Q n-1 , PP)e(P n , PP)
= (e(P 1 , PP) σ1 ) α1 • • • (e(P n-1 , PP) σn-1 ) αn-1 (e(P n , PP)) with σ i a cheap endomorphism in F * p k such that e(σ i (P i ), PP) = e(P i , PP) σi .

Example on on a Barreto-Naehrig curve. For optimal Ate pairing on a BN curve with 128-bit security level (i.e. 256-bit prime number p), the endomorphism set S can be defined as {Id, -Id, φ, φ 2 , -φ, -φ 2 } where φ is computed from the complex multiplication endomorphism available on the curve. These endomorphisms are almost free on E(F p ) if D = 1 or D = 3. They cost at most one multiplication and one subtraction in F p and the resulting point Q i is still in affine coordinates [START_REF] Bos | Exponentiating in pairing groups[END_REF].

In the Setup procedure, the smartcard has to obtain P n in affine coordinates, this costs one inversion in F p plus four multiplications, resulting in an additional cost of (say) 64M p . The cost of computing P n is (n -1) • ( • 7 + /2 • 11 + 16) + 64M p . Indeed, in Jacobian coordinates, one addition on E(F p ) with one of the two points in affine coordinates costs 11M p , if none of the points are in affine coordinates, this costs 16M p , and one doubling costs 8M p . If moreover we use a BN curve (a 4 = 0), a doubling costs 7M p .

The computation cost for the powerful device is 16336(0.84(n -1) + 1) M p . Indeed, the first pairing costs ≈ 16336M p and the (n -1) other ones cost 0.84 of one The protocol only achieves weak secrecy: the helper will learn the session key K (but still not the secret key SK).

Final Powering Delegation

We can blind the output f ← u•f of the Miller function by an element u ∈ F * p k which is an r-th power (there exists a u ∈ F * p k such that u r = u), see Alg. 5. Hence u will disappear after the final powering f = u p k -1 = 1. So we can delegate the final powering thanks to the equality f (p k -1)/r = (uf ) (p k -1)/r = K the session key. The helper learns the session key K but as no additional information on f (in particular pairing inversion is not possible). For an ate pairing on a BN curve, the line is of the form = 0 + 1 ω + 3 ω 3 , with F p 12 = F p 2 [ω] = F p 2 [ω]/(ω 6 -ξ). The smartcard can delegate the computation of the three coefficients then compute the line equation evaluated at SK.

Tangent and line computation One can found Relic [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF] formulas for tangent and line computation in src/pp/relic pp dbl.c (function pp dbl k12 projc basic) and src/pp/relic pp add.c (function pp add k12 projc basic).

We recall the formula from [2, eq. ( 10)]:

2T (P ) = -2Y Z y P + 3X 2 x P ω + (3b Z 2 -Y 2 )ω 3 (1)
with ω such that F p 12 = F p 2 [ω]/(ω 6 -ξ), X, Y, Z ∈ F p 2 and x P , y P ∈ F p . The second formula is the following [2, eq. ( 13)], with L = X -x Q Z and M = Y -y Q Z:

T +Q (P ) = -Ly P -M x P ω + (M X -LY )ω 3 (2)

In both cases the coefficients of are computed from a public parameter Q = PP hence can be delegated. The smart card saves 2S p 2 + 7M p 2 = It remains for the smart card to evaluate the line at SK = P = (x P , y P ). This costs 4M p in both cases.

Efficiency improvement. To sum up, the smartcard sends the point PP to the external computer and computes the intermediate values of the Miller function on the fly, when receiving the coefficients of the intermediate values. No information on SK is provided to the external helper (except f which does not reveal more information than the session key K). For an optimal Ate pairing on a Barreto-Naehrig curve, this saves 31% of the Miller loop, then we delegate 100% of the final powering, saving at the end 65% of the pairing cost. Note that the idea can be adapted to achieve (strong) secrecy by further masking the final powering but the efficiency improvement is smaller if pre-computation is not possible. Note also that the same idea can be applied to any instantiation of pairings (but requires a specific analysis).

  Input: secret points SK ∈ G1 and SP ∈ G2 of prime order r, elliptic curve parameters Output: corresponding session key K = e(SK, SP) 1 Sample random a, b ∈ Zr and compute I = [a]SK, J = [b]SP.

3

 3 Compute (ab) -1 mod r. ≈ 60Mp 4 Receive f = e(I, J). delegated: ≈ 16336Mp 5 Compute f (ab) -1 to retrieve K = e(SK, SP). ≈ 9252Mp 6 return K. Total cost (b = 1): ≈ 9252 + 60 + 2738 ≈ 12050Mp = 0.74 pairing Total cost a, b = 1: ≈ 12050 + 6590 ≈ 18640Mp = 1.14 pairing

Algorithm 3 :3

 3 Pairing delegation with public right-side point [7, §4.1]. Input: secret point SK ∈ G1 and public point PP ∈ G2 of prime order r, G1 generator of G1, G2 of G2, elliptic curve parameters Output: Pairing value e(SK, PP) 1 Sample a random a ∈ Zr and compute I1 = [a]G1. [a]G1 on E(Fp): ≈ 2738Mp 2 Sample a random b ∈ Zr and compute I2 = [b]G2. [b]G1 on E(Fp): ≈ 2738Mp Compute χ = e(G1, G2) ab 1 exp. in GT ≈ 9216Mp 4 Compute (a) -1 mod r and (b) -1 mod r Ip + 3Mp ≈ 63Mp 5 Sample c random c ∈ Zr and compute J0 = [c]SK.

  Total cost: 46136Mp = 2.8 pairings Cost w/o pre-computation: 25905Mp = 1.6 pairings

-

  Algorithm B chooses a random bit b * and runs one of the following simulation depending on the bit b * If b * = 0, B chooses n bit strings σ 1 , . . . , σ n uniformly in {0, 1} m . Internally, B keeps track of the encoded elements using elements in the ring Z p [X 1 , . . . , X n ].

Algorithm 5 :

 5 Partial reduced Tate pairing delegationInput: Elliptic curve E(Fp) of embedding degree k and prime order r subgroup, with degree d twist available, pointsP ∈ E(Fp), Q ∈ E(F p k ) ∩ Ker(π p k/d -[p k/d ])Output: Reduced Tate pairing er(P, Q)p k -1 r 1 f = fr,P (Q) Miller function 2 Compute a random r-th power u ∈ F * p k i.e. such that ∃v ∈ F * p k , u = v r 3 f = f • u 4 Send f to the external resource 5 Receive h = (f )Tangent and line Delegation The two points P, Q play two different roles in a Tate-like pairing computation. In an ate pairing, the point P is used to evaluate the intermediate line functions (P ). The line functions are computed through a scalar multiplication [s]Q (with s a public parameter of the curve). The coefficients arising in the lines and tangent computation are re-used to update the Miller function f s,PP (SK). If Q is actually a public parameter PP, then the line computation PP can be delegated. The restricted device (such as a smartcard) will ask for the successive intermediate values then evaluate them at the secret point P = SK.

Table 1 .

 1 Estimations for common operations in algorithms, for a BN curve with log p = 256 bits and Relic[START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF] implementation (Running Relic toolkit on a Intel Xeon E5-1603 at 2.80 GHz). Norm F p 12 /Fp (z) = 1 log a S φ 12 (p) + log a /3 M p 12 36 log a Mp 2.818 ms Norm F p 12 /Fp (z), for any z Norm F p 12 /F p 6 /F p 2 /Fp (z)

	Operation	cost	total over Fp	Relic
		F p k arithmetic
			Mp 0.149 µs
	M p 2	3Mp	3Mp 0.427 µs
	S p 2	2Mp	2Mp 0.360 µs
	M p 6	6M p 2	18Mp 3.362 µs
	S p 6	2M p 2 + 3S p 2	12Mp 2.523 µs
	M p 12	3M p 6	54Mp 10.856 µs
	S p 12	2M p 6	36Mp 7.598 µs
	S φ 12 (p)	z 2 , z ∈ F p 12 , Norm(z) = 1	18Mp 4.731 µs
	z a , for any z, a	log a S p 12 + log a /3 M p 12	54 log a Mp 3.864 ms
	z a , 59 Mp	-
	z p z 1-t = z p (z p 6 check order(z) = r in F p k Norm F p 12 /Fp (z) = 1; z r = 1 ) t-1 z r , Norm F p 12 /Fp (z) = 1	4616 Mp 4675 Mp	--
		E(Fp) arithmetic
	Doubling (Dblp)	2Mp + 5Sp	7Mp 1.043 µs
	Addition (Addp)	7Mp + 4Sp	11Mp 1.639 µs
	Scalar mult. [a]P	log a Dbl + log a /3 Add	10.7 log a Mp	-
	[a1]P1 + [a2]P2	max(log a1, log a2) (Dbl +2/3 Add)	max(log a1, log a2) 14.33Mp	-
		E(F p 2 ) arithmetic
	Doubling (Dbl p 2 )	2M p 2 + 5S p 2	16Mp 3.137 µs
	Addition (Add p 2 )	7M p 2 + 4S p 2	29Mp 4.866 µs
	Scalar mult. [b]Q	log b Dbl p 2 + log b /3 Add p 2	25.7 log b Mp 2.017 ms
	[b1]Q1 + [b2]Q2	max(log b1, log b2) (Dbl p 2 +2/3 Add p 2 )	max(log b1, log b2) 35.33Mp	-
		Pairing on a BN curve with log 2 p = 256
	Dbl step + T,T (P )	3M p 2 + 7S p 2 + 4Mp	27 Mp 6.036 µs
	Add step + T,Q(P )	11M p 2 + 2S p 2 + 4Mp	41 Mp 7.593 µs
	Miller loop	see Alg. 1	8425Mp 1.776 ms
	Final powering	see Alg. 1	7911Mp 1.465 ms
	Pairing	see Alg. 1	16336Mp 3.241 ms

Table 2 .

 2 Communication/Efficiency Trade-off of our knapsack delegation protocol

	n Generic Security Computational Cost Communication
	59 5	128	8788Mp = 0.53 pairing 15360 bits
	23 10	126	8109Mp = 0.49 pairing 30720 bits
	13 15	127	7574Mp = 0.46 pairing 46080 bits
	8 20	125	6859Mp = 0.41 pairing 61440 bits
	8 20	125	6859Mp = 0.41 pairing 61440 bits
	5 25	122	6072Mp = 0.37 pairing 76800 bits
	3 30	118	5249Mp = 0.32 pairing 92160 bits
	0 51	128	3650Mp = 0.22 pairing 156672 bits

steps in the pairing algorithm, looking carefully at each instruction in Miller algorithm.

It is worth mentioning that this computational cost can be further decreased by using classical multi-exponentiation techniques (in particular for small values of n (e.g. n = 5).

Acknowledgements. The authors thank Olivier Blazy, Renaud Dubois and Fabien Laguillaumie for their fruitful comments. This work was supported in part by the French ANR-12-INSE-0014 SIMPATIC Project.

[αi]: log 2 αi(Dbl E(Fp) + 1 3 Add E(Fp) ) 10.7 Mp 7 Online:

9 Send PP and all the P1, . . . , Pn to the server. communication: log(p) • (n + 1) bits 10 Ask for all the fi = e(Pi, PP),

for n = 20 and = 8: 6859Mp = 0.4 pairing pairing (since the second argument is the fixed point PP, the tangents and lines can be computed from PP one single time for all the pairings). Finally, the smartcard computes 1 n -1 exponentiations and multiplies n elements in G T to obtain the session key K = e(SK, PP). An exponentiation costs in average squaring plus /2 multiplications in F p 12 . The n -1 exponentiations cost (n -1)(18 + 54 /3)M p . It remains to compute n -1 multiplications.

Overall, we obtain the global cost for the restricted device is: (n -1)(73M p + 46, 7 M p ) (and (n-1)(73M p +36 M p ) is pre-computation is possible). We summarize our proposition in Alg. 4. By choosing appropriate values for n and , one can achieve various communication-efficiency trade-off as shown in Tab. 2. To achieve statistical security (instead of generic computational security), one basically needs to double the value of . One can find parameters for which the delegation procedure is more efficient than the pairing computation (0.5 pairing for practical parameters).

Partial Pairing Computation Delegation

In this final section, we propose a completely different approach based on the arithmetic of the pairing computation (without verifiability) of a pairing e(SK, PP) of a secret key SK and some public parameter PP. More precisely, we delegate only the non-critical