Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Christopher Goyet
email: christopher.goyet@thalesgroup.com

Guénaël Renault
email: guenael.renault@lip6.fr

Attacking (EC)DSA Given Only an Implicit Hint

Keywords: DLP, ECDSA, Lattice attack, Oracle, Implicit information

We describe a lattice attack on DSA-like signature schemes under the assumption that implicit information on the ephemeral keys is known. Inspired by the implicit oracle of May and Ritzenhofen presented in the context of RSA (PKC2009), we assume that the ephemeral keys share a certain amount of bits without knowing the value of the shared bits. This work also extends results of Leadbitter, Page and Smart (CHES2004) which use a very similar type of partial information leakage. By eliminating the shared blocks of bits between the ephemeral keys, we provide lattices of small dimension (e.g. equal to the number of signatures) and thus obtain an efficient attack. More precisely, by using the LLL algorithm, the complexity of the attack is polynomial. We show that this method can work when ephemeral keys share certain amount of MSBs and/or LSBs, as well as contiguous blocks of shared bits in the middle. Under the Gaussian heuristic assumption, theoretical bounds on the number of shared bits in function of the number of signed messages are proven. Experimental results show that we are often able to go a few bits beyond the theoretical bound. For instance, if only 2 shared LSBs on each ephemeral keys of 200 signed messages (with no knowledge about the secret key) then the attack reveals the secret key. The success rate of this attack is about 90% when only 1 LSB is shared on each ephemeral keys associated with about 400 signed messages.

Introduction

The security of the main public-key cryptosystems is based on the difficulty of solving certain mathematical problems. In this context, the most commonly used problems come from Number Theory, most notably the integer factorization problem and the discrete logarithm on finite cyclic groups. For instance, an efficient factorization leads immediately to an attack on the RSA cryptosystem. The security of RSA is then partly based on the presumed difficulty of factoring large integers. Indeed, the most efficient published factoring algorithms have sub exponential asymptotic running times ([Pom84,Len87,LL93]) and it is not known whether efficient factorization can be done in polynomial time on a classical Turing machine. Another classical example is the discrete logarithm problem on a finite cyclic group, upon which is based the security of the ElGamal encryption system, the Diffie-Hellman key exchange and the DSA-like signature schemes. Despite the proven fact that a generic algorithm for computing discrete logarithms in any group is necessarily an exponential algorithm ([Tes01,Sho97,Sha71,Pol78,Pol00]), once again, subexponential algorithms are known to solve some instances of the discrete logarithm problem, i.e. on well-defined classes of groups. For instance, discrete logarithms can be computed in subexponential time on the multiplicative group of finite fields ( [START_REF] Adleman | A Subexponential Algorithm for Discrete Logarithms over All Finite Fields[END_REF]) or on some hyperelliptic curves ([ADH94,ADH99]). Conversely, there is no known subexponential algorithm to solve the discrete logarithm problem on the group of rational points of a well-chosen elliptic curve.

Instead of trying to solve directly a hard mathematical problem, we can rather look at which information should be added in order to solve this problem in polynomial time. With this objective in mind, Rivest and Shamir introduced in [START_REF] Rivest | Efficient factoring based on partial information[END_REF] the notion of oracle to formalize this approach and showed that a RSA modulus N = pq of bit size n (with p and q balanced prime factors of n) can be factored in polynomial time as soon as the n/3 most significant bits (MSB) from one of the factors are known. This result was next improved with the so-called Coppersmith's method based on lattice basis reduction as introduced in [START_REF] Coppersmith | Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known[END_REF], and which reduced the number of needed bits known to only one-half of the MSB of one of the factors. Beyond the theoretical interest, this additional information can be provided for instance with the help of side-channel analysis and the discovery of some leaks of secret information in some cryptographic systems, and brought to the attacker under the form of an oracle.

In this article, we focus on the Digital Signature Algorithm (DSA) [START_REF]FIPS. Digital Signature Standard (DSS)[END_REF] of which the security is based on the difficulty of computing discrete logarithms. The Elliptic Curve Digital Signature Algorithm (ECDSA) [START_REF] Johnson | The Elliptic Curve Digital Signature Algorithm (ECDSA)[END_REF] is the elliptic curve variant of DSA. The ElGamal [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] and the Schnorr [START_REF] Schnorr | Efficient Identification and Signatures for Smart Cards[END_REF] digital signature schemes are also variants of DSA but are rarely used in practice. Anyway, we note that all results presented in this article could be applied to any of these variants. Without redefining the DSA-like schemes (see section 2 for details), we only recall that each user is associated with a pair of private key/public key, such that the private key is the discrete logarithm in a given group of the public key. The user private key and a randomly generated number, called the ephemeral key, are required to compute the signature of a message. The ephemeral key must remain secret and is to be renewed for any new message to be signed.

The first proposal of using an oracle on DSA comes from Howgrave-Graham and Smart in [START_REF] Howgrave | Lattice Attacks on Digital Signature Schemes[END_REF] using the LLL lattice reduction algorithm ( [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF]) to take benefit from the knowledge of a small number of bits in many ephemeral keys. For instance, they show experimentally that if only 8 bits out of 160 bits are known from each ephemeral keys for 30 signed messages, then the secret key is known in less than 10 seconds. However, these results were only heuristics, even though confirmed by experimentation. Nguyen and Shparlinski then presented in [START_REF] Phong | The Insecurity of the Digital Signature Algorithm with Partially Known Nonces[END_REF] the first polynomial time algorithm that provably recovers the secret DSA key if about log 1/2 (q) LSB (or MSB) of each ephemeral key are known (q denoting the order of the chosen group, see section 2) for a polynomially bounded number of corresponding signed messages. They also show that the case of arbitrary consecutive bits requires much more known bits (about twice as much). Finally, in addition of proving the heuristic attack of [START_REF] Howgrave | Lattice Attacks on Digital Signature Schemes[END_REF], Nguyen and Shparlinski ([NS02]) also improved the experimental results of [START_REF] Howgrave | Lattice Attacks on Digital Signature Schemes[END_REF] by showing that only 3 known bits of each ephemeral key for 100 signed messages are enough to make the attack feasible. The previous attack is adapted to the case of ECDSA [START_REF] Phong | The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces[END_REF] and other DSA-like signature schemes like the Nyberg-Rueppel variants of DSA [START_REF] Mahassni | The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces[END_REF]. It is also necessary to mention another analysis that shows the threats associated with the use of private keys generated from an imperfect source of randomness. The attack of Bellare, Goldwasser and Micciancio [START_REF] Bellare | Pseudo-Random" Number Generation Within Cryptographic Algorithms: The DSS Case[END_REF] shows that DSA is totally insecure if private keys are produced by weak pseudo-random number generator such as the Knuth's linear congruential generator. When private keys are smaller than a certain bound, Poulakis proposed in [START_REF] Poulakis | Some lattices attacks on dsa and ecdsa[END_REF] an attack on (EC)DSA using the LLL algorithm and an algorithm to compute the integral points of a class of conics.

