Thierry Mefenza

Damien Vergnaud

Lattice Attacks on Pairing-Based Signatures

Keywords: Cryptanalysis, Side-channel attacks, Lattice attacks, Coppersmith's methods, Pairing-based signatures, Boneh-Boyen signatures, Gentry signatures, Modular Inversion Hidden Number Problem

Practical implementations of cryptosystems often suffer from critical information leakage through side-channels (such as their power consumption or their electromagnetic emanations). For public-key cryptography on embedded systems, the core operation is usually group exponentiation -or scalar multiplication on elliptic curves -which is a sequence of group operations derived from the private-key that may reveal secret bits to an attacker (on an unprotected implementation). We present lattice-based polynomial-time (heuristic) algorithms that recover the signer's secret in popular pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the corresponding exponents are known by the attacker. Our techniques relies upon Coppersmith method and apply to all signatures in the so-called exponent-inversion framework in the standard security model (i.e. Boneh-Boyen and Gentry signatures) as well as in the random oracle model (i.e. Sakai-Kasahara signatures).

Introduction

Pairing-based signatures. An identity-based encryption (IBE) scheme is a public key encryption scheme in which a user public key is its identity which may be an arbitrary string such as an email address, a phone number or any other identifier and the user private key is generated by a trusted authority called the privatekey generator. In their seminal paper proposing the first IBE scheme, Boneh and Franklin [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] mentioned an interesting transform from an IBE scheme to a signature scheme (whose observation was attributed to Naor). The transformation is as follows: the private-key generator public key and secret key correspond to the public key and secret key of the signature scheme and the user private key generation correspond to signatures generation. The well-known short signature scheme proposed by Boneh, Lynn and Shacham [START_REF] Boneh | Short signatures from the Weil pairing[END_REF][START_REF] Boneh | Short signatures from the Weil pairing[END_REF] can be seen as an application of Naor transformation to Boneh and Franklin IBE [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF].

Pairings (or bilinear maps) are powerful mathematical constructs which have been used since 2000 to design numerous complex cryptographic protocols. There are three known pairing-based approaches to design IBE schemes [START_REF] Boyen | A tapestry of identity-based encryption: practical frameworks compared[END_REF]: full-domainhash [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF], commutative-blinding [START_REF] Boneh | Short signatures without random oracles[END_REF] and exponent-inversion [START_REF] Boneh | Short signatures without random oracles[END_REF][START_REF] Boneh | Efficient selective-ID secure identity based encryption without random oracles[END_REF][START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF]. We focus on the latter framework which gives rise to several short signature schemes thanks to Naor transformation.

Embedded devices and side-channel attacks. The pairing-based signature schemes are very well-suited for resource-limited devices since they produce short signatures and their generation involves only one scalar multiplication on an elliptic curve. In the recent years, theoretical attacks against elliptic curves have shown little improvements whereas side-channel attacks became a major threat against elliptic curves implementations [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF][START_REF] Kocher | Differential power analysis[END_REF]. These attacks are based on information gained from the physical leakage of a cryptosystem implementation (such as timing information, power consumption or electromagnetic leaks).

For elliptic-curve cryptography, the core operation is scalar multiplication which is usually computed with the binary method: the binary representation of the (secret) exponent is scanned; for the bit-value zero, a point-doubling is computed, whereas a point-doubling and a point-addition are calculated when the bit-value is one. Distinguishing point-doubling from point-addition in power traces can thus reveal the secret exponent. Classical countermeasures to this simple power analysis consist of using regular algorithms for scalar multiplication. In the more involved differential power analysis, the idea is to guess the secret bit-by-bit, and try to confirm or infirm the guess for each bit thanks to statistical analysis of several power traces. This approach requires that the same secret is used to perform several cryptographic operations but since pairing-based signatures in the exponent-inversion framework use a different exponent for each new signature, they seem immune to differential power analysis.

In [START_REF] Chari | Template attacks[END_REF], Chari, Rao and Rohatgi introduced the so-called template attacks which aim at exploiting side-channel information when only a limited number of leakage traces is available. These attacks require that the attacker is able to perform a profiling of the side-channel leakage. Countermeasures against simple power analysis attacks might not prevent such template-based attacks since they exploit data dependent leakages and not only operation dependent leakages. For pairing-based signatures in the exponent-inversion framework, the signature generation consists of a single scalar multiplication of a fixed base point where the exponent depends algebraically on the secret key, the message and some public randomness. Since the base point is fixed, the first bits of these variable exponents that are processed during the signature computation can only lead to a small set of points and we only need to build templates for the points in this (small) set. In this paper, we show that only a small number of bits of several such exponents is sufficient to determine the secret key via lattice attacks. This approach is similar to lattice attacks [START_REF] Howgrave-Graham | Lattice attacks on digital signature schemes[END_REF][START_REF] Nguyen | The insecurity of the digital signature algorithm with partially known nonces[END_REF][START_REF] Nguyen | The insecurity of the elliptic curve digital signature algorithm with partially known nonces[END_REF] combined with template attacks [START_REF] Mulder | Using Bleichenbacher's solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA[END_REF] that were proposed against the standardized signature scheme DSA and ECDSA.

Contributions of the paper

We consider several pairing-based signature schemes in the exponent-inversion framework. In [START_REF] Sakai | ID based cryptosystems with pairing on elliptic curve[END_REF], Sakai and Kasahara presented the first such scheme (whose security was analyzed in the random oracle model by Zhang, Safavi-Naini and Susilo in [START_REF] Zhang | An efficient signature scheme from bilinear pairings and its applications[END_REF]). Boneh and Boyen [START_REF] Boneh | Efficient selective-ID secure identity based encryption without random oracles[END_REF] then presented the first pairing-based signature whose security can be proven in the standard security model. In 2006, Gentry [START_REF] Gentry | Practical identity-based encryption without random oracles[END_REF] proposed yet another scheme using the exponent-inversion paradigm, with a tighter security proof than the earlier proposals.