Note that unlike the case of RSA, where the oracle gives a way to directly compute the factors of the modulus, all these methods against the DSA-Like cryptosystems bypass the problem of computing discrete logarithm, but rather take advantage of the particular form of the modular equality defining the signature (see (1) in section 2).

At PKC 2009 [START_REF] May | Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint[END_REF], May and Ritzenhofen, in the context of factorization, highly restricted the power of the oracle. They did not assume that the oracle explicitly outputs bits but rather provides only implicit information. This unusual oracle applied against the cryptosystem RSA was formalized as follows: given an RSA modulus N 1 = p 1 q 1 as input, the oracle outputs a different RSA modulus N 2 = p 2 q 2 such that the factors of N 2 shared a certain amount of bits with the factors of the modulus N 1 . The implicit nature of the information given by the oracle is due to the fact that the value of the shared bits remains unknown as long as the modulus N 1 or N 2 are not factored. Surprisingly, May and Ritzenhofen give an efficient lattice-based algorithm that provably factors N 1 and N 2 in quadratic time provided that factors of the two moduli shared enough of their least significant bits (LSB). They also showed that this algorithm extends to an algorithm with more than one oracle query, which improves upon the required number of shared LSB. This cryptanalysis with the help of an implicit oracle was next extended to the case of shared MSB (and both LSB/MSB) in [START_REF] Faugère | Implicit Factoring with Shared Most Significant and Middle Bits[END_REF][START_REF] Sarkar | Further Results on Implicit Factoring in Polynomial Time[END_REF] and the bound on the required number of shared bits was also improved.

In the case of DSA, an attack using implicit information of a totally different kind was already proposed by Leadbitter, Page and Smart in [START_REF] Peter | Attacking DSA Under a Repeated Bits Assumption[END_REF] and made effective in [START_REF] Takashima | Practical Application of Lattice Basis Reduction Algorithm to Side-Channel Analysis on (EC)DSA[END_REF][START_REF] Takashima | Practical modifications of Leadbitter et al.'s repeated-bits side-channel analysis on (EC)DSA[END_REF]. From a theoretical point of view, this attack can also be formalized by queries to an oracle which returns a message signed with an ephemeral key of the form k = y + 2 w y + 2 2w x, i.e. such that the w first bits of k are equal to the w next bits. Experiments show that the repetition of a 4-bits window in the ephemeral keys of 20 signatures is enough to recover the secret key. This attack is motivated by side-channel analysis. According to the authors, recovering some relation amongst the bits of the secret keys (called "second order leakage") is much more probable than determining the values of such bits because of implementation protections against side-channel analysis. They also described many realistic scenarii where this type of leakage could occur.

+ c-log 2 ( n+1 n ) 2 (Theorem 1) δ ≥ 2N+(n-2) n + c-log 2 ( n n-1 ) 2 (Theorem 2) δ ≥ N+(n-1) n + c(n+1) 2n (Theorem 3a) δ ≥ N+(n-2) n-1 + cn 2(n-1) (Theorem 3b)
Table 1. Summary of our results

Our contribution is to define an attack on DSA-like schemes using implicit information, like in [START_REF] Peter | Attacking DSA Under a Repeated Bits Assumption[END_REF], but with an oracle very similar to the one introduced by May and Ritzenhofen ( [START_REF] May | Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint[END_REF]). More precisely, we assume that on input of a signed message (m 1 , s 1 ) an oracle outputs different signed message (m 2 , s 2 ) signed with the same secret key and such that the ephemeral keys k 1 and k 2 (used to signed the messages m 1 and m 2 respectively) share a certain amount δ of bits. This oracle only gives implicit information about the bits of the ephemeral keys because the value of the shared bits remains unknown as long as the ephemeral keys stay unknown (or equivalently as long as the secret key stays unknown). In other words, we only know that there are equalities between δ bits of the unknown ephemeral keys used to sign the given messages. We show that this implicit information should be extracted by constructing a lattice which contains a very short vector such that its components yield the secret key. The attack succeeds when this vector is found by the LLL lattice reduction algorithm ([LLL82]), that is when it is small enough. This happens when the ephemeral keys share enough bits δ . This method also works for an arbitrary number n of oracle's queries, each new piece of information decreasing the number of required shared bits.

As usual in lattice basis reduction problems, we have to use the Gaussian heuristic to find a condition on the number of shared bits δ in function of the number of messages n for this vector to be the shortest of the lattice. This condition can be improved by the use of a weighted Euclidean inner product instead of the canonical inner product during the reduction algorithm. A variant of this lattice is also proposed so that the complexity of the attack becomes independent of the secret key size and is polynomial time in n (assuming that the bound on δ is verified). In this case, the lattice is spanned by a set of linearly dependent vectors and the condition on δ is slightly deteriorated. A summary of our method and the proposed improvements can be found in table 1.

As an example of our results, the theorem 3 proves that under the Gaussian heuristic assumption, only 4 LSBs shared on each ephemeral keys of 100 signed messages are enough to make a never-failing attack and that with only 3 LSBs shared, the method needs about 200 signed messages. The result of experiments confirms these theoretical values with a computation time less than 5s, and they even show that the number of messages can be most of the time reduced to an amount comparable to the one which is described in [START_REF] Phong | The Insecurity of the Digital Signature Algorithm with Partially Known Nonces[END_REF] despite of the weakness of the oracle. However, these experiments also showed that the success rate of this attack is about 90% when only 1 LSB is shared on each ephemeral key of about 400 signed messages. Interestingly enough, this improves the experimental results of [START_REF] Phong | The Insecurity of the Digital Signature Algorithm with Partially Known Nonces[END_REF] where the best experiment corresponds to 3 LSB known (even though LSB are not even known in our contribution).

Throughout this paper, we use common results on euclidean lattice summarized in Appendix A. Section 2 recall the (EC)DSA signature algorithm. Section 3 provides a concrete scenario to justify the existence of this implicit information. In section 4, we present our method by beginning with the case of shared MSB and LSB (subsection 4.1). Essential improvements are proposed in subsection 4.2. In subsection 4.3, we present our method when they are many blocks of shared bits. Finally, we present the result of our experiments in section 5.

DSA-Style Signature Scheme

The Digital Signature Algorithm was adopted in 1993 by the U.S. government's National Institute of Standards and Technology (NIST) to become the Digital Signature Standard (DSS) [START_REF]FIPS. Digital Signature Standard (DSS). pub-NIST[END_REF]. It is much more used than ElGamal [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] and Schnorr [START_REF] Schnorr | Efficient Identification and Signatures for Smart Cards[END_REF] digital signature schemes which are variants of DSA. Thus, we focus on DSA although our attack is transferable to others.

The (EC)DSA algorithm ([FIP09,JMV01]) is defined over a finite abelian group G of prime order q. The group G is chosen as a subgroup of F × (resp. E(F)) for DSA (resp. ECDSA) where F is a finite field (resp. E(F) the group of rational points of an elliptic curve defined over F). For security reason, the size of q is chosen to be at least 160 bits. More precisely, the last revision of the standard ([FIP09,JMV01]) specifies that the parameter q must verify 2 N-1 < q < 2 N where N ∈ {160, 224, 256}. The private key is an integer a ∈ {1, . . . , q -1} and the public key is the group element A = g a where g is a publicly known generator of G. Let the function f : G -→ F q be defined by

f : x ∈ G ⊂ F × p -→ x mod q for DSA (x, y) ∈ G ⊂ E(Z p ) -→ x mod q for ECDSA
The signer chooses an hash function h mapping messages to G. To sign a message m, he chooses a random number k ∈ {1, . . . , q -1} called the ephemeral key and computes (here we present the computation in the case of DSA only)

r = f (g k ) and s = k -1 (h(m) + ar) mod q (1)
The signature on the message m is then the pair (r, s). The verification of the signature is performed by checking

f (g s -1 h(m) mod q A s -1 r mod q ) = f (g s -1 (h(m)+ar) mod q ) = f (g k ) = r

Possible application scenario

As stated in [START_REF] Peter | Attacking DSA Under a Repeated Bits Assumption[END_REF] in reference to side-channel analysis, "the assumption that an attacker may be able to determine a specific set of bits from the ephemeral secrets is less probable than when the original attacks were first published.

It is far more probable that second order, seemingly innocuous information can still be recovered and used by the attacker, even if a defense against the first order leakage is implemented". Indeed, there are always many situations where implicit information can be found despite the implementation of typically recommended countermeasures. In this paper, as in [START_REF] Peter | Attacking DSA Under a Repeated Bits Assumption[END_REF], the attacker is only assumed to be able to determine relations of equality between bits of the ephemeral keys. In addition to the three scenarii given as examples in [START_REF] Peter | Attacking DSA Under a Repeated Bits Assumption[END_REF] where implicit information is collected by a power analysis or a timing attack (involving a fixed table implementation of elliptic curve point multiplication, address-bit DPA and cache analysis), we suggest other scenarii which are specifically relevant to our model. Using invasive attacks, an attacker could lock some bits of the register or memory containing the ephemeral key. This kind of attack largely depends on the implementation and requires a good knowledge of the target, which presupposes at least a partial reverse engineering of the chip. Lasers are then used to cut some wires or to modify the chip (see Skorobogatov thesis [START_REF] Skorobogatov | Semi-invasive attacks -A new approach to hardware security analysis[END_REF]). More generally, a lot of fault attacks assume that some bits of the memory are flipped to zero (as in [START_REF] Naccache | Experimenting with Faults, Lattices and the DSA[END_REF]). But it seems more general to assume that the attacked bits take an indeterminate value.

In addition to weak and wrong implementations (e.g. [START_REF] Gillet | Cautionary note for protocols designers: Security proof is not enough[END_REF]), we could also think to destructive applications with a malicious manipulation of random generators for instance. This application could be possible on both embedded systems and software implementation, for instance with physical disturbances, invasive attacks or with malicious softwares. Moreover, the presence of a random number generator testing suite ([Bro11,RSN + 10]) does not seem to be an effective countermeasure (see experimental results in section 5.3).

Embedding into a Lattice Problem

In this section, we study the security of (EC)DSA given a set of messages signed with the same secret key, and such that the secret ephemeral keys share a certain amount of bits. We recall that the values of these common bits are unknown to us. Thus, the information about the unknown ephemeral keys are implicitly given by the set of signed messages. In other words, we only know that there are some relations amongst the bits of the ephemeral keys used to sign the messages. To ease the exposition of this method, the bit length of the modulus q is noted by N (i.e. we have 2 N-1 < q < 2 N ).

We will show how the secret key can be revealed by lattice basis reduction provided that there are enough messages or relations between the bits of the ephemeral keys. These constraints are estimated by relating our method to the Gaussian heuristic (see theorem 6 of Appendix A). Since all the complexities given in this paper depend on the complexity of computing a shortest vector in a given lattice, we set the following notation.

Notation 1 The time complexity of computing a shortest vector of a d-dimensional lattice L of Z n will be denoted by C (d, B), where B = log max i ( b i ). Notice that computing a shortest vector of any lattice is a NP-hard problem ( [START_REF] Ajtai | The shortest vector problem in l 2 is np-hard for randomized reductions (extended abstract)[END_REF]) called the Shortest Vector Problem (SVP).

For certain families of lattices (i.e. under certain conditions on lattices), the shortest vector can be computed with the LLL Algorithm. In this case, we have that C (d, B) = O(d 5 (d + B)B), i.e. polynomial time in d and B ([NS05], see Appendix A). In this paper, we seek to always stay in this situation.

We first present the case when most significant bits (MSB) and/or less significant bits (LSB) are shared and next the case when blocks of bits are shared.

Shared MSB and LSB

We first assume that we have n messages m i (i = 1, . . . , n) with the associated signatures (r i , s i ) such that all the corresponding ephemeral keys k i share a total of δ bits between the MSB and LSB independently of i (see Figure 1). Thus, they are of the form

k i = k + 2 t ki + 2 t k for all i = 1, . . . , n (2)
where

0 ≤ k < 2 t , 0 ≤ k < 2 N-t , δ = N -t + t and 0 ≤ ki < 2 N-δ
with k and k common for all the k i (i.e. independent of i).

k i = k ki k N -δ 0 t t N Fig. 1. Ephemeral keys
Note that all the values of k i , k, ki and k are unknown. In the n equations (1) defining the signature

         m 1 + ar 1 -s 1 k 1 ≡ 0 (mod q) m 2 + ar 2 -s 2 k 2 ≡ 0 (mod q) . . . . . . . . . . . . m n + ar n -s n k n ≡ 0 (mod q) (3)