These schemes can be described in a general simplified form as follows. Let G and G T be two cyclic groups of the same prime order p and let g be a generator of G. We suppose that (G, G T ) are equipped with an efficiently computable bilinear map e : G×G → G T . Let H : {0, 1} * → Z q be a collision-resistant hash function. Let f, g ∈ Z p [X, Y, M, R] be two polynomials of degree at most one in X and Y . The key generation picks uniformly at random two integers (x, y) ∈ Z p as the signing secret key and outputs (g x , g y ) ∈ G 2 as the public-key. To sign a message m ∈ {0, 1} * , the signer picks uniformly at random r ∈ Z p , computes σ = g f (x,y,H(m),r)/g(x,y,H(m),r) and outputs the pair (σ, r) as the signature. The validity of a signature is checked by verifying whether the following equality holds: e(σ, g g(x,y,H(m),r) ) = e(g f (x,y,H(m),r) , g) where the elements g f (x,y,H(m),r) and g g(x,y,H(m),r) can be computed publicly from g x , g y , m and r. The three schemes use the following specific polynomials:

-Sakai-Kasahara [26]: f (X, Y, M, R) = 1, g(X, Y, M, R) = X + M -Boneh-Boyen [2]: f (X, Y, M, R) = 1, g(X, Y, M, R) = X + M + Y R -Gentry [14]: f (X, Y, M, R) = Y + R, g(X, Y, M, R) = X + M
We present lattice-based polynomial-time algorithms that recover the signer's secret (x, y) ∈ Z 2 p in these pairing-based signatures when used to sign a constant number of messages under the assumption that blocks of consecutive bits of the corresponding exponents f (x, y, H(m), r)/g(x, y, H(m), r) modulo p are known by the attacker. We consider known-message attacks and chosen-message attacks (i.e. where the attacker is allowed to choose the message m). The method of this paper is heuristic and uses Coppersmith's lattice technique. Let denote the bit-length of p and N denote the number of unknown blocks of each signing exponent. In a nutshell, we show that one can recover the secret key if the number of consecutive bits of each unknown block is smaller than the following theoretical values:

-Sakai-Kasahara: /2N 2 -Boneh-Boyen: /2N 2 -Gentry: /N provided that the number of signatures is sufficiently large (see the corresponding sections in the paper for more precise bounds). It is interesting to note, that Gentry scheme which provides the best classical security (tight security reduction in the standard security model), is the weakest against our class of attacks.

More generally, our lattice-based algorithms can be seen as methods to solve variants of the modular inversion hidden number problem which was introduced by Boneh, Halevi and Howgrave-Graham in 2001 [START_REF] Boneh | The modular inversion hidden number problem[END_REF]. This problem is to find a hidden number given several integers and partial bits of the corresponding modular inverse integers of the sums of the known integers and that unknown integer. It was used in [START_REF] Boneh | The modular inversion hidden number problem[END_REF] to built a pseudo-random number generator and a message authentication code scheme. In [START_REF] Ling | On the modular inversion hidden number problem[END_REF], the authors mentioned that it is interesting to study a general problem of recovering of an unknown rational function. One can see our results as a first step towards solving this problem.

The efficiency of our (heuristic) attacks has been validated experimentally.

Coppersmith Method

We provide a short description of the Coppersmith method [START_REF] Coppersmith | Finding a small root of a univariate modular equation[END_REF][START_REF] Coppersmith | Finding a small root of a bivariate integer equation; factoring with high bits known[END_REF] for finding small roots of a multivariate modular polynomial system of equations modulo an integer p. We refer the reader to [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants[END_REF] for details and proofs.

Problem definition. Let f 1 (y 1 , . . . , y n ), . . . , f s (y 1 , . . . , y n ) be irreducible multivariate polynomials defined over Z, having a root (x 1 , . . . , x n ) modulo a known integer p namely for i ∈ {1, . . . , s}, we have f i (x 1 , . . . , x n ) ≡ 0 mod p. Our goal is to recover the desired root (x 1 , . . . , x n ). This problem is generally intractable but becomes solvable (under some conditions) in polynomial time log(p) O (1) (for constant n and constant total degree of the input polynomials) if the root (x 1 , . . . , x n ) is upper-bounded by some values (X 1 , . . . , X n ) that depends on p and the degree of the polynomials f 1 , . . . , f s .

Polynomials collection. In a first step, one generates a larger collection P of polynomials { f1 , . . . , fr } linearly independent having (x 1 , . . . , x n ) as a root modulo p m , for some positive integer m. Usually, the technique consists in taking product of powers of the modulus p, the polynomials f i for i ∈ {1, . . . , s} and some well-chosen monomials, such as

f = p m-s j=1 k j, y α 1, 1 • • • y α n, n f k 1, 1 • • • f k s, s
for some positive integers α 1, , . . . , α n, , k 1, , k s, . These polynomials satisfy f (x 1 , . . . , x n ) ≡ 0 mod p m .

Lattice construction. In a second step, one denotes as M the set of monomials appearing in collection of polynomials P, and one writes the polynomials fi (y 1 X 1 , . . . , y n X n ) for i ∈ {1, . . . , r} as a vector b i ∈ (Z) ω , where ω = M. One then constructs a lattice L generated by the vectors b 1 , . . . , b r and computes its reduced basis using the LLL algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF].

Lemma 1. Let L be a lattice of dimension ω. In polynomial time, the LLL algorithm given as input of basis of L outputs a reduced basis of L formed by vectors v i , 1 i ω that satisfy:

v 1 v 2 . . . v 2 2 ω(ω-1) 4(ω+1-i) det(L) 1 ω+1-i .
Generating new polynomials. In a third step of the method, one combines Lemma 2 below (from [START_REF] Howgrave-Graham | Finding small roots of univariate modular equations revisited[END_REF]) and Lemma 1 to obtain n multivariate polynomials g 1 (y 1 , . . . , y n ), . . . , g n (y 1 , . . . , y n ) having (x 1 , . . . , x n ) as a root over the integers.

Lemma 2. (Howgrave-Graham) Let h(y 1 , . . . , y n ) be a polynomial over Z having at most ω monomials. Suppose that:

1. h(x 1 , . . . , x n ) = 0 mod W for some |x 1 | < X 1 , . . . , |x n | < X n and, 2. h(X 1 y 1 , . . . , X n y n ) W √ ω . Then h(x 1 , . . . , x n ) = 0 holds over the integers.
The LLL algorithm run on the lattice L to obtain n reduced vectors v i , i ∈ {1, . . . , n} that we see as some polynomials hi (y 1 X 1 , . . . , y n X n ), i ∈ {1, . . . , n}. One can see that for i ∈ {1, . . . , n}, hi (x 1 , . . . , x n ) = 0 mod p m , since hi is a linear combination of f1 , . . . , fr . Then if the following condition holds: 2 r(r-1)

4(r+1-n) det(L) 1 r+1-n < p m √ ω ,
by Lemmas 1 and 2, hi (x 1 , . . . , x n ) = 0, i ∈ {1, . . . , n} holds over the integers and we then obtain n polynomials having (x 1 , . . . , x n ) as a root over the integers.

Condition. In our attacks, the number of polynomials in the first step is equal to the number of monomials that appears in the collection, so r = ω = M.

In the analysis, we let (as usual in this setting) terms that do not depend on p contribute to an error term ε, and the simplified condition becomes:

det(L) < p m(ω+1-n) .
Under the (heuristic) assumption that all created polynomials in the third step define an algebraic variety of dimension 0, the previous system can be solved (e.g., using elimination techniques such as resultant computation or Gröbner basis) and the desired root recovered in polynomial time5 log(p) O(1) (for constant n and constant total degree of the input polynomials). In this paper, we assume that these polynomials define an algebraic variety of dimension 0 and we justify the validity of our attacks by computer experiments.

Gentry Signatures

As mentioned in the introduction, Gentry introduced in [START_REF] Gentry | Practical identity-based encryption without random oracles[END_REF] an IBE scheme without random oracles with short public parameters and tight security reduction in the standard security model. In this paragraph, we describe the signature scheme obtained by applying Naor transformation to Gentry's IBE. The resulting scheme achieves existential unforgeability under chosen-message attacks in the standard security model.

Let G and G T be two cyclic groups of the same prime order p (where p > 2 2λ for a security parameter λ) and let g be a generator of G. We suppose that (G, G T ) are equipped with an efficient computable bilinear map e : G×G → G T . Let H : {0, 1} * → Z q be a collision-resistant hash function. Gentry signature scheme is defined by the three following algorithms:

-Key generation. The user picks uniformly at random (x, y) ∈ Z 2 p , computes h 1 = g x and h 2 = g y and sets sk = (x, y) and pk

= (h 1 , h 2 ) ∈ G 2 .
-Signature generation. Given a message m ∈ {0, 1} * , the user computes its hash value H(m), and picks uniformly at random r ∈ Z p . It computes the signing exponent σ = (y + r)/(x + H(m)) mod p and the group element s = g σ . The signature is the pair (r, s) = e g, h 1 g H(m)

∈ Z p × G. -Signature verification. Given (r, s) ∈ Z p × G,

Description of the Attack

In this section, we use Coppersmith's methods to attack Gentry's signatures when the attacker learns some blocks of consecutive bits of the signing exponents.

Let n 1 be some integer. We suppose that the attacker is given (n + 2) message/signature pairs (m i , (r i , s i )) i∈{0,...,n+1} as described above (where n does not depend on the security parameter λ). To simplify the notation in the following, instead of the hash values H(m i ), we assume that the m i belongs to Z p (for i ∈ {0, . . . , n + 1}).

We assume that the attacker knows some blocks of consecutive bits of the corresponding signing exponents σ i for i ∈ {0, . . . , n+1} and its goal is to recover the secret keys x and y. From the knowledge of two different signing exponents σ i and σ j for integers i, j ∈ {0, . . . , n + 1} with i = j, the attacker can actually recover the secrets x and y. Its goal is therefore to recover the hidden bits of two σ i 's in order to obtain x and y.

We have σ i = (y + r i )/(x + m i ) mod p for i ∈ {0, . . . , n + 1} which can be rewritten as:

σ i (x + m i ) -y -r i = 0 mod p, i ∈ {0, . . . , n + 1}.
We consider a chosen-message attack where the attacker uses an arbitrary unique message m for all signatures (i.e. m i = m for all i ∈ {0, . . . , n + 1}). Eliminating x and y, in the previous equation, we obtain for a, b, i ∈ {0, . . . , n + 1} with 0 a < b < i n + 1:

(r a -r b )σ i + (r i -r a )σ b + (r b -r i )σ a = 0 mod p Putting σ i = N j=1 x i,j 2 ki,j + γ i , i ∈ {0, . . . , n + 1}
, where γ i is known to the attacker and x i,j , j ∈ {1, . . . , N } are unknown and |x i,j | < 2 µi,j for some integer µ i,j and with the choice a = 0, b = 1, we obtain a polynomial f i (z 0,1 , . . . , z 0,N , . . . , z n+1,1 , . . . , z n+1,N ) having as root X 0 = (x 0,1 , . . . , x 0,N , . . . , x n+1,1 , . . . , x n+1,N ) modulo p with:

f i = z i,N + N -1 j=1 a i,j z i,j + N j=1 b i,j z 1,j + N j=1 c i,j z 0,j + γ i (r 0 -r 1 ) + d i mod p for i ∈ {2, . . . , n + 1}, where        a i,j = 2 ki,j /2 k i,N mod p b i,j = 2 k1,j (r i -r 0 )/((r 0 -r 1 )2 k i,N ) mod p c i,j = 2 k0,j (r 1 -r i )/((r 0 -r 1 )2 k i,N ) mod p d i = (γ i (r 0 -r 1 ) + γ 1 (r i -r 0 ) + γ 0 (r 1 -r i ))/((r 0 -r 1 )2 k i,N
) mod p for i ∈ {2, . . . , n + 1} and j ∈ {1, . . . , N }.

We consider the following collection of polynomials (parameterized by some integer m ∈ N that does not depend on the security parameter λ): P m = f i0,1,...,in+1,1,i0,2,...,in+1,2,...,i 0,N ,...,i n+1,N , for all vectors of integers (i 0,1 , . . . , i n+1,1 , i 0,2 , . . . , i n+1,2 , . . . , i 0,N , . . . , i n+1,N ) verifying

0 i 0,1 + • • • + i n+1,1 + • • • + i 0,N , . . . , i n+1,N m
and where the polynomial f i0,1,...,in+1,1,i0,2,...,in+1,2,...,i 0,N ,...,i n+1,N is defined by:

z i0,1 0,1 . . . z in+1,1 n+1,1 . . . z i 0,N -1 0,N -1 . . . z i n+1,N -1 n+1,N -1 z i 0,N 0,N z i 1,N 1,N f i 2,N 2 . . . f i n+1,N n+1 p m-(i 2,N +•••+i n+1,N ) .
One can see that f i0,1,...,in+1,1,i0,2,...,in+1,2,...,i 0,N ,...,i n+1,N (X 0 ) = 0 mod p m for all such vector of integers.