we substitute the k i by (2) and eliminate the common variables k and k . Then we have

         (s -1 1 m 1 -s -1 2 m 2 ) + a(s -1 1 r 1 -s -1 2 r 2 ) -2 t ( k1 -k2 ) ≡ 0 (mod q) (s -1 1 m 1 -s -1 3 m 3 ) + a(s -1 1 r 1 -s -1 3 r 3 ) -2 t ( k1 -k3 ) ≡ 0 (mod q) . . . . . . . . . . . . (s -1 1 m 1 -s -1 n m n ) + a(s -1 1 r 1 -s -1 n r n ) -2 t ( k1 -kn ) ≡ 0 (mod q) (4) Let α i , β i , κ i ∈ Z be such that    α i := 2 -t (s -1 1 m 1 -s -1 i m i ) mod q β i := 2 -t (s -1 1 r 1 -s -1 i r i ) mod q κ i := k1 -ki then (4) becomes          α 2 + aβ 2 -κ 2 ≡ 0 (mod q) α 3 + aβ 3 -κ 3 ≡ 0 (mod q) . . . . . . . . . . . . α n + aβ n -κ n ≡ 0 (mod q) (5)
where a and κ i are unknown, β i and α i are known. The set of solutions

L = {(x 0 , x 1 , . . . , x n ) ∈ Z n+1 |x 0 α i + x 1 β i -x i ≡ 0 (mod q)
for all i = 2, . . . , n} forms an (n + 1)-dimensional lattice spanned by the row vectors of the following basis matrix

M =        1 0 α 2 . . . α n 0 1 β 2 . . . β n 0 0 q . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . q        (6)
Note that v 0 = (1, a, κ 2 , κ 3 , . . . , κ n ) is an element of the lattice L. Indeed by (5), there are λ 2 , . . . , λ n ∈ Z such that

(1, a, λ 2 , . . . , λ n ) • M = v 0 (7)
If we were able to find this vector v 0 in L, then we could recover the secret key a. Thus, we would like to give some conditions so that the vector v 0 be a short vector in L, and therefore may be obtained by lattice basis reduction. However, it is easy to see that the norm of v 0 is lower bounded by the secret key a, which can be an integer of roughly N bits. The second component of v 0 is then much bigger than the next ones which are (Nδ )-bits integers. Actually, v 0 has no reason to be a short vector of L while a is so high. Therefore we will first assume that the secret key a is smaller than 2 N-δ , before adapting the lattice to be able to find the secret keys up to N-bit size.

This temporary assumption makes v 0 short in the lattice L, but we are still unable to prove that it is the shortest vector of L. Therefore, the Gaussian heuristic (see Appendix A), which is usually applied in this situation, gives us a way to estimate the required number δ of shared bits in function of the number of available messages so that v 0 is likely to be the shortest vector of L.

Assumption 1 The Gaussian heuristic (theorem 6 of Appendix A) holds with the lattice L. Thus, if v 0 is shorter than

the Gaussian heuristic λ 1 (L) ≈ d 2πe Vol(L) 1 d then it is a shortest vector of L.
Experiments of the section 5 confirm this assumption which seems to be true in practice with the lattices used in our method.

Theorem 1. Let n messages m i (i = 1, . . . , n) with the associated signatures (r i , s i ) such that the ephemeral keys k i share a total of δ bits between the MSB and LSB. Under assumption 1 and, under the assumption that the secret key a is smaller than 2 N-δ , then a can be computed in time C (n + 1, 1 2 log 2 (n -1) + N) as soon as

δ ≥ 2N + (n -1) n + 1 + 1 + log 2 (πe) -log 2 ( n+1 n ) 2
Proof. First of all, we find an upper-bound for the norm of v 0 . Under our assumptions, each coefficient of v 0 is an integer of about (Nδ ) bits (except the first one which is equal to 1). Thus, we have the following inequality:

v 0 2 ≤ n ∑ i=1 2 2(N-δ ) = 2 2(N-δ )+log 2 n
On the other hand, thanks to the upper-triangular shape of the matrix M, the volume of L is easily computed as Vol(L) = q (n-1) > 2 (N-1)(n-1) . We now seek the condition on δ and n under which the norm of v 0 is smaller than the Gaussian heuristic:

2 2(N-δ )+log 2 (n) ≤ n + 1 2πe 2 2(N-1) n-1 n+1 which is equivalent to δ ≥ 2N + (n -1) n + 1 + 1 + log 2 (πe) -log 2 ( n+1 n ) 2

Proposal for improvements

Until now, we made the assumption that a ≤ 2 N-δ to simplify the presentation. Actually, this assumption is rarely verified by the secret key, so we have to adapt the previous attack to be able to find the secret key up to N-bit long. We suggest three ways, which may be concurrent to each other, to reach this goal.

Exhaustive search:

If δ is reasonably small then the method comes down to the previous one with an exhaustive search on the δ -most significant bits of a. Indeed, we have a = ã + 2 N-δ a with ã < 2 N-δ and a < 2 δ . An exhaustive search is then made on a with the previous lattice L in which we set

α i = 2 -t (s -1 1 m 1 -s -1 i m i ) + a 2 -t (s -1 1 r 1 -s -1 i r i ).
The bound given by the theorem 1 remains true with this method.

Remove the second column:

There is an other way to make the previous attack independent of the size of the secret key, but this trick needs a slight modification of the LLL Reduction Algorithm ( [START_REF] Pohst | A Modification of the LLL Reduction Algorithm[END_REF]). Let the lattice L spanned by the row vectors of the following matrix

M =        1 α 2 . . . α n 0 β 2 . . . β n 0 q . . . 0 . . . . . . . . . . . . 0 0 . . . q        , n > 2 (8)
The matrix M is the matrix M without the second column. As previously, we have that v 0 = (1, κ 2 , κ 3 , . . . , κ n ) is an element of the lattice L . Indeed, there are λ 2 , . . . , λ n ∈ Z such that

(1, a, λ 2 , . . . , λ n ) • M = v 0 (9)
However, the row vectors of this matrix M are not linearly independent. Thus, they do not form a basis of the lattice L and the original LLL algorithm can not be applied directly. In this case, we use the MLLL algorithm ( [START_REF] Pohst | A Modification of the LLL Reduction Algorithm[END_REF]) which is a variant of LLL in which the input vectors can be linearly dependent, and has the same complexity as the LLL algorithm.

Remark 1. Note that the secret key must be read in the transformation vector (1, a, λ 2 , . . . , λ n ) and not in the reduced basis. We could also have removed the first column, but experiments show that the required number of messages is greater in this case.