If we use for instance the lexicographical monomial order (with z i,j < z i ,j if (j < j or (j = j and i < i )) on the set of monomials, we can define an order over the set of polynomials as: f i0,1,...,in+1,1,i0,2,...,in+1,2,...,i 0,N ,...,i n+1,N < f i 0,1 ,...,i n+1,1 ,i 0,2 ,...,i n+1,2 ,...,i 0,N ,...

,i n+1,N if z i0,1 0,1 . . . z in+1,1 n+1,1 . . . z i 0,N 0,N . . . z i n+1,N n+1,N < z i 0,1 0,1 . . . z i n+1,1 n+1,1 . . . z i 0,N 0,N . . . z i n+1,N n+1,N .
Using this order, we can write P m = { fi , i ∈ {1, . . . , ω}}, with f1 < f2 < • • • < fω where ω is the number of polynomials. Putting U = 2 maxi,j µi,j , we define the lattice L generated by b 1 , . . . , b ω , where for i ∈ {1, . . . , ω}, b i is the coefficient vector of the polynomial fi (U z 0,1 , . . . , U z n+1,1 , . . . , U z 0,N , . . . , U z n+1,N ).

One can easily verify that the basis matrix is lower triangular and the diagonal elements are U a p m-(i 2,N +•••+i n+1,N ) , where the integer a is equal to

i 0,1 + • • • + i n+1,1 + i 0,N + • • • + i n+1,N .
The number of variables is N (n + 2) and the success condition of Coppersmith's method is det(L) < p m(ω-N (n+2)) , where ω = i∈I 1 is the dimension of the lattice with

I = {i = (i 0,1 , . . . , i 0,N , . . . , i n+1,N )|0 i 0,1 + • • • + i n+1,N m}. We have det(L) = U η p mω p -µ with µ = i∈I i 2,N + • • • + i n+1,N and η = i∈I i 0,1 + • • • + i n+1,N .
If m is large, we can neglect the N (n + 2) term in Coppersmith success condition and the asymptotic condition becomes:

U η < p µ .
Using analytic combinatorics methods (see for instance [START_REF] Benhamouda | Easing Coppersmith methods using analytic combinatorics: Applications to public-key cryptography with weak pseudorandomness[END_REF] and the references therein), one can verify that when m tends to ∞, we have η = N (n+2)β(m, N, n) and µ = nβ(m, N, n), with

β(m, N, n) = m N (n+2)+1 (N (n + 2) + 1)! + o(m N (n+2)+1 ).
Therefore, the attacker can recover x and y as long as the sizes of each unknown block in the signatures σ i for i ∈ {0, . . . , n + 1} satisfies:

U < p n (n+2)N → n→∞ p 1 N .
We can thus heuristically recover (using large 6 constant parameters n and m) the secret key (x, y) if the number of consecutive bits of each unknown block is smaller than log 2 (p) /N .

Experimental Results

We have implemented the attack in Sage 7.6 on a MacBook Air laptop computer (2,2 GHz Intel Core i7, 4 Gb RAM 1600 MHz DDR3, Mac OSX 10.10.5). Table 1 lists the theoretical bound δ theo = n (n+2)N and an experimental bound δ exp for a 512-bit prime p (corresponding to a 256-bit security level) with (n + 2) signatures (for n ∈ {1, 3, 5}) and a few number of unknown blocks (N 2). We consider the family of polynomials P m with m = 4 and m = 2. We ran 2 7 N n δ theo δexp dimension m LLL time(s) Gröbner basis time(s) [START_REF] Benhamouda | Easing Coppersmith methods using analytic combinatorics: Applications to public-key cryptography with weak pseudorandomness[END_REF] experiments for all parameters and Table 1 gives the average running time (in seconds) of the LLL algorithm and the Gröbner basis computation.

We denote α the maximum number of least significant bits that the attacker knows in each signature σ j , for all j = 0 (for instance α = 0 means that it does not know any least significant bits of the signatures σ j , for all j ∈ {1, . . . , n+1}).

If we know at least δ exp log 2 (p) +α least significant bits of the signature σ 0 then the Gröbner basis always gives us a system of dimension 0 and we are able to find the N unknown block of sizes p δexp in each signature σ i for i ∈ {0, . . . , n + 1}. Otherwise, Gröbner basis computations gives us a system of dimension 1 and we are a priori unable to find the unknown blocks (though it is possible in some cases to obtain additional information). This system of dimension 1 occurs because the constructed system admits a large number of "small" solutions. We give an example of this in Appendix A. However, If the condition mentioned above is satisfied, we obtain for N = 1 and n + 2 = 3, the success rates given in Table 2 (over 250 attacks performed for each parameter pair (m, δ exp )). 4 Lattice Attack on Boneh-Boyen Signatures

m = 2 m = 3 m = 4 δexp = 0.

Boneh-Boyen Signatures

Two years before the proposal of Gentry's IBE, Boneh and Boyen proposed two IBE schemes in [START_REF] Boneh | Efficient selective-ID secure identity based encryption without random oracles[END_REF] and described one signature scheme obtained using the Naor transformation in [START_REF] Boneh | Short signatures without random oracles[END_REF]. Their scheme has comparable efficiency properties and also achieves existential unforgeability under chosen-message attacks in the standard security model. With the same notation as above, Boneh-Boyen signature scheme is defined by the three following algorithms:

-Key generation. The user picks uniformly at random (x, y) ∈ Z 2 p , computes h 1 = g x and h 2 = g y and sets sk = (x, y) and pk = (h 1 , h 2 ) ∈ G 2 . -Signature generation. Given a message m ∈ {0, 1} * , the user computes its hash value H(m), and picks uniformly at random r ∈ Z p . It computes the signing exponent s = 1/(x + H(m) + yr) mod p and the group element σ = g s . The signature is the pair (r, σ) ∈ Z p × G. -Signature verification. Given (r, σ) ∈ Z p × G, a verifier accepts it as a signature on m ∈ {0, 1} * if and only if the following equality holds:

e(σ, h 1 • g H(m) • h r 2 )
? = e (g, g)

Description of the Attack

In this section, we use the Coppersmith's methods to attack Boneh-Boyen's signature. Let n 1 be some integer. We suppose that the attacker is given (n + 2) message/signature pairs (m i , (r i , s i )) i∈{0,...,n+1} as described above (where n does not depend on the security parameter λ). As above, to simplify the notation, we replace H(m i ) by m i ∈ Z p (for i ∈ {0, . . . , n + 1}). We assume that the attacker knows some blocks of consecutive bits of the corresponding signing exponents σ i = 1/(x + m + yr i ) mod p, for i ∈ {0, . . . , n}, where p, r i and m i are known to the attacker and x and y are kept secret. As for Gentry signatures, from the knowledge of two different signing exponents, the attacker can actually recover the secrets x and y and its goal is to recover the hidden bits of two σ i 's in order to recover x and y.

We have σ i = 1/(x + m i + yr i ) mod p for i ∈ {0, . . . , n + 1} and we have:

x + m i + yr i - 1 σ i = 0 mod p, i ∈ {0, . . . , n + 1}.
Eliminating x and y and assuming again that the attacker chooses a unique message m (namely m i = m, for all i ∈ {0, . . . , n + 1}), we obtain, for a, b, i ∈ {0, . . . , n + 1} with 0 a < b < i n + 1:

(r b -r i )σ i σ b + (r i -r a )σ i σ a + (r a -r b )σ a σ b = 0 mod p.
Putting σ i = N j=1 x i,j 2 ki,j + γ i , i ∈ {0, . . . , n + 1}, where γ i is known to the attacker and x i,j , j ∈ {1, . . . , N } are unknown with |x i,j | < 2 µi,j for some integer µ i,j and a = 0, we obtain a polynomial f 0,b,i (z 0,1 , . . . , z 0,N , . . . , z n+1,1 , . . . , z n+1,N ) having as "small" root X 0 = (x 0,1 , . . . , x 0,N , . . . , x n+1,1 , . . . , x n+1,N ) modulo p, where :

f 0,b,i = N j=1 N k=1 α b,i,j,k z i,j z b,k + N j=1 N k=1 α 0,i,j,k z i,j z 0,k + N j=1 N k=1 α 0,b,j,k z b,j z 0,k + N j=1 α 0,b,i,j z i,j + N j=1 β 0,b,i,j z b,j + N j=1
γ 0,b,i,j z 0,j + δ 0,b,i mod p for b, i ∈ {1, . . . , n + 1}, b < i and with known coefficients , where α b,i,N,N = 1. The set of monomials appearing in the polynomials f 0,b,i is:

M = 1, z a,j z b,k , z i,j : i ∈ {0, . . . , n + 1} a, b ∈ {0, . . . , n + 1}; a < b j, k ∈ {0, . . . , N } .
We consider the following set of polynomials:

P = {p m, m ∈ M 1 } ∪ {f 0,b,i : b, i ∈ {1, . . . , n + 1}; b < i} ,
where

M 1 = M \ M 2 with M 2 = {z b,N z i,N : b, i ∈ {1, . . . , n + 1}; b < i}.
One can see that for any polynomial f ∈ P, f (X 0 ) = 0 mod p. We can define an order on the set of monomials such that all the monomials in M 1 are smaller than any monomial in M 2 and for z b,N z i,N , z b ,

N z i ,N ∈ M 2 , z b,N z i,N < z b ,N z i ,N if (b < b or (b = b and i < i )).
Using that order, we can order the set of polynomials from the smallest element to the greatest as follows: P = {p m1 , . . . , p mω1 , f 0,1,2 , . . . , f 0,1,n+1 , f 0,2,3 , . . . , f 0,2,n+1 , . . . , f 0,n,n+1 } = { f1 , . . . , fω } where m1 < • • • < mω1 , ω 1 is the cardinality of M 1 and ω is the cardinality of M.

Putting U = 2 maxi,j µi,j , we define the lattice L generated by b 1 , . . . , b ω , where for each i ∈ {1, . . . , ω}, b i is the coefficient vector of the polynomial fi (U z 0,1 , . . . , U z 0,N , . . . , U z n+1,1 , . . . , U z n+1,N ).

One can verify that the basis matrix is lower triangular. The number of variables is N (n + 2) and the success condition for the Coppersmith's method is:

det(L) < p ω-N (n+2)+1 , with ω = M = N 2 (n + 1)(n + 2) 2 + (n + 2)N + 1. We have det(L) = U 2N 2 (n+1)(n+2) 2 +(n+2)N p ω-n(n+1)
2 and the success condition becomes:

U < p n(n+1) 2 -N (n+2)+1 2N 2 (n+1)(n+2) 2 +(n+2)N .
If n is large and since N is small, we can neglect -N (n + 2) + 1 which contribute to a small error term. So the attacker can recover x and y as long as the sizes of each unknown block in the signatures σ i , i ∈ {0, . . . , n + 1} satisfies:

U < p n(n+1) 2N 2 (n+1)(n+2)+2(n+2)N → n→∞ p 1 2N 2 .
We can thus heuristically recover the secret key if the number of consecutive bits of each unknown block is smaller than log 2 (p) /(2N 2 ). We ran 2 7 experiments for all parameters and in all cases (for the bound δ exp ), the assumption that the created polynomials define an algebraic variety of dimension 0 was verified. The constructed system was solved using Gröbner basis and the desired root recovered. Table 3 gives the average running time (in seconds) of the LLL algorithm and the Gröbner basis computation (using the same configuration as above).

Experimental results

5 Lattice Attack on Sakai-Kasahara Signatures

Sakai-Kasahara Signatures

In [START_REF] Sakai | ID based cryptosystems with pairing on elliptic curve[END_REF], Sakai and Kasahara presented the first pairing-based signature scheme in the exponent-inversion framework. Their scheme is very close to Boneh-Boyen signature schemes but produces shorter signatures (at the cost of relying on the random oracle heuristic [START_REF] Zhang | An efficient signature scheme from bilinear pairings and its applications[END_REF]).

With the same notation as above, Sakai-Kasahara signature scheme is defined by the three following algorithms:

-Key generation. The user picks uniformly at random x ∈ Z p , computes h = g x and sets sk = x and pk = h ∈ G. -Signature generation. Given a message m ∈ {0, 1} * , the user computes its hash value H(m). It computes the signing exponent s = 1/(x+H(m)) mod p and the group element σ = g s . The signature is the group element σ ∈ G. -Signature verification. Given σ ∈ G, a verifier accepts it as a signature on m ∈ {0, 1} * if and only if the following equality holds:

e(σ, h • g H(m) ) ? = e (g, g)
We present in the following an attack on this scheme when the attacker learns some blocks of consecutive bits of the signing exponents. This computational problem is related to the Modular Inversion Hidden Number Problem which was introduced in 2001 by Boneh, Halevi and Howgrave-Graham [START_REF] Boneh | The modular inversion hidden number problem[END_REF]. In this problem, the attacker does not know exactly one block of least significant bits of the signing exponents σ i while our attack considers the setting where the attacker does not know N 1 different blocks in each σ i (for any N ).

Description of the Attack

In this section, we use the Coppersmith's methods to attack Sakai-Kasahara signatures. Let n 1 be some integer. We suppose that the attacker is given (n + 1) message/signature pairs (m i , s i ) i∈{0,...,n+1} as described above (where n does not depend on the security parameter λ). Again, to simplify the notation, we replace H(m i ) by m i ∈ Z p (for i ∈ {0, . . . , n + 1}). We assume that the attacker knows some blocks of consecutive bits of the corresponding signing exponents σ i = 1/(x + m i ) mod p for i ∈ {0, . . . , n} and its goal is to recover x. One can see that from the knowledge of a value σ i , the attacker can actually recover the hidden number x and it is thus sufficient to recover the hidden bits of a single σ i 's in order to recover x.

We have σ i = 1/(x + m i ) mod p for i ∈ {0, . . . , n} which can be rewritten as:

x + m i -1 σ i = 0 mod p, i ∈ {0, . . . , n}.

Eliminating x, we obtain:

(m i -m a )σ i σ a + σ i -σ a = 0 mod p a, i ∈ {0, . . . , n}, 0 a < i n.
Putting, for i ∈ {0, . . . , n + 1}, σ i = N j=1 x i,j 2 ki,j + γ i , where γ i is known to the attacker and x i,j for j ∈ {1, . . . , N } are unknown with |x i,j | < 2 µi,j for some integer µ i,j , we obtain a polynomial f a,i (z 0,1 , . . . , z 0,N , . . . , z n,1 , . . . , z n,N ) having as root X 0 = (x 0,1 , . . . , x 0,N , . . . , x n,1 , . . . , x n,N ) modulo p with:

f a,i = N j=1 N k=1 α a,i,j,k z i,j z a,k + N j=1 β a,i,j z i,j + N j=1
γ a,i,j x a,j + δ a,i mod p for a, i ∈ {0, . . . , n}, a < i and with known coefficients, where α a,i,N,N = 1. The set of monomials appearing in the polynomials f a,i is: M = {1, z a,j z b,k , z i,j : i ∈ {0, . . . , n}; a, b ∈ {0, . . . , n}; a < b; j, k ∈ {1, . . . , N }} .

We consider the following set of polynomials:

P = {p m, m ∈ M 1 } ∪ {f a,i : a, i ∈ {0, . . . , n}; a < i} ,
where M 1 = M \ M 2 with M 2 = {z a,N z i,N : a, i ∈ {0, . . . , n}; a < i}. One can see that for any polynomial f ∈ P, f (X 0 ) = 0 mod p. We can define an order on the set of monomials such that all the monomials in M 1 are smaller than any monomial in M 2 and for z a,N z i,N , z a ,N z i ,N ∈ M 2 , z a,N z i,N < z a ,N z i ,N if (a < a or (a = a and i < i )).

Using that order, we can order the set of polynomials from the smallest element to the greatest as follows: P = {p m1 , . . . , p mω1 , f 0,1 , . . . , f 0,n , f 1,2 , . . . , f 1,n , . . . , f n-1,n } = { f1 , . . . , fω } where m1 < • • • < mω1 , ω 1 is the cardinality of M 1 and ω is the cardinality of M. Putting U = 2 maxi,j µi,j , we define the lattice L generated by b 1 , . . . , b ω , where b i is the coefficient vector of fi (U z 0,1 , . . . , U z 0,N , . . . , U z n,1 , . . . , U z n,N ) for i ∈ {1, . . . , ω},. One can easily verify that the basis matrix is lower triangular. The number of variables is N (n + 1) and the success condition for the Coppersmith's method is: det(L) < p ω-N (n+1)+1 ,

with ω = M = N 2 n(n+1) 2 +(n+1)N +1 and det(L) = U 2N 2 n(n+1) 2 +(n+1)N p ω-n(n+1)

2

. The success condition then becomes:

U < p n(n+1) 2 -N (n+1)+1 2N 2 n(n+1) 2 +(n+1)N .
If n is large and since N is small, we can neglect -N (n+1)+1 which contributes to a small error. The attacker can recover x and y as long as the sizes of each unknown block in the signatures σ i , i ∈ {0, . . . , n} satisfies:

U < p n(n+1) 2N 2 n(n+1))+2(n+1)N → n→∞ p 1 2N 2 .
We can heuristically recover the secret key of Sakai-Kasahara signatures if the number of consecutive bits of each unknown block is smaller than log 2 (p) /(2N 2 ). We ran 2 7 experiments for all parameters . As in the attack on Boneh-Boyen signatures, the assumption that the created polynomials define an algebraic variety of dimension 0 was verified (in all cases for the bound δ exp ) and the constructed system was solved using Gröbner basis and the desired root recovered. Table 4 gives the average running time (in seconds) of the LLL algorithm and the Gröbner basis computation (using the same configuration as above).