The lattice L used in this case is different from the lattice L of theorem 1. The bound and the volume must be updated.

Lemma 1. The volume of the lattice L defined by the matrix M given as (8) is equal to q n-2 .

Proof. The sublattice S of L spanned by the row vectors of the following matrix

     1 α 2 . . . α n 0 q . . . 0 . . . . . . . . . . . . 0 0 . . . q     
is a n-dimensional lattice. The dimension of the lattice L defined by the matrix M given as ( 8) is equal to the dimension of its sublattice S, therefore S is a full-rank sublattice of L (see [START_REF] Phong | Hermite's Constant and Lattice Algorithms[END_REF]). We consider a lattice as a group and we have the classical relation between volume and index: Vol(S) = Vol(L )[L : S]. Now, it is easy to see that Vol(S) = q n-1 and [L : S] = q, from which we get Vol(L ) = q n-2 .

The following theorem is directly derived from this lemma.

Theorem 2. Let n messages m i (i = 1, . . . , n, n > 2) with associated signatures (r i , s i ) such that the ephemeral keys k i share a total of δ bits between the MSB and LSB (see Figure 1). Under the assumption 1, the secret key a can be computed in time C (n, 1 2 log 2 (n -1) + N) as soon as

δ ≥ 2N + (n -2) n + 1 + log 2 (πe) -log 2 ( n n-1 ) 2
The required number of shared bits δ is slightly larger with the lattice L defined by the matrix M given as (8) than the one given in the theorem 1. Experiments confirm this fact but the success rate is now independent of the secret key size (see section 5).

Remark 2. As a referee pointed out to us, this result may be reworded by CVP instead of SVP. This will be detailed in an extended version of this paper.

Weighted Euclidean inner product:

In order to obtain the v 0 vector (7) (or similarly the v 0 vector (9)) within a LLL-reduced basis, we can also use a weighted Euclidean inner product, to take advantage of the knowledge of the components size of the targeted vector. For example, we can take the following inner product of two vectors

(x 0 , . . . , x n ), (y 0 , . . . , y n ) := n ∑ i=0 x i y i 2 2(N-log 2 (v 0,i ) )
during the LLL algorithm. In practice, this trick drastically reduces the required number of shared bits δ (see section 5).

Remark 3. Weights can be used without needing to change the norm. Indeed, it is equivalent to multiplying all columns of the lattice by the corresponding weight.

As previously, a bound can be obtained with Gaussian Heuristic.

Theorem 3. Let n messages m i (i = 1, . . . , n, n > 2) with associated signatures (r i , s i ) such that the ephemeral keys k i share a total of δ bits between the MSB and LSB. Under the assumption 1, the secret key a can be computed a. with the exhaustive search method in time δ C (n + 1, 1 2 log 2 (n) + δ N) as soon as

δ ≥ N + (n -1) n + (n + 1)(1 + log 2 (πe)) 2n (10)
b. with the lattice L (8) in time C (n, 1 2 log 2 (n -1) + δ N) as soon as

δ ≥ N + (n -2) n -1 + n(1 + log 2 (πe)) 2(n -1) (11)
Proof. Let an integer k ≥ Nδ . We use a weighted Euclidean inner product such that each component of the targeted vector v 0 have the same size k (i.e. the i-th weight is equal to klog 2 (v 0,i ) ).

a. With the exhaustive search method, a close approximation of the vector v 0 (7) is computed. Its norm is given by n+1) and the volume of the lattice (6) is