Experimental results

Conclusion and Open Questions

We presented lattice-based polynomial-time algorithms that recover the signer's secret in popular pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the corresponding exponents are known by the attacker. This partial information can be obtained in practice easily through side-channels (such as the power consumption or the electromagnetic emanations of the device generating the signature).

In order to prevent the leakage of partial information on the exponent, it is customary to use a probabilistic algorithm to encode the sensitive values such that the cryptographic operations only occur on randomized data. In [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF], Coron proposed notably to randomize the exponent and the projective coordinates of the base point. It is an interesting question to extend our attacks in such setting (as it was done recently for ECDSA in [START_REF] Goudarzi | Lattice attacks against elliptic-curve signatures with blinded scalar multiplication[END_REF]). It is also interesting to study the security against side-channel attacks of the pairing-based signatures whose design does not rely on the exponent inversion framework (i.e. based on the full domain hash framework and the commutative blinding framework).

Our attacks are heuristic and it would be very interesting to provide proven versions of them (as it was done in [START_REF] Nguyen | The insecurity of the digital signature algorithm with partially known nonces[END_REF][START_REF] Nguyen | The insecurity of the elliptic curve digital signature algorithm with partially known nonces[END_REF] for ECDSA signatures). It is also interesting to study further the attack against Gentry signatures when the unknown blocks of consecutive bits overlap. Finally, it would be nice to improve our attacks on Boneh-Boyen and Sakai-Kasahara signatures.

A Concrete Attack Examples against Gentry signatures

In this section, we present two attack examples on Gentry signatures for a 256-bit prime p with 3 signatures (r 0 , σ 0 ), (r 1 , σ 1 ) and (r 2 , σ 2 ) and one T -bit unknown block in each signature, with T = 0.3 log 2 (p) .

We recall that for i ∈ {0, 1, 2}, σ i = g si where s i = (y + r i )/(x + m) mod p, x and y are the secret keys and p, m and r i , i ∈ {0, 1, 2} are public information. In this example, we took the following random values:

-p = 9b814891e89496e776bfeeebcac5c74130862914fe2b928d40c3a88323dcbaaf -m = 440f4a9df2936c4aad3856ed0ea5cf3d131ef658fc36c2fa56763373288d5519 -x = 57a7b0913f5202e31555ec9538ff90f38a5e6c53b359edfe1106c8ee9518029a -y = 259b67be7de53e0546860379bc31ab9bb30caf68c314a956a1719e18d4a24ae2 -r 0 = 75c471becf6a9d86aa5480985a95702617892ba84b7662d6bdf3a3c1931abf3b -r 1 = 675e28ffbf96b29365ebda463c3a0a4290a284f9fed9ddd0ccdada587c1f0152 -r 2 = 7961b0df3f0a286547f25da59a7c2a7c28764f4335a0aa2cd5a72ba2393a6cd3 -s 0 = 45f185a8ce35c2b95b3e1aef9fc516ec9e840c9a5b6b36c70532b10145790401 -s 1 = 8f63fe87fd0d67f6594ff44ba86a2755b2b6ad6a0b7ab4aafecae41fca50c713 -s 2 = 57de02b444bb7716c021d21162c3727ba904ae6e4d44aca2ad9f4406669e8744
and T = 0.3 log 2 (p) = 76.