v 0 2 = ∑ n+1 i=1 v 2 0,i 2 2(k-log 2 (v 0,i ) ) ≤ ∑ n+1 i=1 2 2k = 2 2k+log 2 (
Vol(L) = 2 k 2 k-(N-δ ) (q2 k-(N-δ ) ) (n-1) ≥ 2 k(n+1)+n(δ -1)-N+1 .
Using the Gaussian heuristic assumption, we have 2 2k+log 2 (n+1) ≤ n+1 2πe (2 k(n+1)+n(δ -1)-N+1 ) 2 n+1 which is equivalent to (10). b. We apply the same method with the n-dimensional lattice L (8) and the seek vector v 0 (9). We obtain

v 0 2 = ∑ n i=1 v 2 0,i 2 2(k-log 2 (v 0,i ) ) ≤ ∑ n i=1 2 2k = 2 2k+log 2 (n) and Vol(L ) = 2 k (q2 k-(N-δ ) ) (n-1)
q ≥ 2 n(k-1)+δ (n-1)-N+2 . The Gaussian heuristic assumption gives 2 2k+log 2 (n) ≤ n 2πe (2 n(k-1)+δ (n-1)-N+2 )

2 n which is equivalent to (11).

Note that both results are independent of the variable k.

Blocks of shared bits

The previous attack can be generalized to the case of ephemeral keys sharing several blocks of bits. Thus, we now assume that we have n messages m i (i = 1, . . . , n) with associated signatures (r i , s i ) such that the ephemeral keys k i share a total of δ bits dispatched between l blocks of bits. We denote by δ i the number of bits of the i-th block b i at position p i (see Figure 2). For convenience we simplify the notation as follows: let t = (t 1 , . . . ,t l ) be a l-tuple of integers then we set 2 t = (2 t 1 , . . . , 2 t l ) Then the ephemeral key k i is of the form

k i = 2 p • b + 2 t • k i for all i = 1, . . . , n (12)
where b = (b 1 , . . . , b l ) is the vector of shared bits blocks, with the position vector p = (p 1 , . . . , p l ) of the l blocks, and k i = (k i,0 , . . . , k i,l ) the vector of no shared bits blocks at positions t = (t 0 , . . . ,t l ). After stating that t 0 := 0 and p l+1 := N, it follows that for all i = 1, . . . , n, and for all j = 1, . . . , l, we must have

t j = p j + δ j , δ = ∑ j δ j , 0 ≤ b j < 2 δ j and 0 ≤ k i, j < 2 (p j+1 -t j )
Note that the values of k i , k i, j and b j are all unknown. In the n signature equations (1), we substitute the k i by (12) and we eliminate the common variable b, then we have

         (s -1 1 m 1 -s -1 2 m 2 ) + a(s -1 1 r 1 -s -1 2 r 2 ) -∑ l j=0 2 t j (k 1, j -k 2, j ) ≡ 0 (mod q) (s -1 1 m 1 -s -1 3 m 3 ) + a(s -1 1 r 1 -s -1 3 r 3 ) -∑ l j=0 2 t j (k 1, j -k 3, j ) ≡ 0 (mod q) . . . . . . . . . . . . (s -1 1 m 1 -s -1 n m n ) + a(s -1 1 r 1 -s -1 n r n ) -∑ l j=0 2 t j (k 1, j -k n, j ) ≡ 0 (mod q) (13) Let α i , β i ∈ Z and κ i ,t ∈ Z l be such that        α i := (s -1 1 m 1 -s -1 i m i ) mod q β i := (s -1 1 r 1 -s -1 i r i ) mod q κ i := (k 1,1 , . . . , k 1,l ) -(k i,1 , . . . , k i,l ) t := (t 1 , . . . ,t l ) k i = k i,0 δ 1 b 1 k i,1 δ j b j k i, j δ l b l k i,l 0 p 1 t 1 p j t j p l t l N Fig. 2. Ephemeral keys then (13) becomes          α 2 + aβ 2 -2 t • κ 2 ≡ k 1,0 -k 2,0 (mod q) α 3 + aβ 3 -2 t • κ 3 ≡ k 1,0 -k 3,0 (mod q) . . . . . . . . . . . . α n + aβ n -2 t • κ n ≡ k 1,0 -k n,0 (mod q) (14)
where a and κ i are unknown, β i and α i are known. Embedding these equations into the lattice L spanned by the row vectors of the following basis matrix

M =          I l(n-1)+2 α 2 . . . α n β 2 . . . β n 2 t 1 I (n-1) . . . 2 t l I (n-1) 0 qI (n-1)          (15)
we obtain that

v 0 = (1, a, k 1,1 -k 2,1 , . . . , k 1,1 -k n,1 , . . . , k 1,l -k 2,l , . . . , k 1,l -k n,l , k 1,0 -k 2,0 , . . . , k 1,0 -k n,0 ) κ i,1 κ i, j κ i,l α i + aβ i -2 t • κ i mod q (16)
is an element of the lattice L. If we were able to find this vector v 0 in L, then we could recover the secret key a.

Example 1. For instance, if we have only one block (i.e. l = 1) of δ shared bits in the middle, then the n ephemeral keys are of the form

k i = k i,0 + 2 p 1 b 1 + 2 t 1 k i,1 for all i = 1, . . . , n where δ = δ 1 , t 1 = p 1 + δ 1 , 0 ≤ k i,0 < 2 p 1 , 0 ≤ k i,1 < 2 N-t 1 and 0 ≤ b 1 < 2 δ 1 and α i , β i , κ i ∈ Z be such that    α i := (s -1 1 m 1 -s -1 i m i ) mod q β i := (s -1 1 r 1 -s -1 i r i ) mod q κ i := k 1,1 -k i,1
In this case, (14

) becomes          α 2 + aβ 2 + 2 t 1 κ 2 ≡ k 1,0 -k 2,0 (mod q) α 3 + aβ 3 + 2 t 1 κ 3 ≡ k 1,0 -k 3,0 (mod q) . . . . . . . . . . . . α n + aβ n + 2 t 1 κ n ≡ k 1,0 -k n,0 (mod q)
and the lattice L is spanned by the row vectors of the following basis matrix

M =               1 0 0 . . . 0 α 2 . . . α n 0 1 0 . . . 0 β 2 . . . β n 0 0 1 . . . 0
0 0 0 . . . 0 0 . . . q              
The targeted element of L is the vector

v 0 = (1, a, κ 2 , . . . , κ n , k 1,0 -k 2,0 , . . . , k 1,0 -k n,0 ) = (1, a, κ 2 , . . . , κ n , λ 2 , . . . , λ n ) • M
The proposed improvements of the section 4.2 can also be (directly) applied in the case of shared bits blocks. Especially, a weighted Euclidean inner product gives rise to the following estimations of the required number of shared bits in function of the number of blocks and the number of available messages.

Theorem 4. Let n messages m i (i = 1, . . . , n, n > 2) with associated signatures (r i , s i ) such that the ephemeral keys k i share a total of δ bits dispatched between l blocks of bits. Under the assumption 1, the secret key a can be computed a. with the exhaustive search method in time δ C ((l + 1)(n -1) + 2, 1 2 log 2 (n -1)) as soon as

δ ≥ N + (n -1) n + (1 + log 2 (πe)) (l + 1)(n -1) + 2 2n (17)
b. with the lattice L obtained by removing the second column (8) in time C ((l + 1)(n -1) + 1, 1 2 log 2 (n -1)) as soon as

δ ≥ N + (n -2) n -1 + (1 + log 2 (πe)) (l + 1)(n -1) + 1 2(n -1) (18)
The proof of this theorem is almost similar as the one developed in Section 4.2 and is given in the Appendix B.

Experimental results

In order to check the validity and the quality of the bounds on δ , we implemented the methods on the computational algebra system Magma V2.17-1 ([BCP97]). All the tests have essentially validated the Gaussian Heuristic assumption (assumption 1) and the fact that the first gap of the lattices (defined as λ 2 /λ 1 , see Annex A) is high enough so that the shortest vector can be computed with the LLL algorithm. Hence they show the effectiveness of our method. In the following, the length of q is fixed to N = 160.

Shared MSB and LSB

The figure 3 is the graph of the four bounds on δ given by the theorems 1, 2 and 3 in function of the number of messages. The table 2 gives more details by listing some theoretical minimal integer values of the necessary number of LSB/MSB shared bits δ for a given number of messages.

We conducted experiments of this attack when the ephemeral keys have their δ LSB in common. For the same reason as the one explained in [START_REF] Phong | The Insecurity of the Digital Signature Algorithm with Partially Known Nonces[END_REF], the results for the case of MSB or both MSB/LSB are not as good as in the LSB case, about one more bit being required. As the secret key is 160 bits long, we used the independent key size method by removing the corresponding column of the lattice (see section 4.2.2). Additionally, we use a weighted Euclidean inner product during the LLL algorithm phase which gives better results than the canonical inner product (more precisely, we use the inner product given as an example in section 4.2.3). The experiments are then conducted under the theorem 3b conditions. Note that we consider an attack to be successful when the secret key is found, that is when the targeted vector ±v 0 (9) is a vector of the reduced basis. For each δ and each n, we generated 100 tests and store the success rate in the table 3. To compare experimental values to the theoretical bound, the success rates corresponding to the theoretical minimal value of δ for a given number of messages are written in red. First of all, the results show that we have a 100% success rate when δ is the bound (11) of theorem 3 and then we could say that they confirm that the assumptions we made are justified. Moreover, we observe that we can often go a few bits beyond the theoretical bound on δ . Then, the success rate gradually decreases to zero percent with δ .

Another interesting result is that the attack still works with only 1 or 2 shared bits (δ = 1, 2) when there are enough messages. This result is particularly surprising considering that the theoretical limit is 3 and that the success rate can be higher than 90% (not to say 99% or 100% when n > 500).

Note also that the step of lattice reduction of this attack is very fast (always less than a minute, or even less than a second up to n ≈ 70). 5. Once more, we wrote in red the success rates corresponding to the theoretical minimal value of δ for a given number of messages. Contrary to the case of shared LSB/MSB, we may have a success rate lower than 100% when δ was within the bound with the attack of blocks of shared bits (see Section 4.3). The reason is that the assumption of the theorem 4 may fail because of the occurrence of exceptionally short vectors. However, we observe that we can always go a few bits beyond the theoretical bound on δ keeping a good success rate.

We can also note that the computation time is longer than in the case LSB/MSB because of the larger dimension of lattices.

Random number generator tests

In the scenario with malicious PRNG, we verified that a defect is experimentally undetectable by conventional tests. Indeed, a 8 GByte bit sequence from the AES OFB random number generator in Dieharder ( [START_REF] Robert | DieHarder: A Random Number Test Suite[END_REF]), manipulated to contain enough implicit information, was used as input for the Dieharder test suite. More precisely, sequences of some randomly selected bits are repeated in a predictable way. For instance, a sequence of 4 bits can be repeated 100 times following a predictable pattern in a random sequence corresponding to 2 10 ephemeral keys. The pattern that describes the positions of corrupted nonces (i.e. ephemeral keys sharing some bits) can be, for example, a function of the position of the first corrupted nonce. Therefore, in this case we need an additional step containing an exhaustive search to find the first corrupted nonce (of complexity of about 2 10 with this example). All tests of the two referenced statistical test suites: Dieharder statistical test suite ( [START_REF] Robert | DieHarder: A Random Number Test Suite[END_REF]) and the NIST statistical test suite (STS) ([RSN + 10]) have shown a random behavior at a high confidence level, our manipulations being then unnoticed when the number of shared bits matches the number of corrupted nonces to have a 100% success rate (see Table 3). These experiments remind that these tests are not a proof of randomness even though they are common tools for initial validation. Finally, it has been shown that an exploitable bias is currently undetectable by conventional statistical tests.

Further developments

Throughout this work, we assumed that all ephemeral keys used in the attack shared a same block of bits. In this scenario, by the pigeonhole principle, our attack needs, in the worst case, 2 δ + 1 samples before obtaining only two signatures that have ephemeral keys with δ bits in common. However, from a practical perspective, we would like to use all the signatures generated by a signer, which is not possible for the moment. Assuming, as in [START_REF] Peter | Attacking DSA Under a Repeated Bits Assumption[END_REF], that an attacker can determine, in practice, some relation amongst the bits of the secret ephemeral keys rather than their specific values, we present below how to solve this problem by slightly adapting the lattices of our method. In this context, our attack can be naturally extended to the more general case where each ephemeral key k i (i = 1 . . . n) shares δ bits with at least one other key k j (i = j) and not necessarily with all of them. For instance, we look at shared MSB/LSB, with the same notation as in section 4.1. For two fixed positions t and t , we can take the partition P of the set of all ephemeral keys corresponding to the equivalence relation R t,t , defined such that related ephemeral keys share the first t MSB and the last t LSB (which represent a total of δ bits). In a given equivalence class [k j ], if we have #[k j ] ≥ 2 then we can apply the method of Section 4.1. For each class [k j ], we obtain a system of #[k j ] -1 modular equations as (5) with

∀k i ∈ [k j ] s.t. i = j,    α i := 2 -t (s -1
j m js -1 i m i ) mod q β i := 2 -t (s -1 j r js -1 i r i ) mod q κ i := k j -ki The set of all common solutions of the #P = # {k i , i = 1..n}/R t,t systems described as above forms a lattice similar to (6) of dimension equal to n -#P.

In the same way, other shared bits in other positions (i.e. when t and t are not fixed) can be exploited by expanding the lattice with the corresponding columns. Also the same improvement can be developped in the case of shared bits blocks in the middle. All these further developments will be detailed in an extended version of this paper. More generally, we could also imagine other forms of implicit information, i.e. an other relationship than just the equality between bits. For instance, an interesting open question is whether we can exploit inequalities or simple relationships between unknown bits. b. Same computation with the lattice L obtained by removing the second column of (15). The dimension of L is equal to (l + 1)(n -1) + 1. Then a close approximation of the norm of vector v 0 is v 0 2 ≤ 2 2k ((l + 1)(n -1) + 1)

Next, the volume of L is Vol(L ) = 2 k q n-2 (2 k-p 1 ) (n-1) l ∏ j=1 2 (k-(p j+1 -t j ))(n-1) ≥ 2 k((l+1)(n-1)+1)+(n-1)δ -N-n+2

Using the Gaussian heuristic assumption, we have

2 2k dim(L ) ≤ dim(L ) 2πe
(2 k dim(L )+(n-1)δ -N-n+2 )

2 dim(L )
which is equivalent to

δ ≥ N + (n -2) n -1 + (1 + log 2 (πe)) dim(L ) 2(n -1)

Fig. 3 .

 3 Fig. 3. Theoretical bounds of Theorems 1, 2 and 3 with N = 160

Table 2 .

 2 Theoretical minimum for δ with N = 160

	Bound on	n, number of messages
	δ of theorem	3 4 5 6 7 8 9 10 15 20 30 40 50 60 70 80 90 100 200	∞
	1	83 67 56 49 43 39 35 32 23 19 14 11 10 9 8 7 7 7 5 ≈3.05
	2	109 83 67 56 49 43 39 35 25 19 14 11 10 9 8 8 7 7 5 ≈3.05
	3a	57 44 36 30 27 24 21 20 14 12 9 8 7 6 6 6 5 5 4 ≈3.05
	3b	84 57 44 36 30 27 24 21 15 12 9 8 7 6 6 6 5 5 4 ≈3.05

  Following the bound (18) (better than the bound (17)) of theorem 4, the table 4 gives some theoretical minimal integer values of the necessary number of total shared bits δ in function of the number of blocks and the number of messages. Under theses conditions, we conducted a large number of experiments (100 tests for each δ and each n) whose results are summarized in table

					2 8 10 35 56 91 99 99
	2	0	0	0	0 0 2 6 12 24 33 42 58 63 73 80 85 100 100 100 100 100 100
	3	0	2 19 34 60 74 82 94 96 97 99 99 99 99 99 100 100 100 100 100 100 100
	4	34 76 90 99 99 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
	5	96 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
	Time (s) 0.35 0.58 0.78 0.94 1.2 1.4 1.7 1.9 2.1 2.4 2.6 2.9 3.2 3.5 3.8 4.1 4.2 6.3 8.5 15 27 44
					Table 3. Success rate of LSB attack of theorem 3b
	5.2 Blocks of shared bits

Table 5 .

 5 Success rate of theorem 4b with one block

	Number of	n, number of messages	δ	n, number of messages 13 14 15 16 17 18 19 20 30 40 50 60 70 80 90 100
	blocks l	3 4 5 6 7 8 9 10 15 20 30 40 50 ∞	4	0	0	0	0	0	0	0 0	0 0 6 13 19 28 26 49
	1	86 59 46 38 32 29 26 23 17 14 11 10 9 6	5	0	0	0	0	0	0	0 0	0 19 32 49 67 78 82 77
	2	88 61 48 40 34 31 28 26 19 16 13 12 11 8	6	0	0	0	0	0	0	0 0 13 49 78 89 90 94 100 99
	3	90 63 50 42 37 33 30 28 21 18 15 14 13 10	7	0	0	0	0	0	0	0 1 63 89 96 99 97 99 97 96
	10	105 78 64 56 51 47 44 42 36 32 30 28 27 24	8	0	0	0	0	2	1	5 20 93 99 99 100 99 98 98 98
	20	125 98 85 77 71 67 65 62 56 53 50 49 48 44	9	0	0	0	1 12 21 49 59 99 100 99 99 100 99 100 99
	30	145 119 105 97 92 88 85 83 76 73 71 69 68 65	10	0	1	1 21 60 82 95 94 100 100 100 100 99 99 100 100
		Table 4. Theoretical minimum for δ with theorem 4b	Time (s) 0.08 0.10 0.13 0.16 0.20 0.23 0.28 0.3 0.8 1.4 2.1 3.0 4.1 5 6 6.8

Acknowledgments

This work has greatly benefited from highly relevant comments of anonymous referees. The authors would like to thank them sincerely for their suggestions that improved this paper. They also thank Olivier Orcière for all his constructive comments on a preliminary version of this paper. Finally, they thank Martin Albrecht for presenting this paper at the SAC2012 conference.

This work was partly supported by the Commission of the European Communities through the ICT program under contract ICT-2007-216676 (ECRYPT-II) and by the French ANR under the Computer Algebra and Cryptography (CAC) project (ANR-09-JCJCJ-0064-01).

A Common results on lattice

In this section, we state common results on lattices that are used throughout this paper. Readers interested in getting more details and proofs can refer to [START_REF] Phong | Hermite's Constant and Lattice Algorithms[END_REF].

An integer lattice L is a discrete additive subgroup of Z n . It can be generated from a basis of d independent vectors (b 1 , . . . , b d ) of Z n by linear combinations with integer coefficients. A lattice may be described by many different bases. The dimension and the volume are independent of the choice of this basis. The volume of a lattice is easy to compute with Definition 2 if at least one explicit basis is known. But, in this article, we also need a way to compute the volume of lattices spanned by a set of linearly dependent vectors. In this case, the following results on sublattices is very useful. Definition 3. A sublattice of L is a lattice M included in L. Clearly, the sublattices of L are the subgroups of L.

Lemma 2 ([NV09]). A sublattice M of L is full-rank if and only if the group index

We also need the following results about lattice basis reduction. More particularly, we require a way to provide a precise estimation of the expected length of the shortest vector, which is called the Gaussian heuristic, and a way to get an approximation of this small vector in polynomial time, which is done by using the LLL algorithm ([LLL82]).

Definition 4. For 1 ≤ r ≤ d, let λ r (L) be the least real number such that there exists at least r linearly independent vectors of L of euclidean norm smaller or equal to λ r (L). We call λ 1 (L), . . . , λ d (L) the d minima of L and we call g(L) = λ 2 (L)/λ 1 (L) the gap of L.

Theorem 5 (LLL [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF]). Let L be a d-dimensional lattice of Z n given by a basis (b 1 , . . . , b d ). Then LLL algorithm computes a reduced basis (v 1 , . . . , v d ) that approximates the shortest vector of L within an exponential factor:

The running time of Nguyen and Stehlé's version is O(d 5 (d + log B) log B) where B = max i ( b i ), see [START_REF] Phong | Floating-Point LLL Revisited[END_REF].

The time complexity of computing a shortest vector of L (which is a NP-Hard problem [START_REF] Ajtai | The shortest vector problem in l 2 is np-hard for randomized reductions (extended abstract)[END_REF]) is denoted here by C (d, B).

Theorem 6 (Gaussian heuristic [START_REF] Ajtai | Generating random lattices according to the invariant distribution[END_REF]). Let L be a random d-dimensional lattice of Z n . Then, with overwhelming probability, all the minima of L are asymptotically close to:

Thus, it is common practice to assume that if a vector v ∈ L is shorter than the Gaussian heuristic λ 1 (L) ≈ d 2πe Vol(L) 1 d applied to the d-dimensional lattice L then it is the shortest vector of L. Moreover, when the gap of L is high this vector can be found in an LLL-reduced basis of L. For lattices proposed in this article, this essential and common assumption is confirmed by experimental results of section 5 and seems to be true in practice.

B Proof of Theorem 4

Proof. Let an integer k ≥ Nδ . We use a weighted Euclidean inner product such that each component of the seek vector v 0 have the same size k (i.e. the i-th weight is equal to klog 2 (v 0,i ) ).

a. With the exhaustive search method: first note that the dimension of the lattice L defined by (15) is dim(L) = (l + 1)(n -1) + 2 A close approximation of the norm of vector v 0 (16) is then computed:

Next, the volume of the lattice (15) is

j=1 p j+1 + ∑ l j=1 p j + ∑ l j=1 δ j ) = (n -1)(k(l + 1)p l+1 + δ ) = (n -1)(k(l + 1) -N + δ ) then Vol(L) = q n-1 2 k 2 k-(N-δ ) 2 (n-1)(k(l+1)-N+δ ) ≥ 2 k((l+1)(n-1)+2)+n(δ -1)-N+1

Using the Gaussian heuristic assumption, we have 2 2k+log 2 (dim(L)) ≤ dim(L) 2πe

(2 k dim(L)+n(δ -1)-N+1 )

which is equivalent to δ ≥ N + (n -1) n + (1 + log 2 (πe)) dim(L) 2n