In the first case, we suppose that we do not know any least significant bits of each signature and show that we are unable to find the unknown blocks since the Gröbner basis gives us a system of dimension 1.

In the second case, we suppose that we know T + 2 least significant bits of σ 0 but do not know any least significant bits of s 1 , and s 2 . We also suppose that we do not know T intermediate bits of s 0 and we show that in this case we are able to find the unknown blocks since the Gröbner basis gives us a system of dimension 0.

First case

-We can write the signatures as:

s 0 = 2 T • 45f185a8ce35c2b95b3e1aef9fc516ec9e840c9a5b6b3 + z 0 , s 1 = 2 T • 8f63fe87fd0d67f6594ff44ba86a2755b2b6ad6a0b7ab + z 1 , s 2 = 2 T • 57de02b444bb7716c021d21162c3727ba904ae6e4d44a + z 2 ,
where the T -bit numbers z 0 , z 1 and z 2 are the unknown blocks.

-We get the polynomial f (y 0 , y 1 , y 2 ) defined by: y 2 + 86acc2de9d15dab4df6a8114243623f246376c1103c29ee97a0dd7490f87eb33 y 1 + 14d485b34b7ebc3297556dd7a68fa34eea4ebd03fa68f3a3c6b5d13a1454cf7b y 0 + 11f10fbe97565b062acfb71c6d98f596de6c1e236edaa9168d891d78d66e8c4a having as root (z 0 , z 1 , z 2 ) modulo p.

-Constructing the lattice with m = 4, after the LLL reduction and the Gröbner basis computation, we obtain the system of polynomials f 1 (y 0 , y 1 , y 2 ) = y 2 -y 0 -5dba86c930521258343 f 2 (y 0 , y 1 , y 2 ) = y 1 -y 0 + 21c0667cce17b283cee having indeed (z 0 , z 1 , z 2 ) as root over the integers. However, the dimension of the system is 1 and then we are a priori unable to find the unknown blocks.

Second case -We can write the signatures as:

s 0 = 36c70532b10145790401 + 2 79 • z 0 + 2 79+T • 8be30b519c6b8572b67c35df3 s 1 = 2 T • 8f63fe87fd0d67f6594ff44ba86a2755b2b6ad6a0b7ab + z 1 s 2 = 2 T • 57de02b444bb7716c021d21162c3727ba904ae6e4d44a + z 2
where the T -bit numbers z 0 , z 1 and z 2 are the unknown blocks. -If one proceeds like in the attack, we obtain the polynomial f (y 0 , y 1 , y 2 ) defined by y2 + 86acc2de9d15dab4df6a8114243623f246376c1103c29ee97a0dd7490f87eb33 y1

+ 78836c7dbcc6bee53ea07b359a07fa111e09607336b452976acd0f0ec2a0c985 y0 + 77b82eec348f27f19cb7a6c1cc895cf7261093b80d067ea4eb7b8da90e1ae306
having as root (z 0 , z 1 , z 2 ) modulo p. -Constructing the lattice with m = 4, after the LLL reduction and the Gröbner basis computation, one obtains the system of polynomials    f 1 (y 0 , y 1 , y 2 ) = y 2 -ca2ad9f4406669e8744 f 2 (y 0 , y 1 , y 2 ) = y 1 -4aafecae41fca50c713 f 3 (y 0 , y 1 , y 2 ) = y 0 -f8a2dd93d081934b6d6 having (z 0 , z 1 , z 2 ) as root over the integers. The dimension of the system is 0 and one finds readily the unknown blocks.

Table 1 .

 1 Lattice Attack on Gentry signatures. Average running time (in seconds) of the LLL algorithm and the Gröbner basis computation.

	1 0.333 0.32	35	4	3.804	4.603
	1 3 0.6 0.49	21	2	0.250	0.699
	1 5 0.714 0.49	36	2	0.871	38.374
	2 1 0.166 0.16	28	2	1.438	0.650
	2 5 0.33 0.29	91	2	191.906	556.715

Table 2 .

 2 Lattice Attack on Gentry signatures. Success rates (over 250 attacks performed for each parameter pair (m, δexp)).

	3225	100	100	100
	δexp = 0.3250 98.4	98.4	99.2
	δexp = 0.3275 90.4	92.8	94.4
	δexp = 0.3300 66.0	65.2	72.8
	δexp = 0.3325 10.0	15.2	17.2
	δexp = 0.3350	0	0	0

Table 3

 3 lists the theoretical bound δ theo = 2N 2 (n+1)(n+2)+2(n+2)N and an experimental bound δ exp for a 512-bit prime p with (n + 2) signatures for a few values of n ∈ {4, 6, 10} and one or two unknown blocks per signatures.

	n(n+1)

Table 3 .

 3 Lattice Attack on Boneh-Boyen signatures. Average running time (in seconds) of the LLL algorithm and the Gröbner basis computation.

Table 4

 4 gives the theoretical bound δ theo =

	n(n+1) 2N 2 n(n+1))+2(n+1)N and an experi-

Table 4 .

 4 Lattice Attack on Sakai-Kasahara signatures. Average running time (in seconds) of the LLL algorithm and the Gröbner basis computation.

It is well known that the computational complexity of Gröbner basis algorithm may be exponential or even doubly exponential. In our setting, the number of variables and the total total degree of the input polynomials are fixed and the theoretical complexity is polynomial in the field size (and thus in the security parameter).

In order to reach this asymptotic bound, the constructed matrix is of huge dimension and the resulting polynomial system has a very large number of variables and the computation which is theoretically polynomial-time becomes in practice prohibitive.