Dahmun Goudarzi
email: dahmun.goudarzi@cryptoexperts.commatthieu.rivain@cryptoexperts.com

Matthieu Rivain

Damien Vergnaud
email: damien.vergnaud@ens.fr

Lattice Attacks against Elliptic-Curve Signatures with Blinded Scalar Multiplication

Elliptic curve cryptography is today the prevailing approach to get efficient public-key cryptosystems and digital signatures. Most of elliptic curve signature schemes use a nonce in the computation of each signature and the knowledge of this nonce is sufficient to fully recover the secret key of the scheme. Even a few bits of the nonce over several signatures allow a complete break of the scheme by lattice-based attacks. Several works have investigated how to efficiently apply such attacks when partial information on the nonce can be recovered through side-channel attacks. However, these attacks usually target unprotected implementation and/or make ideal assumptions on the recovered information, and it is not clear how they would perform in a scenario where common countermeasures are included and where only noisy information leaks via side channels. In this paper, we close this gap by applying such attack techniques against elliptic-curve signature implementations based on a blinded scalar multiplication. Specifically, we extend the famous Howgrave-Graham and Smart lattice attack when the nonces are blinded by the addition of a random multiple of the elliptic-curve group order or by a random Euclidean splitting. We then assume that noisy information on the blinded nonce can be obtained through a template attack targeting the underlying scalar multiplication and we show how to characterize the obtained likelihood scores under a realistic leakage assumption. To deal with this scenario, we introduce a filtering method which given a set of signatures and associated likelihood scores maximizes the success probability of the lattice attack. Our approach is backed up with attack simulation results for several signal-to-noise ratio of the exploited leakage.

Introduction

In 1985, Koblitz [Kob87] and Miller [START_REF] Miller | Use of elliptic curves in cryptography[END_REF] independently proposed to use the algebraic structure of elliptic curves in public-key cryptography. Elliptic curve cryptography requires smaller keys and it achieves faster computation and memory, energy and bandwidth savings. It is therefore well suited for embedded devices. There exists several digital signature schemes based on the discrete logarithm problem in the group of points of an elliptic curve (e.g. [START_REF]A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF][START_REF] Schnorr | Efficient signature generation by smart cards[END_REF][START_REF]FIPS PUB 186-2: Digital Signature Standard (DSS)[END_REF]). These schemes use a nonce k for each signed message and compute [k]P for some public point P on the elliptic curve. It is well known that the knowledge of partial information on the nonces used for the generation of several signatures may lead to a total break of the scheme [START_REF] Howgrave-Graham | Lattice attacks on digital signature schemes[END_REF][START_REF] Bleichenbacher | On the generation of one-time keys in dl signature schemes[END_REF].

Side-channel attacks are a major threat against implementations of cryptographic algorithms [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 consists in analyzing the physical leakage of a cryptographic hardware device, such as its power consumption or its electromagnetic emanations. Elliptic curves implementations have been subject to various side-channel attacks. In order to prevent the leakage of partial information on the nonce k from the run of the algorithm that computes scalar multiplication [k]P , many countermeasures have been proposed. To thwart simple side-channel analysis, it is customary to ensure a constant (or secret-independent) operation flow (see for instance [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF][START_REF] Joye | The Montgomery powering ladder[END_REF][START_REF] Izu | Improved elliptic curve multiplication methods resistant against side channel attacks[END_REF]). To prevent more complex attacks it is necessary 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 scalar k and the projective coordinates of the point P . These countermeasures are nowadays widely used and it is not very realistic to assume that a specific set of bits from the nonces could be recovered in clear by a side-channel attacker.

Related works. Two famous attacks have been designed against elliptic-curve signature schemes that exploit partial information on the nonces of several signatures: the Bleichenbacher's attack [START_REF] Bleichenbacher | On the generation of one-time keys in dl signature schemes[END_REF] and the Howgrave-Graham and Smart's attack [START_REF] Howgrave-Graham | Lattice attacks on digital signature schemes[END_REF]. Nguyen and Shparlinski [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] proposed a proven variant of Howgrave-Graham and Smart's attack when a single block of consecutive bits is unknown to the adversary. Very few results on the security of elliptic-curve signatures with noisy partial information on the nonces are known. In [START_REF] Leadbitter | Attacking DSA under a repeated bits assumption[END_REF], Leadbitter, Page and Smart considered adversaries that can determine some relation amongst the bits of the secret nonces rather than their specific values (but this relation is known with certainty). This work was recently extended by Faugère, Goyet and Renault in [START_REF] Faugère | Attacking (EC)DSA given only an implicit hint[END_REF]. In [START_REF] Bauer | Practical key recovery for discrete-logarithm based authentication schemes from random nonce bits[END_REF], Bauer and Vergnaud designed an attack where the adversary learns partial information on the nonces but not with perfect certainty (but their attack does not apply to ECDSA or Schnorr signatures).

In [START_REF] Chari | Template attacks[END_REF], Chari, Rao and Rohatgi introduced the so-called template attacks which aim at exploiting all the available side-channel information when the adversary can only obtain a limited number of leakage traces (which is the case in our discrete logarithm setting since a nonce is used only once). Template attacks require that the adversary is able to perform a profiling of the side-channel leakage (e.g. based on a copy of the target device under her control). Template attacks against ECDSA were proposed in [MO09,HMHW09,HM09,MHMP13] but none of them considered a blinded implementation of the scalar multiplication.

Our contributions. We consider practical attack scenario, where the target implementation is protected with usual countermeasures and where the adversary recovers some noisy information from a signature computation. We consider an elliptic curve signature based on a regular scalar multiplication algorithm which is protected using classic randomization techniques, such as the masking of projective coordinates and the scalar blinding [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF][START_REF] Ciet | Virtually) free randomization techniques for elliptic curve cryptography[END_REF]. Our contributions are three-fold.

Firstly, we adapt the lattice-based attack proposed by Howgrave-Graham and Smart [START_REF] Howgrave-Graham | Lattice attacks on digital signature schemes[END_REF] to the setting where the adversary gets partial information on blinded nonces of the form k + r • q where r is a small random integer (typically of 32 bits) and q is the elliptic curve group order [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF]. We show that the attack works essentially in the same way than the original one but the number of known bits per nonce must be increased by the bit-length of the random r and the number of unknown blocks of consecutive bits.

Afterwards, we consider a scenario where some noisy information is leaked on the bits of the blinded nonces. Under a realistic leakage assumption, the widely admitted multivariate Gaussian assumption, we show how to model the information recovered by a template attacker. Specifically, we characterize the distribution of the obtained likelihood scores with respect to a multivariate signal-tonoise ratio parameter. We then introduce a filtering method which, given a set of signatures and associated likelihood scores, select the blinded nonce bits to construct the lattice a way to maximize the success probability of the attack. The method relies on a criteria derived from the analysis of the Howgrave-Graham and Smart's attack and techniques from dynamic programming.

Finally, we consider a second implementation setting in which the scalar multiplication is protected by the random Euclidean splitting method [START_REF] Ciet | Virtually) free randomization techniques for elliptic curve cryptography[END_REF]. In this setting, the nonces k are split as k = k/r • r + (k mod r) for a (small) random r and the adversary gets partial information on r, k/r and (k mod r). We show how this partial information can be use to directly get likelihood scores on the nonce bits and we adapt our filtering method to this scenario. For both blinding schemes, we provide some experimental results for our attack based on several values for the multivariate SNR parameter. Our experiments are simulation-based but one could equally use practically-obtained score vectors from a template attack against an actual implementation. The obtained results would be the same for similar multivariate signal-to-noise ratios.

Implementation and Leakage Model

ECDSA Signature Scheme

The ECDSA signature scheme [START_REF]FIPS PUB 186-2: Digital Signature Standard (DSS)[END_REF] relies on an elliptic curve E defined over some finite field K where E(K), the group of K-rational points of E, has (almost) prime order q. The public parameters of the scheme include a description of E(K), a base point P ∈ E(K) that is a generator of the group (or of the large prime-order subgroup), and a cryptographic hash function H :

{0, 1} * → [[0, 2 -1 ]]
, where := log 2 q . The secret key x is randomly sampled over [[0, q -1]] = [0, q) ∩ Z and the corresponding public key is set as the point Q = [x]P , that is the scalar multiplication of P by x.

A signature σ = (t, s) of a message m ∈ {0, 1} * is then computed from the secret key x as t = xcoord([k]P ) and s = k -1 (h+t•x) mod q, where k is a random nonce sampled over [[1, q -1]] and h = H(m). One can then verify the signature from the public key Q by computing u = s -1 h mod q and v = s -1 t mod q, and checking whether xcoord

([u]P + [v]Q) = t. A legitimate signature indeed satisfies [u]P + [v]Q = [s -1 (h + t • x) • h mod q]P = [k]P .

Target Implementation

The attacks presented in this paper target an ECC-signature implementation that relies on a regular scalar multiplication algorithm, which is assumed to be binary in the sense that each loop iteration handles a single bit of the scalar. A prominent example of such a binary regular algorithm is the Montgomery ladder [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF] which is widely used for its security and efficiency features [JY03,IMT02,GJM + 11].

The target implementation is also assumed to include common countermeasures against side-channel attacks such as as the classic scalar blinding [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF] and the Euclidean blinding [START_REF] Ciet | Virtually) free randomization techniques for elliptic curve cryptography[END_REF]:

Classic blinding scheme:

1. r $ ← -[[0, 2 λ -1]] 2. a ← k + r • q 3.

return [a]P

Euclidean blinding scheme:

1. r $ ← -[[1, 2 λ -1]] 2. a ← k/r ; b ← k mod r 3. return [r]([a]P ) + [b]P

Leakage Model

The computation performed during one iteration of any regular binary scalar multiplication is deterministic with respect to the current scalar-bit b and the two points P 0 and P 1 in input of the iteration. The side-channel leakage produced in such an iteration can hence be modeled as a noisy function ψ(b, P 0 , P 1 ). In the following we shall assume that for randomized points (P 0 , P 1 ), the leakage ψ(b, P 0 , P 1 ) can be modeled by a multivariate Gaussian distribution:

ψ(b, P 0 , P 1 ) ∼ N (m b , Σ) , (1)
where m 0 and m 1 are T -dimensional mean leakage vectors and where Σ is a T × T covariance matrix. In what follows, we shall simply denote this leakage ψ(b). The overall leakage of the scalar multiplication [a]P is hence modeled as ψ(a a -1 ), . . . , ψ(a 1 ), ψ(a 0 ) where we further assume the mutual independence between the ψ(a i ) (where the length a of a depends on the randomization scheme).

Profiling Attack

We consider a profiling attacker that owns templates for the leakage of a scalar multiplication iteration w.r.t. the input bit. Based on these templates, the attacker can mount a maximum likelihood attack to recover each bit of the scalar with a given probability. More precisely, the considered attacker can measure the side-channel leakage of a scalar multiplication [a]P , divide the measured traces into sub-traces ψ(a i ), compare the measured leakage with templates for ψ(0) and ψ(1), and determine the probability that a i = 0 or a i = 1 given an observation ψ(a i ).

In particular, we consider the ideal case where the attacker knows the exact distribution of ψ(0) and ψ(1), namely he knows the leakage parameters m 0 , m 1 and Σ. Although this might be viewed as a strong assumption, efficient techniques exist to derive precise leakage templates in practice, especially in our context where the key-space is of size 2 (b ∈ {0, 1}). Even if model-error might lower the probability of correctly recovering a target bit in practice, it would not invalidate the principle of our attacks.

Considering the above leakage model, the probability that the bit

a i equals b ∈ {0, 1} given a leakage sample ψ(a i ) = x i satisfies p b (x i ) := Pr(a i = b | ψ(a i ) = x i ) ∝ exp - 1 2 (x i -m b ) t • Σ -1 • (x i -m b ) , (2)
where ∝ means is equal up to a constant factor, such that p 0

(x i ) + p 1 (x i ) = 1.
Let us define the multivariate signal-to-noise ratio (SNR) θ as

θ = Λ • (m 0 -m 1 ) , ( 3
)
where Λ is the Cholesky decomposition matrix of Σ -1 , that is the upper triangular matrix satisfying Λ t • Λ = Σ -1 . This decomposition always exists provided that Σ is full-rank (i.e. no coordinate variable of the multivariate Gaussian is the exact linear combination of the others) which can be assumed without loss of generality. We have the following result:

Proposition 1. For every x i ∈ R t p 0 (x i ) ∝ exp -1 2 y t i y i if a i = 0 exp -1 2 (y t i y i + 2θ t y i + θ t θ) if a i = 1 (4)
where

y i = Λ • (x i -m ai ). Moreover if x i follows a distribution N (m ai , Σ), then y i follows a distribution N (0, I T )
, where I T is the identity matrix of dimension T .

The above proposition shows that, for any T -dimensional leakage distribution, the outcome of the considered template attack only depends on the multivariate SNR θ. That is why, in Section 6 we provide attack experiments for several values of θ. In practice, one could evaluate the vulnerability of an implementation to our attack by constructing leakage templates for ψ(0) and ψ(1), deriving the corresponding multivariate SNR θ, and simulating probability scores based on Proposition 1.

Lattice Attack with Partially-Known Blinded Nonces

In this section, we recall the lattice attack by Howgrave-Graham and Smart [START_REF] Howgrave-Graham | Lattice attacks on digital signature schemes[END_REF] against ECDSA with partially known nonces, and we extend it to the case where the attacker has partial information on the blinded nonces. The attacker is assumed to collect n + 1 signatures σ 0 , σ 1 , . . . , σ n , for which he knows some bits of the blinded nonces a 0 , a 1 , . . . , a n . These blinded nonces are defined as

a i = k i + r i • q,
where k i is the original (non-blinded) nonce, and r i is the λ-bit random used in the blinding of k i . Additionally, we denote by t i and s i the two parts of the ECDSA signature σ i = (t i , s i ) and by h i the underlying hash value.

Attack Description

By definition, we have s i -a -1 i (h i + t i x) ≡ 0 mod q for every signature σ i . We can then eliminate the secret key x from the equations since we have

x ≡ a i s i -h i t i mod q =⇒ a 0 s 0 -h 0 t 0 ≡ a i s i -h i t i mod q (5)
for every i ∈ {1, . . . , n} . The above can then be rewritten as

a i + A i a 0 + B i ≡ 0 mod q (6)
where

A i = -s0ti sit0 mod q and B i = h0ti-hit0 t0si mod q.
The goal of the attack is to use the information we have on each a i to derive a system of equations which can be reduced to a lattice closest vector problem (CVP). Let us assume we can obtain several blocks of consecutive bits so that a i can be expressed as:

a i = N j=1 x i,j 2 κi,j + x i (7)
where x i is known, and x i,1 , x i,2 , . . . , x i,N are the N unknown blocks. We will denote by µ i,j the bit-length of each x i,j so that we have 0 ≤ x i,j < 2 µi,j . We can now rewrite (6) to obtain a system of linear equations in the x i,j as follows:

x i,1 + N j=2 α i,j x i,j + N j=1 β i,j x 0,j + γ i = η i q (8)
for some known coefficients α i,j , β i,j , γ i ∈ [[0, q -1]], and unknown integers x i,j and η i . Let C ∈ M n,N (n+1)-n (Z) be the matrix defined as

C =      α 1,2 • • • α 1,N β 1,1 β 1,2 • • • β 1,N α 2,2 • • • α 2,N β 2,1 β 2,2 • • • β 2,N . . . . . . . . . . . . . . . α n,2 • • • α n,N β n,1 β n,2 • • • β n,N      (9)
and let x ∈ Z N (n+1)-n and η ∈ Z n be the (column) vectors defined as

x = (x 1,2 , . . . , x 1,N | x 2,2 , . . . , x 2,N | . . . | x n,2 , . . . , x n,N | x 0,1 , . . . , x 0,N ) t , η = (η 1 , η 2 , . . . , η n ) t .
According to (7), we have

C • x -q • η = -(γ 1 + x 1,1 , γ 2 + x 2,1 , . . . , γ n + x n,1 ) t (10)
We consider the lattice L spanned by the columns of the following matrix:

M = C -q • I n -I N (n+1)-n 0 ( 11
)
where I n and I N (n+1)-n denote the identity matrices of dimension n and N (n + 1) -n respectively. In particular, the vector y t = -(x t |η t ) ∈ Z N (n+1) yields the following lattice vector:

M • y = (γ 1 + x 1,1 , γ 2 + x 2,1 , . . . , γ n + x n,1 | x t ) t (12)
which might be close to the non-lattice vector

v = (γ 1 , γ 2 , . . . , γ n , 0, 0, . . . , 0) t (13)
It is indeed easy to check that the Euclidean distance

M • y -v satisfies M • y -v 2 = 0≤i≤n 1≤j≤N x 2 i,j ≤ 0≤i≤n 1≤j≤N 2 2µi,j (14)
If the distance is small enough, and if the lattice dimension (n + 1)N is not too high, one can find M • y as the closest lattice vector to v and hence get the solution to the system. From the latter solution, one can recover the randomized nonces a i (by (7)) which in turn yields the secret key x (by (5)).

Normalization. We consider unknown blocks x i,j that may be of different bitlengths µ i,j . Therefore, we shall normalize the matrix M in order to have the same weight in all the coordinates of M • y, which shall lead to a better heuristic on the resolution of the lattice problem. To do so, let us define ρ i,j ∈ Z as

ρ i,j = 1 2 µi,j . ( 15
)
We then consider the lattice L spanned by the rows of the matrix M = D • M , where D denotes the following diagonal matrix:

D = D (ρ i,1 ) n i=1 (ρ 1,j ) N j=2 (ρ n,j ) N j=2 (ρ 0,j ) N j=1 ( 16
)
where D is the function mapping a vector to the corresponding diagonal matrix. 3The non-lattice vector v is then defined as

v = D • v = (ρ 1,1 γ 1 , ρ 2,1 γ 2 , .
. . , ρ n,1 γ n , 0, 0, . . . , 0) t and the target closest lattice vector is M • y. The distance between these two vectors then satisfies

M • y -v = D • (M • y -v) = 0≤i≤n 1≤j≤N (ρ i,j x i,j ) 2 1 2 ≤ (n + 1)N . (17)

Attack Parameters

We make the classic heuristic assumption that the CVP can be efficiently solved as long as the dimension is not too high and the distance is upper-bounded by

M • y -v ≤ c 0 dim(M ) det(M ) 1 dim(M ) , (18)
for some constant c 0 = 1/ √ 2πe 0.24197 (see for instance [START_REF] Faugère | Attacking (EC)DSA given only an implicit hint[END_REF]). In our attacks, we will actually use the polynomial-time LLL [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] algorithm in order to recover the lattice vector M • y. This gives a slightly worse inequality in (18) and the CVP can be efficiently solved for smaller values c 0 that may actually depend on the dimension of the lattice.

Let us denote by µ i = j µ i,j the number of unknown bits in a i , and by µ = i µ i the total number of unknown bits. Let us also denote by δ i = +λ-µ i the number of known bits in a i , and by δ = i δ i = (n + 1)( + λ) -µ the total number of known bits. The dimension of the matrix M is (n + 1)N and its determinant is det(M ) = det(M ) • det(D) = q n • 2 -µ . By (17), the above inequality is satisfied whenever we have4

1 ≤ c 0 (q n • 2 -µ ) 1 N b ⇐⇒ µ + c 1 N b ≤ n • log 2 (q) < n , (19)
where N b = (n + 1)N denotes the total number of unknown blocks in the n + 1 signatures, and where c 1 is a constant defined as c 1 = -log 2 (c 0 ) > 0. We can deduce a sufficient condition on the number of bits δ that must be known for the attack to succeed:

δ ≥ + (n + 1)λ + c 1 N b ⇐⇒ n i=0 (δ i -λ -c 1 N ) ≥ . ( 20
)
This means that in order to mount a lattice attack against ECDSA protected with classic randomization of the nonce, one must recover at least (λ + c 1 N ) bits of each blinded nonce plus some extra bits, where the total amount of extra bits must reach .

Varying number of blocks. For the sake of clarity, we described the attack by assuming a constant number N of unknown blocks for all the signatures. Note that the attack works similarly with a varying number of blocks N 0 , N 1 , . . . , N n and the above condition keep unchanged. To see this, simply consider the above description with N = max i N i and µ i,j = 0 for every j > N i . Note however that for different block sizes, we have

N b = n i=0 N i instead of N b = (n + 1)N .

Experiments

The CVP can be solved using Babai's rounding algorithm [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF], but in practice one shall prefer the embedding technique from [START_REF] Goldreich | Public-key cryptosystems from lattice reduction problems[END_REF]. This technique reduces the CVP to the shortest vector problem (SVP), by defining the embedding lattice L emb spanned by the columns of

    M v 0 • • • 0 -K     (21)
where K is a constant taken to be of the same order as the greatest coefficient of

M . Informally, if M • y ∈ L is close to v, then w = (M • y -v) t | K t
is a short vector of the embedding lattice L emb . By applying LLL to L emb , one can therefore recover w as the shortest vector in the reduced basis, from which M • y is easily deduced.

In order to validate the constraint on the parameters (see (20)) and determine the actual value of c 1 , we experienced the attack using the embedding technique with different set of parameters. Specifically, we used the ANSSI 256-bit elliptic curve ( = 256), different random sizes (λ ∈ {0, 16, 32, 64}), different numbers of signatures ((n + 1) ∈ {5, 10, 20}), as well as different numbers of blocks per signature (N ∈ {1, 2, 5, 10}). In each experiments, the blocks were randomly distributed in the blinded nonces (by randomly sampling the starting index among possible ones). Additionally, we considered that the number of bits per block could vary according to a standard deviation parameter σ as follows. The bit-length δ i,j of each block is randomly sampled according to the distribution N (m, σ) with m = δ/N b , where we recall that δ = i,j δ i,j is the total number of known bits and N b = (n + 1)N is the total number of unknown blocks. Samples are then rounded to the nearest integer with rejection for samples lower than 1 (minimum number of bits per block). Finally, samples are randomly incremented or decremented until they sum to the desired value δ. In a nutshell, taking a standard deviation σ = 0 makes all the δ i,j 's equal to m. On the other hand, taking a standard deviation to σ ≈ m makes the δ i,j 's to vary over [[1, 2m]] (with a few ones beyond 2m). For our experiments, we took σ = 0.1m (slight deviation), σ = 0.5m (medium deviation), and σ = m (strong deviation).

In each setting, the number of known bits is set to δ = + (n + 1)λ + τ for a varying margin τ that shall correspond to c 1 N b . For each tested value of τ , we record the success rate of the attack over 100 trials. Table 1 summarizes the obtained ratio τ 95 /N b where τ 95 is the margin required to obtain a 95% success rate. This ratio gives a good estimation of the practical value of c 1 . We observe that for the tested parameters, the experimental value of c 1 lies between 3 and 5 most of the time. We also observe that the size of the random (λ) and the deviation on the number of bits per known blocks have a small impact on the resulting c 1 , whereas the number of signatures and the total number of blocks have a stronger impact.

Attacking Implementations with Classic Blinding

In this section we focus on attacking implementations of elliptic-curve signatures that leak side-channel information on the blinded nonce as described in Section 2. In this model, one performs a template attack on the randomized scalar multiplication and recovers a probability score Pr(a i,j = 0) for every bit a i,j of every blinded nonce a i . The goal is then to select a set of bits among all the recovered noisy bits that has the required properties for solving the associated lattice system and that has the highest possible probability of success (i.e. all the selected bits must have been correctly guessed based on the probability scores).

For the lattice construction, we shall use the most probable value âi,j of each bit a i,j , that is âi,j = argmax b∈{0,1}

Pr(a i,j = b) ,

and we shall denote by p i,j the probability that the bit a i,j is correctly guessed, that is

p i,j = Pr(â i,j = a i,j ) = max b∈{0,1} Pr(a i,j = b) . ( 23
)
Let I denote the set of indices corresponding to the selected signatures {σ i } i∈I and let J i denote the set of indices corresponding to the selected guessed bits {â i,j } i∈Ji within a random nonce for every i ∈ I. Then we will use the bits {â i,j |i ∈ I, j ∈ J i } to construct the lattice. The CVP's algorithm will only succeed in recovering the right solution if all these bits are correctly guessed, namely if âi,j = a i,j for every i ∈ I and j ∈ J i . The probability p that these success events happen satisfies

p = i∈I p i with p i = j∈Ji p i,j , (24)
where p i is the probability that all the guessed bits within the random nonce a i are correct. Our goal is hence to define the sets I, and J i for every i ∈ I such that the success probability is maximal and such that the prerequisites of the lattice attack are well met.

Let N i denote the number of unknown blocks in the blinded nonce a i , i.e. the number of non-adjacent blocks of indices j / ∈ J i . The dimension ∆ of the lattice satisfies ∆ = i∈I N i (see Section 4). Let ∆ max be the maximal dimension of a lattice for which the attack can be practical, i.e. the LLL-reduction can be done in a reasonable time. 5 The selected bits must then satisfy

i∈I N i ≤ ∆ max . (25)
Following Section 4, we denote by δ i = |J i | the number of recovered bits in the nonce a i . We recall the necessary condition for the lattice reduction to work:

i∈I (δ i -λ -c 1 N i ) ≥ . ( 26
)
From the two above conditions, a requirement for the selected bits within a blinded nonce a i is to satisfy:

δ i -λ N i > ∆ max + c 1 . (27)
Otherwise, the contribution in terms of known bits is too small with respect to the increase of the lattice dimension. In other words, if the above condition is not satisfied then the maximal dimension ∆ max is reached before the number of necessary known bits.

The above condition on the pair (δ i , N i ) is not sufficient in itself as it does not specify how to select the sets J i maximizing the success probability. Our goal is now to define a sound criterion on each signature that will allow us to select the best sets J i i.e. the set maximizing the success probability defined in (24). Maximizing this probability is equivalent to maximizing the log-success probability log(p) = i∈I log(p i ), and maximizing the latter sum while satisfying (26) can be done by selecting the sets J i with maximal ratio log pi δi-λ-c1Ni . We hence look for the set of indices J i that maximizes the following value

γ i = p 1 δ i -λ-c 1 N i i . ( 28
)
Let f : N →

•N ∆max + c 1 N + λ be the function that define the minimum number of known bits from a number of unknown blocks for condition (27) to hold. For each signature σ i and for each possible number of blocks N ∈ 1, N max we define:

J i (N ) = argmax J;|J|=f (N ) g(J)≤N j∈Ji p i,j , (29)
where the function g(J) gives the number of unknown blocks in the set J.

We then define

p i (N ) = j∈Ji(N ) p i,j and γ i (N ) = p i (N ) 1 f (N )-λ-c 1 N . (30)
Eventually, we shall set

N i = argmax N γ i (N ) , γ i = γ i (N i ) , J i = J i (N i ) , and δ i = f (N i ) .
Remark 1. At this point, a natural idea is to take I as the set of indices with the highest values γ i . However, this strategy is not reliable in practice. Indeed, it can occur that a bad guess âi,j = a i,j comes with a strong probability p i,j (i.e. one gets a strong confidence in the wrong choice). Since each γ i aggregates many probabilities p i,j , the occurrence of such an extreme event is only marginally correlated to the actual value of γ i .

In view of the above remark, our approach in practice is to try several random combinations of signatures, namely to take I uniformly at random among the subsets of signatures (tightly) satisfying the constraint (26).

Evaluating Equation (29). We now explain how to evaluate the function

N → max J;|J|=f (N ) g(J)≤N j∈Ji p i,j (31)
for some family of probabilities p i,0 , p i,1 ,. . . , p i, +λ-1 (getting the argmax is then straightforward). For this purpose, we define maxp as the function mapping a triplet (j, δ, N ) to the above max but with the condition J ⊆ [[j, + λ -1]], |J| = δ, and g(J) ≤ N , so that the target function in (31) can be rewritten as:

N → maxp(0, f (N ), N ) (32)
The maxp function can then be evaluated by the following recurrence relation:

maxp(j, δ, N ) = max block(j, δ, N ), next(j, δ, N ) (33)
where block(j, δ, N ) = max

w∈[[1,δ]] j+w-1 k=j p i,k maxp(j + w + 1, δ -w, N -1) , (34)
next(j, δ, N ) = maxp(j + 1, δ, N ) . (35)
The term block(j, δ, N ) in the above max represents the case where the next w bits are added to the set J, while the term next(j, δ, N ) is for the case where the next bit is not taken in the set J. 6 The tail of the recursion is fourfold:

maxp(j, δ, N ) =          0 if j + δ > + λ +λ-1 k=j p i,k if j + δ = + λ 0 if N = 0 and δ > 0 1 if δ = 0 (36)
Remark 2. In order to get a higher success probability, we can also use exhaustive search to guess certain bits in a signature. In fact, between two blocks of bits selected by the block function, we can find a small block of bits with poor probability score which will discard the chance of selecting a larger unique block.

To tackle this issue and improve the probability of success, we can use exhaustive search to recover these bits with probability 1 (independently of the underlying p i,j values). This improvement of our method is described in Appendix A.

Attacking Implementations with Euclidean Blinding

In this section we focus on attacking implementations protected with Euclidean blinding [START_REF] Ciet | Virtually) free randomization techniques for elliptic curve cryptography[END_REF], i.e. for which the nonces are decomposed as k i = a i • r i + b i for i ∈ {1, . . . , n} where r i is picked uniformly at random over 1, 2 λ -1 , a i = ki ri and b i = k i mod r i (see Section 3). We suppose that the attacker can recover the probability score for every bit of a i , r i and b i for i ∈ {1, . . . , n} with the same template attack as in the previous section. One approach to mount an attack is to use the information we have on each nonce to derive a system of equations which we may solve using a lattice attack. The equations are of degree 2 and the number of involved monomials increases quadratically with the number of unknown blocks. A natural idea is to use the famous 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] which is a family of lattice-based techniques to find small integer roots of polynomial equations. The method generates more non-linear equations by multiplication of several non-linear equations before the linearization step in order to improve attacks. However, in this case the structure of the variables is complex and even using polynomials of small degree leads to a lattice of very large dimension.

Our approach is different and practical: from the recovered noisy bits, one can compute probability scores for the individual bits of the nonces k i themselves. If the probability that the individual bits in a i , r i and b i for i ∈ [[1, n]] are all correctly guessed is equal to 1/2 + ε, for some ε > 0, it can be checked that the obtained probabilities Pr( ki,j = k i,j ) that the j-th bit of the nonce k i is correctly guessed tends towards 1/2 quickly as j grows towards the middle bit /2. To show this fact, we ran the following experiments:

for several bias ε ∈ {1/4, 1/8, . . . , 1/24}, we picked uniformly at random 10,000 nonces k i and random r i (for λ = 16) and we computed the corresponding a i and b i such that a i • r i + b i = k i ; we computed noisy versions of (ã i , ri , bi ) of (a i , r i , b i ) as if they were transmitted over a binary symmetric channel with crossover probability ε and we computed ki = ãi • ri + bi ; for each bias and each individual bit, we computed the proportion of ki,j that matches k i,j .

The estimated error probability Pr( ki,j = k i,j ) is plotted in Figure 1 for the first 64 bits (in log-scale for the x-axis). These experiments show that the probabilities Pr( ki,j = k i,j ) tends towards 1/2 exponentially as j comes close to the middle bit /2. For this reason, in the case of the Euclidean blinding, we will only focus on two particular blocks of k i for each signature: the block of δ i,1 least significant bits (lsb) and the block of δ i,2 most significant bits (msb), for some δ i,1 , δ i,2 . In this model, the necessary condition for the lattice reduction to work (see (20)) becomes:

i∈I (δ i -c 1 ) ≥ where δ i = δ i,1 + δ i,2 , (37)
since λ = 0 and N i = 1 (there is a single unknown block per nonce), implying:

δ i ≥ ∆ max + c 1 (38)
as a sound condition on each signature. As seen in the previous sections, the CVP algorithm will only succeed in recovering the right solution if the two blocks of k i are correctly guessed for each signature. In order to select the blocks and their respective sizes δ i,1 , δ i,2 , we use an approach similar to the one proposed in Section 5. Let B i,1 and B i,2 denote the blocks of δ i,1 lsb and δ i,2 msb of k i . The guessed blocks are defined as:

Bi,j = argmax x∈{0,1} δ i,j Pr(B i,j = x) (39)
for j ∈ {1, 2}. The block probabilities are then defined as

p i,j = Pr(B i,j = Bi,j ) = max x Pr(B i,j = x)
for j ∈ {1, 2} and the probability for one signature is p i = p i,1 • p i,2 . Then, we select δ i,1 and δ i,2 such that they maximize the value γ i = p

1 δ i -c 1 i .
Clearly, γ i depends on the sizes δ i,1 and δ i,2 of the blocks B i,1 and B i,2 . We shall denote γ i (δ i,1 , δ i,2 ) to see γ i as a function of these sizes. We then set δ i,1 and δ i,2 as (δ i,1 , δ i,2 ) = argmax (δ1,δ2) γ i (δ 1 , δ 2 ) so that γ i = max (δ1,δ2) γ i (δ 1 , δ 2 ). Unlike for the classic blinding (see Remark 1), the number of selected bits δ i per signature can be small (it just has to be greater than c 1 ). Therefore, it is more relevant to select the signatures according to the γ i value in the case of the Euclidean blinding. In order to still allow several selection trials, we suggest a hybrid approach: we first randomly pick half of the available signatures and then select a subset I among them such that the values (γ i ) i∈I are the highest, and such that the constraint (37) is well (tightly) satisfied.

Computation of block probabilities. We now explain how to evaluate (39), i.e. how to evaluate the probabilities Pr(B i,1 = x) and Pr(B i,2 = x). For the sake of simplicity, we drop the index i, namely we consider a nonce k = a • r + b for which we know some probability score Pr(a j = 1), Pr(r j = 1) and Pr(b j = 1) for the bits of a, r, and b. Moreover, for some integer v, we shall denote v [j0:j1] = v 2 j 0 mod 2 j1-j0 , i.e. the integer value composed of the j 0 -th bit to the (j 1 -1)th bit of v. It is easy to check that the block B 1 = k [0:δ1] only depends on the δ 1 lsb of a, r and b. We can then compute the probability Pr(B 1 = x) as:

Pr(B 1 = x) = x,y,z χ 1 (x, w, y, z) δ1-1 j=0
Pr(a j = w j ) Pr(r j = y j ) Pr(b j = z j ) (40) with χ 1 (x, w, y, z) = 1 if x = (w • y + z) [0:δ1] and χ(x, w, y, z) = 0 otherwise.

For the case of the block B 2 = k [ -δ2: ] , we shall denote by a h and r h the δ msb of a and r respectively for some δ (i.e. a h = a [ -λ-δ: -λ] and r h = r [λ-δ:λ] ). We then have

k [ -2δ: ] = a h r h + c where c = a • r + b -a h r h 2 -2δ 2 -2δ . (41)
It can be checked that the carry c is lower than 2 δ+1 . Then if we take δ sufficiently greater than δ 2 , we get B2 = B 2 with high probability, where B2 denotes the δ 2 msb of a h r h (i.e. B2 = (a h r h ) [2δ-δ2:2δ] ). We then approximate

Pr(B 2 = x) ≈ Pr( B2 = x) = 2 2δ-δ 1 x0=0 Pr(a h r h = x 0 + 2 2δ-δ1 x) , (42)
where the probability mass function of a h r h satisfies

Pr(a h r h = x) = w,y χ 2 (x, w, y) δ-1 j=0 Pr(a -λ-δ+j = w j ) Pr(r λ-δ+j = y j ) (43)
where χ 2 (x, w, y) = 1 if x = w • y and χ 2 (x, w, y) = 0 otherwise. The above approximation is sound as long as we take δ sufficiently greater than δ 2 . Since we have c ≤ 2 δ+1 , it can be checked that the approximation error is upper bounded by 2 δ1+1-δ . We shall then take δ such that the latter approximation error does not impact the selection of the maximal probability Pr(B 2 = x).

Experimental Results

This section provides experimental results: we have implemented our attacks against ECDSA on the ANSSI 256-bit elliptic curve (i.e. = 256) with the two considered blinding schemes for 3 different random sizes, specifically λ ∈ {16, 32, 64}. We considered a three-dimensional leakage model with unbalanced multivariate SNR θ = α • (0.5, 1, 2), where α ∈ {1.5, 2.0}. For each setting, the used signatures and blinded nonces were randomly generated, and the corresponding likelihood scores were simulated from the multivariate SNR θ as shown in Proposition 1. We then applied our filtering methods to select the best blocks of bits from which we constructed the Howgrave-Graham and Smart lattice with the constant c 1 set to 4, and we checked whether the correct solution was well retrieved by the CVP algorithm. We experimented our attacks with n sig available signatures and n tr trials for the subset selection (and the underlying lattice reduction) for (n sig , n tr ) ∈ {(10, 1), (20, 5), (20, 10), (100, 10), (100, 50), (100, 100)}.

The obtained success rates are reported in Table 2. The lattice reduction worked almost every time the selected bits were correctly guessed (we noticed only a few lattice failures in all the performed experiments). These results suggest that the classic blinding is more sensitive to our attack than the Euclidean blinding. However, one should note that the classic blinding is inefficient when the group order is sparse. We also observe that for the Euclidean blinding, the random size λ has a small impact on the resulting success rate, which is not surprising since it can be checked from Section 5 that this parameter is not expected to play a significant role.

A Using Exhaustive Search

In order to increase the success probability of our attack, we can make use of exhaustive search to guess certain bits in a signature. Specifically, we can select m bits among all the signatures for which we shall try the 2 m possible values and apply the previously defined lattice attack. To select the guessed bits in a signature we follow the same approach as previously but with a new dimension for the parameters: the number of bits allowed to be exhaustively guessed. Specifically, we shall compute the optimal parameters γ i , J i and N i for each possible m i ≤ m max , where m i is the number of bits exhaustively guessed in the i-th signature and m max is the maximal value for m. We hence get a new constraint to the selection of the signatures, that is:

n i=0 m i ≤ m max . (44)
Let us introduce the function π i defined for every J ⊆ [[0, + λ -1]] and m ∈ N as:

π i (J, m) = max J ⊆J |J |=|J|-m j∈J p i,j . (45)
Namely, π i (J, m) is the maximal product of |J|-m probabilities among (p i,j ) j∈J . This gives the probability of correctly guessing the bits (a i,j ) j∈J while m among them are exhaustively guessed. We then define

J i (m, N ) = argmax J;|J|=f (N ) g(J)≤N π i (J, m) (46)

Table 1 .

 1 Ratio τ95/N b for various set of parameters.

			(n + 1) = 5			(n + 1) = 10		(n + 1) = 20
	Nb =	5	10	25	50	10	20	50	100	20	40	100
	λ = 0 (slight dev)	2.80 2.50 2.36 2.90 3.90 3.55 3.58 4.62 5.20 4.90 5.26
	λ = 0 (medium dev)	3.60 2.60 2.56 2.90 4.10 3.30 3.52 3.57 4.85 4.42 4.51
	λ = 0 (strong dev)	3.20 2.50 2.28 2.54 4.10 2.95 3.14 3.07 5.25 4.17 3.93
	λ = 16 (slight dev)	3.40 2.80 2.44 2.90 3.80 3.35 3.62 4.75 5.05 4.95 5.5
	λ = 16 (medium dev)	3.40 2.60 2.40 3.02 4.20 3.15 3.40 4.20 5.25 4.77 4.96
	λ = 16 (strong dev)	3.60 2.50 2.36 2.66 3.70 3.05 3.24 3.29 5.25 4.67 4.28
	λ = 32 (slight dev)	3.80 2.70 2.68 3.06 3.80 3.45 3.74 4.71 4.75 4.70 5.17
	λ = 32 (medium dev)	3.40 2.60 2.60 2.68 3.90 3.10 3.60 4.07 4.95 4.50 5.12
	λ = 32 (strong dev)	3.00 2.90 2.36 2.60 4.00 3.05 3.32 3.41 4.90 4.73 4.62
	λ = 64 (slight dev)	3.00 2.90 2.52 2.98 3.80 3.35 3.44 4.72 4.70 4.77 5.24
	λ = 64 (medium dev)	3.20 2.80 2.36 2.98 3.70 3.55 3.68 4.31 4.80 4.60 5.23
	λ = 64 (strong dev)	3.20 2.80 2.44 2.72 3.50 3.40 3.68 3.78 5.45 4.30 4.75

Table 2 .

 2 Success rate of our attacks.

	(nsig, ntr)	(10,1)	(20, 5)	(20, 10) (100, 10) (100, 50) (100, 100)
				Classic blinding
		λ = 16 13.5 % 38.3 %	54.0 %	70.1 %	99.0 %	99.9 %
	α = 1.5	λ = 32 3.5 %	13.6 %	22.7 %	27.8 %	73.9 %	91.9 %
		λ = 64 0.2 %	0.6 %	1.2 %	1.5 %	6.2 %	11.7 %
		λ = 16 91.2 % 99.9 %
	α = 2	λ = 32 90.5 % 99.5 %	100 %	100 %	100 %	100 %
		λ = 64 85.7 % 99.3 %
				Euclidean blinding
		λ = 16
	α = 1.5	λ = 32	0 %	0 %	0 %	0 %	0 %	0 %
		λ = 64
		λ = 16 0.7 %	3.1 %	5.8 %	42.8 %	76.8 %	83.3 %
	α = 2	λ = 32 0.1 %	0.4 %	0.8 %	41.1 %	74.9 %	82.6 %
		λ = 64 0.1 %	0.4 %	1.0 %	40.2 %	75.0 %	82.8 %

In practice, we might take ρi,j = 2 µmax-µ i,j where µmax = maxi,j µi,j to work over the integers.

In[START_REF] Howgrave-Graham | Lattice attacks on digital signature schemes[END_REF], Howgrave-Graham and Smart overlooked the linear dependency in N b in (19) as they assumed c0 = 1. As we show in Section 3.3, this increase in the number of known bits is not an artifact of the technique but is actually necessary.

For our experiments, we took ∆max = 256 for which SageMath (using the fplll library) performs the reduction within 20 seconds on a 2.0 GHz Intel Xeon E5649 processor.

A particular case occurs when j = 0 for which the recursive call to maxp in block does not decrement N since no unknown block appears before the index j = 0.

Acknowledgments. The authors were supported in part by the French ANR JCJC ROMAnTIC project (ANR-12-JS02-0004).

and

from which we set

(48) Eventually, we select I and (J i (m i )) i∈I such that (44) and

are both satisfied.

Evaluating Equation (46). We now explain how to evaluate the function

from which getting the argmax is then straightforward. For such a purpose, we extend the maxp function of Section 4 to deal with the m parameter i.e. the number of bits that can be exhaustively guessed. Here, maxp maps a quadruple (j, δ, N, m) to the above max with the condition J ⊆ [[j, + λ -1]], |J| = δ, and g(J) ≤ N , so that the target function in (50) can be rewritten as:

The difference with the original method is that in a recursive call to the maxp function, one can spend v out of m bits to be exhaustively guessed. Specifically, the recurrence relation becomes:

The recursion tail is pretty similar to the original case:

Only the second case changes, where the m left bits of exhaustive search are spend for the final block.


est destinée au dépôt

Comment on "The 'inverted Bonds' revisited. Analysis of 'in silico' models and of [1.1.1]Propellane using Orbital Forces"

Benoît Braïda,* [a] Sason Shaik, [b] Wei Wu, [c] and Philippe C. Hiberty* [d] Keywords: [1.1.1]Propellane, Charge-Shift Bonds, Inverted Bonds, Orbital Forces, Valence

Bond

In a recent publication in this journal, Laplaza, Contreras-Garcia, Fuster, Volatron and

Chaquin [1] (LCFVC) report an application of the Dynamical Orbital Forces (DOF) method, [2] which was used by the authors to challenge the presence of an inverted central C-C bond in [1.1.1]propellane (1 in Scheme 1), which was suggested long ago by Jackson and Allen, [3] then by Feller and Davidson, [4] and recently given theoretical support on the basis of ab initio valence bond calculations. [5] Scheme 1. The [1. 1.1]propellane and bicyclo[1.1.1]pentane molecules

The DOF of a molecular orbital (MO) is the derivative of its energy with respect to distance between two atoms of the molecule. This quantity is interpreted, on the basis of Koopmans' theorem, as the force exerted on the nuclei along this interatomic distance by removal of one electron from the MO, in the frozen MO approximation. The positive/negative sign of the [a] Dr. Benoît Braïda, Sorbonne Université, Laboratoire de Chimie Théorique, 75005, Paris, France. E-mail: benoit.braida@sorbonne-universite.fr [b] Prof. Dr. Sason Shaik, Institute of Chemistry, The Hebrew University of Jerusalem, 9190401 Jerusalem, Israel.

[c] Prof. Wei Wu, State Key Laboratory of Physical Chemistry of Solid Surfaces, Fujian Provincial Key Laboratory of Theoretical and Computational Chemistry, and Department of Chemistry, Xiamen University, Xiamen, Fujian 361005, China.

[d] Prof. Philippe C. Hiberty Laboratoire de Chimie Physique, CNRS UMR8000, Bat. 349, Université de Paris-Sud, 91405 Orsay Cédex, France. E-mail: philippe.hiberty@u-psud.fr

H 2 C CH 2 H 2 C H 2 C CH 2 H 2 C H H 1 2
DOF is used as a mean to characterize the bonding/antibonding nature of the MO with respect to the two atoms in question. As an extension of this model, the DOFs with respect to a given interatomic distance are summed over all the MOs (fi) of a molecule, and the result S(DOFi)

is considered as the central quantity that determines the nature and strength of a particular bond. A large positive S(DOFi) corresponds to a strong bond, [1,6,7] while a negative S(DOFi) signifies a repulsive interaction. This method was recently applied to a series of hydrocarbons and a linear correlation was found between the CC bonding energies and the CC S(DOFi). 7 Back to [1.1.1]propellane 1 in Scheme 1: this cage molecule was long supposed to possess a significant s bond between the two bridgehead carbons [3,4] owing to its remarkably weak enthalpy of formation (only 143 kcal mol -1 ) by extrusion of two hydrogen atoms from bicyclo[1.1.1]pentane 2. This value is significantly smaller than twice the standard bonding energy of a C-H bond. The presence of this central s bond in 1 was confirmed by ab initio calculations of the "breathing-orbital valence bond" (BOVB) type. [5] These calculations confirmed the order of magnitude of ca. 60 kcal mol -1 , that was estimated in previous studies for this bond based on the above thermodynamic considerations.

Two features of the bridgehead bond in 1 are noteworthy: (i) the bonding interaction takes place between two sp 3 -like hybrid atomic orbitals (HAOs) pointing away from the center of the molecule, hence its description as an "inverted bond" ; (ii) at variance with classical covalent bonds, the bonding strength of the bridgehead CC bond is mostly due to the stabilizing resonance interaction, C•-•C « [C + :C -+ C: -C + ], i.e. the resonance energy arising from mixing of the purely covalent component of the bond with its ionic components. At the same time, the covalent part alone C•-•C, involving singlet-coupling between the two HAOs, although being significantly stabilizing, cannot by itself overcome the large repulsions from the surrounding wing C-C bonds, and is thus overall only slightly repulsive. Such bonds that are dominated by the resonance energy of the constituent VB structures that differ by a shift of charge are qualified as "Charge-shift bonds" (CSBs) and constitute a bonding class on their own, quite different by many aspects from classical covalent bonds. [8] By contrast to the BOVB study, the bridgehead bond was diagnosed as being absent in the LCFVC paper, on account that the negative S(DOFi) of the MOs considered as being relevant to this bond (we will come back to this point later). Since the correlations of S(DOFi)

to bonding energies (BEs) were established for a series of CC bonds that are all of classical covalent bonding types, [7] whereas the bridgehead bond of [1.1.1]propellane was characterized as a typical CSB by our high level ab initio valence bond study, it is therefore important to check whether or not the DOF-BE relationship still holds for CSBs. Furthermore, since CSBs are generally found when the bond is surrounded by adjacent Pauli repulsion, it is also useful to test the adequacy of the DOF method for handling this latter kind of electronic interaction.

These two key questions are addressed here by means of our own DOF calculations in the three following sections, in the light of the DOF analysis of the prototypes ground state of difluorine anion F2 -(which is a pure CSB), and of the excited 3 Su triplet (which is repulsive and devoid of any bond) and ground 1 Sg states of difluorine F2 (which is a CSB in the ground state).

Is the DOF method reliable for Charge-shift bonds? The difluorine anion example

The difluorine anion, F2 -, is a typical example of a two-center three-electron (2c,3e) bond, usually represented as [F\F] -. In MO terms, such bonds display a doubly occupied bonding MO and a corresponding singly occupied antibonding one. In terms of Lewis structures,

[F\F] -is a resonating combination of two components, F: -•F and F• :F -. As each of these components is, by itself, dissociative, [9,10] the totality of the bonding energy arises from the electron fluctuation, i.e. the resonance between the charge-shift related structures F: -•F « F• :F. As such, the bond in F2 -, like all (2c,3e) bonds, [8,10,11] is a pure CSB. How does the DOF method account for the existence of this bond and its bonding energy?

To address this question, we performed DOF calculations on F2 -at the Restricted Open-Shell Hartree-Fock level (ROHF), using a quadruple-zeta Dunning basis set, aug-cc-pVQZ, with an interatomic distance optimized at the CCSD(T)/aug-cc-pVQZ level. The Gaussian 09 program was used throughout. [12] The results are displayed in Table 1.

Table 1. Energy derivatives of valence MOs of F2 -in its 2 Su anionic state, and of F2 in its 3 Su triplet and 1 Sg ground states, as calculated at the Hartree-Fock and density functional levels, in aug-cc-pVQZ basis set. The F-F interatomic distance in F2 is 1.412 Å, and (dropping the core MOs). It may first be noted that the DOFs correctly characterize the bonding/antibonding natures of the MOs (if one excepts the 1pu MO which is found nonbonding), in agreement with the early aims [6] of this method: the 1sg and 2sg MOs are found to be bonding, all with positive DOFs, whereas 1su, 1pg and 2su have negative DOFs, hence antibonding. However, the sum of the DOFs over all occupied MOs, S DOFi, is significantly negative, (-0.291 a.u.), hence predicting the absence of any bond between the two atoms, and that F2 -would be dissociative. This is of course in absolute disagreement with the experimental bonding energy of F2 -, 30.2 kcal mol -1 . [13] It is noteworthy that the BOVB method, the same as the one that characterized the s bridgehead bond of [1.1.1]propellane and whose results are challenged in Ref. 1, yields a bonding energy of 30.4 kcal mol -1 for F2 -, [10] in perfect agreement with experiment.

To check the effect of changing the Hartree-Fock MOs to Kohn-Sham MOs, as done in Ref. 1, and argued to tentatively bring in electron correlation, we restarted the DOF calculations by using the density functional that was shown to yield the best (2c,3e) bonding energies, [14] the BHandHLYP functional, in the spin-unrestricted version to maximize accuracy. The results are displayed in Table 1, and are quite similar to the ROHF results, with a negative SDOFi of -0.251 a.u., hence still predicting a dissociative F2 -anion. Note that even if SDOFi is restricted to the valence MOs of s type only (those directly responsible for the 2c-3e bond), the value is found to be substantially negative. Thus, in view of these definite failures, one cannot avoid the conclusion that the SDOFi method, when used as means of predicting the existence or absence of bonds actually fails to do so when the bonds are CSB types. But this is not the only failure… Does the DOF method handle Pauli repulsion? The 3 S u triplet state of F2.

In the MO framework, the ground configuration of the 3 Su state of F2 is 1sg 2 1su 2 1pu 4 1pg 4 2sg 1 2su 1 . The elementary representations of this state are equivalent in the Hartree-Fock and valence bond frameworks, and in the latter the picture is that of two fluorine atoms displaying some Pauli repulsion between their respective s HAOs, each bearing a single electron with alpha spin. In accord, at the F…F distance of 1.412 Å (the equilibrium distance of singlet F2) the 3 Su state of F2 lies some 110 kcal mol -1 above the two separate F• atoms, as calculated at the ROHF level.

The results of our DOF calculations on the ROHF wave function of the 3 Su state at an interatomic distance of 1.412 Å are displayed in Table 1. Once again, the bonding/antibonding characters of the MOs are correctly assigned by the respective DOFs, positive for the bonding orbitals and negative for the antibonding ones. On the other hand, the strongly repulsive nature of this triplet state is definitely missed by the sum of the DOFs over all the occupied orbitals, as SDOFi is found to be slightly positive (0.069), which in this framework would characterize a slightly attractive interaction.

Furthermore, this SDOFi value can be decomposed into an interaction (SDOFi,s = 0.016) that is close to non-bonding in the s system, despite the expected repulsion between two electrons with parallel spins, and a slightly attractive interaction in both p systems (SDOFi,p = 0.053). These assignments are in contrast with the fact that each of these DOF components is a closed-shell system of p lone pairs which should undergo some fourelectron-two-orbital Pauli repulsion. So, somehow surprisingly, the errors of the SDOFi predictions are in opposite directions for the bonded F2 -vs. the repulsive triplet state of F2.

While in the first case SDOFi predicts a repulsion where there is a bond, in the second case it predicts a slight attraction where there is a strong repulsion.

The ground state of F2

In view of the above results, it is difficult to tell what would the DOF method predict for the F2 bond, which is a CSB. On the one hand, this molecule is found repulsive at the Hartree-Fock level (by ca. 31 kcal mol -1 at the experimental bonding distance), so in all rigor the DOF method should find it repulsive too, since it analyzes precisely the Hartree-Fock wave function. On the other hand, F2 is experimentally found to be bound by 38.3 kcal mol -1 . [START_REF]NIST data base[END_REF] Be it as it may, the DOF method finds F2 to possess a large positive SDOFi value (Table 1), and hence to be bound, despite its repulsive nature in the Hartree-Fock level. This latter result deserves comments.

First, the F2 bond is the site of a strong "lone pair bond weakening effect" (LPBWE) discovered long ago by Sanderson. [START_REF] Sanderson | Polar Covalence[END_REF] This effect originates primarily in the Pauli repulsion between the bonding electrons and the lone pairs that have the same symmetry as the bond, as shown in Scheme 2, and was estimated as ca. 77 kcal mol -1 in a computational study. [START_REF] Lauvergnat | [END_REF] Second, the charge-shift resonance energy (RECS) arising from the mixing of covalent and ionic structures is also very large, computed as 67 kcal mol -1 , making this molecule the prototype of pure CSB. [18] As was seen above, the neglect of these two effects by the DOF method is responsible for the DOF failure in triplet F2, as well as for the failure in F2 -. On the other hand, since the LPBWE and RECS are respectively repulsive and attractive, their joint absence in the DOF analysis of F2 somehow cancel out, so that the DOF result is correct, owing to cancellation of errors.

Scheme 2. The LPBWE in the ground state of F2

Interestingly, the S DOFi value for F2 is quite large, 0.661 a.u. and even 0.826 a.u. in Ref. 7, to be compared with 0.412 a.u. for ethane, [7] whereas the bond strengths (De values) are in the reverse order, 38.3 and 97.0 kcal mol -1 , respectively. [START_REF]NIST data base[END_REF] This apparent paradox can be explained by the fact that the DOF method is based on orbital-energy derivatives, while orbital energies are themselves dominated by the reduced resonance integral ß for bonding as well as antibonding MOs. Therefore, the DOF for a given MO is directly connected to the variation of ß with the interactomic distance. However, all other things being equal, this ß integral increases in absolute value from left to right of the Periodic Table [18] and so does its derivative, thus explaining the large S DOFi value found for F2, entirely based on a counting of orbital energy derivatives, but not quantifying the strength of the respective bond.

DOF Analysis of the inverted bond in [1.1.1]propellane

The ß-dependence of the DOF method has an interesting consequence. Apart from the abovenoted tendency in the Periodic be considered as a negative combination of bonding fragment orbitals localized on wing bonds, as indicated by its shape, the absence of axial p atomic orbitals, and the low orbital energy (-0.533 hartrees, this work). Thus, the largely negative DOF of -0.109 a.u. for this MO is better interpreted as being due to the out-of-phase combination of bonding wing orbitals rather than to the minor contribution of the central bond. Now, keeping or removing this MO from the DOF analysis reverses conclusions of the analysis, which leads to a very small but positive DOF value, in accordance with the very small ß in this case. In view of such uncertainties, the attribution of a SDOFi of -0.029 a.u. to the central bridgehead bond alone appears as largely arbitrary. Incidentally, this difficulty to separate interactions from each other is also the problem that is encountered in the first section of the LCFVC paper, with the inverted C2H6 model. As the two methyl fragments approach each other in an inverted geometry, some H-H repulsions take place, blocking the approach at a long distance and preventing any CC bond formation.

However, this latter issue with the DOF analysis, which surfaces in systems that are more complex than simple diatomic molecules, is secondary. The main problems of DOF in analyzing the inverted bond in [1,1,1]propellane, are: i) the inability of the DOF method to account for the "charge-shift" component of bonding as illustrated with F2 -prototype case, ii) the inability of this method to probe situations of large Pauli repulsion, iii) the DOF's inability to probe bonding situation occurring when the overlap and thus ß resonance integral derivative is small. All these factors combine here in the case of the inverted bond of [1,1,1]propellane: large RECS has been previously quantified by means of accurate high level ab initio valence bond calculations, a large Pauli repulsion is present due to small-rings strain, and a quasi-zero ß resonance integral derivative is expected from the quasi-zero overlap between the hybrids involved in the inverted bond.

Conclusion

The DOF method which deals with derivatives of orbital energies may be useful and correlated to bond strengths in cases of small molecules displaying classical covalent bonds, where significant overlap between the respective fragment orbitals of the two atoms is the main factor of bonding, and furthermore if the bonding/antibonding character of MOs is well localized on the bond under study.

For more complex cases, when several factors come into play, the DOF model which is based on sums of MO energy derivatives inevitably misses some important features of the chemical bond, e.g., the Pauli repulsions or charge-shift resonance energies. As a consequence, the DOF method may fail to find bonding interactions, where there is repulsion, and repulsive interactions, where there is a significant bond. This was demonstrated in the case of difluorine in its triplet and anionic states. Finally, switching from Hartree-Fock MOs to Kohn-Sham orbitals as suggested in Ref. 1 does not improve the predictive accuracy of DOF, as shown in the F2 -example.

These severe failures, as well as the delocalized character of the MOs where wing bonds and the central bond are entangled, make the DOF method an inappropriate tool for characterizing the CC inverted bond in [1.1.1]propellane, which is revealed by direct ab initio valence bond calculations [5] as well as electronic stress tensor analysis, [19] density decomposition into paired and unpaired contributions, [20] and experimental Laplacian of the bond critical point. [21]

  Comment on "The 'inverted Bonds' revisited. Analysis of 'in silico' models and of [1.1.1]Propellane using Orbital Forces" Benoît Braïda, Wei Wu, Sason Shaik, Philippe C. Hiberty To cite this version: Benoît Braïda, Wei Wu, Sason Shaik, Philippe C. Hiberty. Comment on "The 'inverted Bonds' revisited. Analysis of 'in silico' models and of [1.1.1]Propellane using Orbital Forces". Chemistry -A European Journal, 2020, 26 (30), pp.6935-6939. 10.1002/chem.201905666. hal-02571872

  Table, the ß integral is proportional to the overlap between the fragments that are involved in the bond. Now, because in such cases the hybrid atomic orbitals (HAOs) interact by their smaller lobes, this overlap is inevitably close to zero in the case of inverted bonds and is not expected to vary significantly with the carbon-carbon distance, leading to a quasi-zero ß integral derivative. It follows that the DOF method is, in principle, unable to detect an inverted bond, be it in [1.1.1]propellane or anywhere else.

	3e repulsion
	F	F
	3e repulsion
	Another problem with the DOF analysis of [1.1.1]propellane is that it cannot cleanly
	separate the wing bonds from the central bridgehead bond in the canonical MOs
	representation, due to the fundamentally delocalized nature of these MOs. In Ref. 1, the MOs
	are divided into two categories, p (e' and e") and s (a'1 and a"2), and all the MOs of the latter
	category are arbitrarily associated to the central bond, whereas two of these MOs, 9a"2 and
	13a'1, are in fact mixtures of wing and central bonds. In particular, the 9a"2 MO should rather


Thierry Mefenza

Damien Vergnaud

Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function

Keywords: Dodis-Yampolskiy pseudo-random function, discrepancy, polynomial interpolation, finite fields, elliptic curves

We give some theoretical support to the security of the cryptographic pseudo-random function proposed by Dodis and Yampolskiy in 2005. We study the distribution of the function values over general finite fields and over elliptic curves defined over prime finite fields. We also prove lower bounds on the degree of polynomials interpolating the values of these functions in these two settings.

Introduction

A cryptographic pseudo-random function family is a collection of functions that can be evaluated in polynomial-time using a secret key but for which no polynomial-time algorithm can distinguish (with significant advantage) between a function chosen randomly from the family and a truly random function (i.e. whose outputs are sampled uniformly and independently at random). In 2005, Dodis and Yampolskiy [START_REF] Dodis | A verifiable random function with short proofs and keys[END_REF] proposed an efficient pseudo-random function family which takes inputs in {1, . . . , d} (for some parameter d ∈ N) and outputs an element in a group G (multiplicatively written) of prime order t with generator g. The secret key is a scalar x ∈ Z * t and the pseudo-random function is defined by:

V x : {1, . . . , d} -→ G m -→ V x (m) = g 1 x+m if x + m = 0 mod t and 1 G otherwise.
The Dodis-Yampolskiy pseudo-random function family has found numerous applications in cryptography (e.g., for compact e-cash [START_REF] Camenisch | Compact e-cash[END_REF] or anonymous authentication [CHK + 06]). Dodis and Yampolskiy showed that their construction has some very attractive security properties, provided that some assumption about the hardness of breaking the so-called Decision Diffie-Hellman Inversion problem holds in G [START_REF] Dodis | A verifiable random function with short proofs and keys[END_REF]. This assumption is non-standard and Cheon [START_REF] Cheon | Discrete logarithm problems with auxiliary inputs[END_REF] proved that it is stronger than the classical discrete logarithm assumption in G.

In practice, two interesting choices for the group G are a subgroup of the multiplicative group of any finite field (in particular, for the so-called verifiable Dodis-Yampolskiy pseudo-random function in groups equipped with a bilinear map [START_REF] Dodis | A verifiable random function with short proofs and keys[END_REF]) or a subgroup of points of an elliptic curve defined over a prime finite field. Very few results supporting the Decision Diffie-Hellman Inversion assumption hardness were proven in these settings (contrary to the Naor-Reingold pseudo-random function family [START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF] for which numerous results are known, e.g. distribution [START_REF] Ling | On the multidimensional distribution of the Naor-Reingold pseudo-random function[END_REF], linear complexity [START_REF] Gómez | On the linear complexity of the Naor-Reingold sequence[END_REF] and non-linear complexity [START_REF] Banks | Non-linear complexity of the Naor-Reingold pseudo-random function[END_REF]). This paper deals with the distribution of the Dodis-Yampolskiy pseudo-random function over finite fields and over elliptic curves and proves lower bounds on the degree of polynomials which interpolate these functions.

Contributions of the paper. As a first contribution, we prove that for almost all values of parameters, the Dodis-Yampolskiy pseudo-random function produces a uniformly distributed sequence. This simple result is based on some recent bounds on character sums with exponential functions. Shparlinski [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF] has obtained in 2011 an explicit bound for exponential sums with consecutive modular roots over a prime finite field. Ostafe and Shparlinski [START_REF] Ostafe | Twisted exponential sums over points of elliptic curves[END_REF] obtained an analoguous result for exponential sums over multiples of a point on an elliptic curve defined over a prime finite field. Following the method from [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF], we obtain readily a bound for such sums over any extension of a prime finite field (Proposition 1). This new bound allows us to give results on the distribution of the Dodis-Yampolskiy pseudo-random functions over finite fields (Theorem 1). We use the bounds from [START_REF] Ostafe | Twisted exponential sums over points of elliptic curves[END_REF] to give results on the distribution of the Dodis-Yampolskiy pseudo-random functions over elliptic curves (Theorem 2).

In order to break the security of the Dodis-Yampolskiy pseudo-random function, it would be sufficient to have a polynomial over a finite field of low degree which reveals information on the function values. From the known lower bounds on the polynomial interpolation on the discrete logarithm in finite fields and elliptic curves (e.g. [CS00,LW02,KW06])), one can prove that a low-degree univariate polynomial cannot reveal the secret key x when evaluated at V x (m) (for some integer m ∈ {1, . . . , d}) for all x. However, the security of the Dodis-Yampolskiy pseudo-random function would also be broken if such low-degree polynomial revealing a value V x (m ) were proved to exist (for some integer m ∈ {1, . . . , d} \ {m} and many different keys x). Our main contribution is to prove lower bounds on the degree of polynomials interpolating the values of these functions over finite fields (Theorem 3) and elliptic curves (Theorem 4 and Theorem 5). These results can be regarded as first complexity lower bounds on the pseudo-randomness of the Dodis-Yampolskiy function families.

Both contributions are motivated by earlier results of the same flavour on the Naor-Reingold pseudo-random function family.

Auxiliary Results

In this section, we collect some statements about finite fields, exponential sums over finite fields and elliptic curves. We provide explicit upper-bounds for exponential sums with consecutive modular roots over a finite field and for analogous exponential sums over elliptic curves [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF][START_REF] Ostafe | Twisted exponential sums over points of elliptic curves[END_REF]. The bound for exponential sums with consecutive modular roots over a general finite field is easily derived from [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF] and may be of independent interest.

Finite Fields and Exponential Sums

Let p be an odd prime number. We denote F q = F p r the finite field with q = p r elements (r ≥ 1). For an integer t, denote by Z t the residue ring modulo t and by Z * t the group of units of Z t . For an integer m > 0, we put e m (z) = exp(2πiz/m). Let g ∈ F * p r of order t (with t | p r -1), and ψ be a non-trivial character of F p r . For a ∈ F * p r and b ∈ Z t , we define the sum:

S a,b = n∈Z * t ψ(ag 1/n )e t (bn).
Throughout the paper, the notation U V is equivalent to the inequality |U | ≤ cV with some constant c > 0. In the following lemmas, the implied constants in the symbols " " may occasionally depend on the integer parameters k, and are absolute otherwise.

In [START_REF] Bourgain | Distribution of consecutive modular roots of an integer[END_REF] Bourgain and Shparlinski proved, when r = 1, that for any ε > 0, there exists δ > 0 such that for t ≥ p ε , we have the bound S a,b t 1-δ . Shparlinski [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF](Theorem 3.1) gave an explicit form of this result (again when r = 1) for relatively large values of t; in the case t = p 1+o(1) , it takes the form S a,b t 127/128+o(1) . Using Shparlinski's methods, we generalize this bound on S a,b for any r ≥ 1 (see Appendix A for a proof which follows [START_REF] Shparlinski | Exponential sums with consecutive modular roots of an integer[END_REF]):

Proposition 1. For any integers k ≥ 2, ≥ 1 we have for t ≥ q 1/2 (log q) 2 : S a,b ≤ t 1-α k, q β k, +o(1) , where α k, = 1 2(2k+ ) -1 4k and β k, = 1 4(2k+ ) .

Elliptic Curves and Exponential Sums

We will also consider the setting of an elliptic curve E defined over F p (where p is a prime number), that is a rational curve given by the following Weierstrass equation y 2 = x 3 +Ax+B with A, B ∈ F p and 4A 3 +27B 2 = 0. The set E(F p ) of the points of the curve defined over F p (including the special point O at infinity) has a group structure (denoted additively) with an appropriate composition rule where O is the neutral element. Given P a point of the curve E with prime order (with | |E(F p )|), we denote [n]P the scalar multiplication, i.e. in fact the adding of the point P to itself n times (for n ≥ 0).

Let E be an elliptic curve and G ∈ E(F p ) be a point of order t ≥ 1. For a ∈ F * p and b ∈ Z t , we define the sum:

Ŝa,b = n∈Z * t e p aX 1 n G e t (bn),
where X(P ) denotes the abscissa of a point P ∈ E(F p ). In [OS11, Theorem 6], Ostafe and Shparlinski obtained an upper-bound on Ŝa,b (with H(X) = X -1 following the notation from [START_REF] Ostafe | Twisted exponential sums over points of elliptic curves[END_REF]):

Proposition 2 ([OS11],). For any integers k ≥ 2, ≥ 1 we have for t ≥ q 1/2 (log q) 2 : Ŝa,b ≤ t 1-α k, p β k, +o(1)
,

where α k, = 1 2(4k+ ) -1 4k and β k, = 1 4(4k+ ) .

Division Polynomials over Elliptic Curves

In this section, we recall some basic facts on division polynomials of elliptic curves (see [START_REF] Washington | Elliptic curves. Number theory and cryptography[END_REF][START_REF] Blake | Elliptic curves in cryptography[END_REF]). The division polynomials

ψ m (X, Y ) ∈ F p [X, Y ]/(Y 2 -X 3 - AX -B)
, m ≥ 0, are recursively defined by:

ψ 0 = 0 ψ 1 = 1 ψ 2 = 2Y ψ 3 = 3X 4 + 6AX 2 + 12BX -A 2 ψ 4 = 4Y (X 6 + 5AX 4 + 20BX 3 -5A 2 X 2 -4ABX -8B 2 -A 3 ) ψ 2m+1 = ψ m + 2ψ 3 m -ψ m-1 ψ 3 m+1 , m ≥ 2 ψ 2m = ψ m (ψ m+2 ψ 2 m-1 -ψ m-2 ψ 2 m+1 )/ψ 2 , m ≥ 3, where ψ m is an abbreviation for ψ m (X, Y ). If m is odd, then ψ m (X, Y ) ∈ F p [X] is univariate and if m is even then ψ m (X, Y ) ∈ 2Y F p [X]. Therefore, we have ψ 2 m (X, Y ) ∈ F p [X] and ψ m-1 (X, Y )ψ m+1 (X, Y ) ∈ F p [X].
In particular, we may write ψ 2m+1 (X) and ψ 2 m (X). The division polynomials can be used to calculate multiples of a point on the elliptic curve E. Let P = (x, y) ∈ E with P = O, then the abscissa of [m]P is given by θ m (x)/ψ 2 m (x) where θ m (X) = Xψ 2 m -ψ m-1 ψ m+1 . The zeros of the denominator ψ 2 m (X) are exactly the first coordinates of the non-trivial m-torsion points, i.e, the points

Q = (x, y) ∈ F p 2 \ {O} on E with [m]Q = O. Note, that
these points occur in pairs Q = (x, y) and -Q = (x, -y), which coincide only if 2Q = O, i.e, if x is a zero of ψ 2 2 (X). We recall that the group of m-torsion points E[m], for an elliptic curve E defined over a field of characteristic p, is isomorphic to (Z/mZ) 2 if p m and to a proper subgroup of (Z/mZ)

2 if p | m. If m is a power of p then E[m] is either isomorphic to (Z/mZ) or to {O}. Accordingly, the degree of ψ 2 m (X) is m 2 -1 if p m
and strictly less than m 2 -1 otherwise. In particular, for p = 2 and m a power of 2 we have deg(

ψ 2 m ) = m -1 if E is not supersingular and deg(ψ 2 m ) = 0 otherwise. By induction one can show that θ m (X) ∈ F p [X] is monic of degree m 2 .

Distribution of the Dodis-Yampolskiy Pseudo-Random Functions

For a real z, we use the notation e(z) = exp(2πiz). For a sequence of N points Γ = (γ 0,n , . . . , γ s-1,n ) n∈{1,...,N } in the s-dimensional unit cube, we denote its discrepancy by D Γ :

D Γ = sup B⊆[0,1) s T Γ (B) N -|B| ,
where T Γ (B) denotes the number of points of the sequence Γ in a box

B (i.e. a polyhedron [α 0 , β 0 )ו • •×[α s-1 , β s-1 ) ⊆ [0, 1) s ) of volume
|B| and the supremum is taken over all such boxes. For an integer vector a = (a 0 , . . . , a s-1 ) ∈ Z s , we define |a| = max ν∈{0,...,s-1} |a ν | and r(a) = s-1 ν=0 max{|a ν |, 1}. In order to show that a sequence Γ is uniformly distributed, we need to show that its discrepancy D Γ is very small (i.e. tends to 0). The following lemma is our main tool for finding non-trivial upper bound for the discrepancy. It is a slightly weaker form of the Koksma-Szüsz inequality [DT97, Theorem 1.21]. The implied constant in the symbol " " depends on the integer s.

Lemma 1. For any integer L > 1 and any sequence Γ of N points, we have

D Γ 1 L + 1 N 0<|a|<L 1 r(a) N n=1 e s-1 ν=0 a ν γ ν,n ,
where the sum is taken over all integer vectors a ∈ Z s with 0 < |a| < L.

We also need the well-known orthogonality relation: (2)

Distribution of the Dodis-Yampolskiy Pseudo-Random Function over Finite Fields

Let q = p r be a prime power for some integer r > 1, let g ∈ F * q be an element of prime order t. For x ∈ Z t and d ≤ t, we denote by D x (d) the discrepancy of the points (

V x,1 (n)/p, . . . , V x,r (n)/p) for 1 ≤ n ≤ d, where V x (n) = g 1 x+n ∈ F p r and V x (n) = V x,1 (n)β 1 + • • • + V x,r (
n)β r , where {β 1 , . . . , β r } is an ordered basis of F p r over F p . We identify F p with the set of integers {0, 1, . . . , p -1}.

Theorem 1. For any x ∈ Z t , any integers k ≥ 2, ≥ 1 and 1 ≤ d ≤ t, we have:

D x (d) ≤ t 1-α k,l q β k,l +o(1) d ,
where

α k,l = 1 2(2k+l) -1 4kl
and β k,l = 1 4(2k+l) . Proof. From Lemma 1, we derive

D x (d) 1 p + 1 d 0<|a|<p 1 r(a) d n=1 e p   r j=1 a j V x,j (n)   ,
where a = (a 1 , . . . , a r ). Set

S d (a) = d n=1 e p ( r j=1 a j V x,j (n)).
Let {δ 1 , . . . , δ r } be the dual basis of the given ordered basis {β 1 , . . . , β r }. For j ∈ {1, . . . , r} and n ∈ {1, . . . , d}, we have V x,j (n) = Tr(δ j V x (n)), where Tr denotes the trace of F p r over F p (namely Tr(x) = x+x p +• • •+x p r-1 ). Therefore,

S d (a) = d n=1 e p   Tr   r j=1 a j δ j V x (n)     = d n=1 e p (Tr(α a V x (n)))
where α a = r j=1 a j δ j ∈ F p r . Let χ be defined by χ(z) = e p (Tr(z)). Then χ is a non trivial additive character on F p r . Since there exists j ∈ {1, . . . , r} such that a j = 0, then α a = 0. We have:

S d (a) = d n=1 χ(α a V x (n)) with α a = 0.
We have

S d (a) = x+d n=x+1 n∈Z * t χ(α a g 1/n ) = 1 t n∈Z * t χ(α a g 1/n ) × t-1 c=0 x+d v=x+1 v∈Z * t e t (c(n -v)) = 1 t t-1 c=0   n∈Z * t χ α a g 1/n e t (cn)   × x+d v=x+1 v∈Z * t e t (-cv).
By applying Proposition 1 and (2), we obtain 1) .

S d (a) ≤ 1 t t-1 c=0 x+d v=x+1 v∈Z * t e t (-cv) × t 1-α k, q β k, +o(1) ≤ t 1-α k, q β k, +o (
By applying this bound to D x (d), we have

D x (d) 1 p + t 1-α k,l q β k, +o(1) d 0<|a|<p 1 r(a) 1 p + t 1-α k, q β k, +o(1) d log r p ≤ t 1-α k, q β k, +o(1) d
With the choice k = 4, l = 8, t = q 1+o(1) and d = t 127 128 +ε , we obtain D x (d) ≤ p r(-ε+o(1)) = q -ε+o(1) .

Distribution of the Dodis-Yampolskiy Pseudo-Random Function over Elliptic Curves

Let E : y 2 = x 3 + Ax + B, be an elliptic curve over F p . For P ∈ E(F p ) of prime order t, for x ∈ Z t , and for 1 ≤ d ≤ t we denote by D x (d) the discrepancy of the points (X(V x (n))/p) for n ∈ {1, . . . , d} where V x (n) = 1 x+n P ∈ E(F p ). We obtain the following theorem.

Theorem 2. For any x ∈ Z t , any integers k ≥ 2, l ≥ 1 and 1 ≤ d ≤ t, we have:

D x (d) ≤ t 1-α k, p β k, +o (1) d
S d (a) ≤ 1 t t-1 c=0 x+d v=x+1 v∈Z * t e t (-cv) × t 1-α k, p β k, +o(1) ≤ t 1-α k, p β k, +o(1)
By applying this bound to D x (d), we have

D x (d) 1 p + t 1-α k, p β k, +o(1) × 1 d 0<|a|<p 1 |a| 1 p + t 1-α k, p β k,l +o(1) × 1 d log p ≤ t 1-α k, p β k, +o(1) × 1 d
With the choice k = 4, = 16, t = p 1+o(1) and d = t

Polynomial Interpolation of the Dodis-Yampolskiy

Pseudo-Random Function over Finite Fields

Let g ∈ F * p r for some integer r > 1, be an element of prime order t | p r -1. In this section, we prove a lower bound on the degree of univariate polynomial interpolation of the Dodis-Yampolskiy pseudo-random function over finite fields. We consider polynomials that interpolates values of the Dodis-Yampolskiy pseudo-random function for a fixed secret key x ∈ F * t . The values considered are evaluation of the function at integers n ∈ {1, . . . , d} for some integer 1 ≤ d ≤ t and translates of these values by some fixed constants λ ∈ N. This setting is interesting for applications in cryptography [CHL05,CHK + 06]. Note that if one value n is larger than d then, the Dodis-Yampolskiy function is not necessarily defined at n + λ. In the following, we consider simple sets where all translates belong to the function domain but our method can be adapted to other settings. Theorem 3. Let λ be a fixed integer and let A ⊆ {1, . . . , d}. For some

x ∈ F * t , let F (X) ∈ F p [X] be such that F (g 1 x+n ) = g 1 x+n+λ for all n ∈ A. We have deg(F ) ≥ t -2s 4 and w(F ) ≥ t 4s 1/2
where A = t -s.

In the proof of Theorem 3, we use the following lemma [START_REF] Lange | Polynomial interpolation of the elliptic curve and XTR discrete logarithm[END_REF] where the weight w(F ) (or sparsity) of a polynomial F (X) ∈ F p [X] is the number of its non-zero coefficients.

Lemma 2 ([LW02]

). Let γ ∈ F p be an element of order and F (X) ∈ F p [X] be a non-zero polynomial of degree at most -1 with at least b zeros of the form γ x with 0 ≤ x ≤ -1. The weight of F (X) satisfies w(F ) ≥ /( -b).

Proof (Theorem 3). Let R = {(n + x) mod t : n ∈ A}. Then R ⊆ F t and R = t -s. We have F (g 1 n ) = g 1 n+λ for all n ∈ R. Noticing that 1 n+λ = 1 λ (1 -1 λ n +1 ), we obtain F (g u λ ) = g 1 λ (1-1 u+1 ) for all u = λ n , n ∈ R. Let R 0 = {u = λ n : n ∈ R \ {0}} and T = {u ∈ R 0 : 2u + 1 ∈ R 0 }. Since R 0 = t -s, we have T ≥ t -2s. Then F g 2u+1 λ = g 1 λ (1-1 2u+2 ) = g 1 λ ( 1 2 + 1 2 (1-1 u+1 )) = g 1 2λ × g 1 2λ (1-1 u+1 )
for all u ∈ T . We thus have

F 2 g 2u+1 λ = g 1 λ × g 1 λ (1-1 u+1 ) = g 1 λ × F (g u λ ), for all u ∈ T . Let H(X) = F 2 (g 1 λ X 2 ) -g 1 λ F (X).
The polynomial H(X) is a non-zero polynomial and deg(H) ≤ 4 deg(F ). Since H(X) has at least T = t -2s zeros, we have 4 deg(F ) ≥ t -2s and then deg(F ) ≥ t-2s 4 . Moreover, if deg(H) ≤ t -1, since the zeros of H are the powers of g 1 λ , then we have by Lemma 2, w(H) ≥ t/(t -(t -2s)), and since w(H) ≤ 2(w(F )) 2 , it follows that w(F ) ≥ (t/4s) 1/2 . Remark 1. Theorem 3 is non-trivial only when A > t/2. It remains an open question to obtain non-trivial lowers bounds for smaller sets A.

Polynomial Interpolation of the Dodis-Yampolskiy

Pseudo-Random Function over Elliptic Curves

In this section, p is an odd prime number, E is an elliptic curve defined over F p and P is a point of the curve E(F p ) with prime order t. We prove lower bounds on the degree of polynomial interpolation of the Dodis-Yampolskiy pseudo-random function over elliptic curves defined by V x (n) = X 1 x+n P for a secret key x ∈ F * t and an integer n ∈ {1, . . . , d}, with 1 ≤ d ≤ t.

Theorem 4. Let S ⊆ {1, . . . , d}, S = t -s. We suppose X(P ) = 0. For some

x ∈ F * t , let F (X) ∈ F p [X] be such that ψ 2 2 (F (X(P ))) = 0 and F (V x (n)) = V x (n + 1) for all n ∈ S. We have deg(F ) ≥ t -2s 176 . Proof. Let R = {(n + x) mod t : n ∈ S} ⊆ F t . We have R = t -s. Let us denote x k = X([k]P ) and R 0 = { 1 n : n ∈ R}, then we have F (x u ) = x 1-1 1+u for all u ∈ R 0 . We consider the set T = {u ∈ R 0 : 2u + 1 ∈ R 0 }, then T ≥ t -2s.
For all u ∈ T , we have:

F (x 2u+1 ) = x 1-1 2(u+1) = x 1/2+1/2(1-1/(u+1))
and F (x u ) = x 1-1/(u+1) (3) Using division polynomials (see Section 2.3), we can write:

x 1+1-1 (u+1) = θ 2 (F (x 2u+1 )) ψ 2 2 (F (x 2u+1 )) (4)
Using the elliptic curve addition law, we have

x 1+α = a(x α ) -2y 1 y α (x α -x 1 ) 2 where a(X) = x 1 X 2 + (x 2 1 + A)X + Ax 1 + 2B,
and for any polynomial G of degree m ≥ 1, we have

G(x 1+α ) = u(x α ) -y α v(x α ) (x α -x 1 ) 2m and lc(u) = G(x 1 )
with uniquely determined polynomials u(X) and v(X) with deg(u) ≤ 2m (deg(u) = 2m if G(x 1 ) = 0) and deg(v) ≤ 2m -2 and where lc(u) is the leading coefficient of the polynomial u(X). Since F (x u ) = x 1-1 u+1 , we can rewrite (4) as:

a(F (x u )) -y 1 y 1-1 u+1 (F (x u ) -x 1 ) 2 = θ 2 (F (x 2u+1 )) ψ 2 2 (F (x 2u+1 ))
.

Since the point (x 1-1 u+1 , y 1-1 u+1 ) ∈ E(F p ) and F (x u ) = x 1-1 u+1 , the poly- nomial y 2 1 (F (x u ) 3 + A • F (x u ) + B)ψ 4 2 (F (x 2u+1 )) is equal to the polynomial [(F (x u ) -x 1 ) 2 θ 2 (F (x 2u+1 )) -a(F (x u ))ψ 2 2 (F (x 2u+1
))] 2 . We thus obtain

y 2 1 (F (x u ) 3 + A • F (x u ) + B) × p 1 (x 2u ) -y 2u p 2 (x 2u ) (x 2u -x 1 ) 12d0 = Q(x u , x 2u , y 2u ),
where d 0 = deg(F ) and Q(x u , x 2u , y 2u ) denotes a polynomial of the form

(F (x u ) -x 1 ) 2 p 3 (x 2u ) -y 2u p 4 (x 2u ) (x 2u -x 1 ) 8d0 -a(F (x u )) p 5 (x 2u ) -y 2u p 6 (x 2u ) (x 2u -x 1 ) 6d0 2 such that deg(p 1 ) ≤ 6d 0 , deg(p 2 ) ≤ 6d 0 -2, deg(p 3 ) ≤ 4d 0 , deg(p 4 ) ≤ 4d 0 -2, deg(p 5
) ≤ 3d 0 and deg(p 6 ) ≤ 3d 0 -2. We obtain:

y 2 1 (F (x u ) 3 + AF (x u ) + B)(x 2u -x 1 ) 4d0 (p 1 (x 2u ) -y 2u p 2 (x 2u )) = P (x u , x 2u , y 2u ), where P (x u , x 2u , y 2u ) = [(F (x u ) -x 1 ) 2 p 3 (x 2u ) -a(F (x u ))(x 2u -x 1 ) 2d0 p 5 (x 2u ) -y 2u ((F (x u ) -x 1 ) 2 p 4 (x 2u ) -a(F (x u ))(x 2u -x 1 ) 2d0 p 6 (x 2u ))] 2 .
We then proceed as previously by trying to eliminate y 2u . We obtain an expression in function of x u and x 2u and we replace x 2u by θ2(xu) ψ 2 2 (xu) . We finally obtain a rational function in x u of the form:

Q(x u ) ψ 40d0 2 (x u ) = 0, where Q(X) ∈ F p [X] and deg(Q) ≤ 88d 0 .
A Proof of Proposition 1

The classical Weil bound for exponential sums can be found in [START_REF] Weil | On some exponential sums[END_REF][START_REF] Niederreiter | Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators[END_REF].

Lemma 4. Let F (x) be a non constant polynomial in F q [x] such that F (x) = h(x) p -h(x) for any h(x) ∈ F q (x). We have x∈Fq ψ(F (x)) ≤ (deg(F ) -1)q 1/2
We deduce the following simple lemma: Proof. Let s = (q -1)/t. We have g = θ s , where θ is a primitive root in F q and

t n=1 ψ υ i=1 a i g rin = t n=1 ψ υ i=1 a i θ srin = 1 s q-1 n=1 ψ υ i=1 a i θ srin = 1 s   x∈Fq ψ υ i=1 a i x sri -1  
Applying Lemma 4, we obtain : max (a1,...,aυ)∈F υ p r (a1,...,aυ) =(0,...,0)

t n=1 ψ υ i=1 a i g rin ≤ 1 s ((Rs -1)q 1/2 + 1) ≤ Rq 1/2 .
Proof (Proposition 1). For any integer k ≥ 2, we have

S a,b k = n1,...,n k ∈Z * t ψ   a k j=1 g 1/nj   e t   b k j=1 n j   .
For m ∈ Z t , we collect together the terms with

n 1 + • • • + n k ≡ m mod t, getting: |S a,b | k ≤ m∈Zt n1,...,n k ∈Z * t n1+•••+n k ≡m mod t ψ   a k j=1 g 1/nj   .
By the Cauchy inequality, we can upper-bound

|S a,b | 2k by t m∈Zt n1,...,n k ∈Z * t n1+•••+n k ≡m mod t ψ   a k j=1 g 1/nj   2 = t (n1,...,n 2k )∈N k ψ   a 2k j=1 (-1) j g 1/nj  
where the outside summation is taken over the set of vectors

N k = {(n 1 , . . . , n 2k ) ∈ (Z * t ) 2k : n 1 + • • • + n 2k-1 ≡ n 2 + n 4 + • • • + n 2k mod t)}.
One can see that for any m ∈ N with gcd(m, t) = 1, we have The number w(t) of prime divisors of t satisfies w(t) ≤ (1+o(1))(log t)/(log log t) (which can be seen from the trivial inequality w(t)! ≤ t and the Stirling formula). By the prime number theorem, we have (since Q ≥ 2 log t):

Q ≥ (1 + o(1)) Q log Q -(1 + o(1)) log t log(log t) ≥ 0.5 Q log Q ,
provided that t is large enough. We have N k ≤ t 2k-1 . Using the Hölder inequality and then extending the region of summation, we obtain that for any integer ≥ 1, we have: .

|S a,b | 4k ≤ t 2 Q 2 ( N k ) 2 -
For O( Q )=O(Q log -Q) tuples (m 1 , . . . , m 2 ) ∈ Q 2 such that the tuple of the elements on the odd positions (m 1 , . . . , m 2 -1 ) is a permutation of the elements on the even positions (m 2 , . . . , m 2 ), we estimate the inner sum trivially as t.

For the remaining O(( Q) 2 ) = O(Q 2 (log Q) -2 ) tuples, we use the bound of Lemma 5. Therefore,

|S a,b | 4k t 4k -2k+1 log 2 Q Q 2l (Q log -Qt 2k + Q 2 log -2 Q(Qq 1/2 ) 2k ) = t 4k -2k+1 (Q -log Qt 2k + Q 2k q k ).
Taking Q = 2t 2k/(2k+ ) q -k/(2k+ ) (log q) /(2k+ ) and if t ≥ q 1/2 (log q) 2 , one can see that Q ≥ 2 log t and we obtain |S a,b | 4k t 4k -(2k -2k-)/(2k+ ) q k /(2k+ ) (log q) /(2k+ )

and the result follows.

  the inequality [[IK04], Bound (8.6)] (which holds for any integers m and M with 1 ≤ M ≤ m):

  255 256 +ε , we obtain D x (d) p -ε+o(1) .

Lemma 5 .a

 5 For any pairwise distinct positive integers 1 ≤ r 1 , . . . , r υ ≤ R, we have max (a1,...,aυ)∈F υ p r (a1,...,aυ) =(0,...,0) i g rin ≤ Rq 1/2 .

  Let us fix some parameter Q with Q ≥ 2 log t. Let Q be the set of primes m ≤ Q with gcd(m, t) = 1. Averaging over all m ∈ Q, we obtain|S a,b | 2k ≤ t Q m∈Q (n1,...,n 2k )∈N k

Acknowledgments. The authors would like to thank the reviewers for their detailed comments and suggestions for the manuscript. The authors were supported in part by the French ANR JCJC ROMAnTIC project (ANR-12-JS02-0004) and by the Simons foundation Pole PRMAIS.

Claim. Q(X) = 0 if ψ 2 2 (F (x 1 )) = 0 and x 1 = 0 Proof (Claim). We have deg(P 5 ) = 3d 0 iff ψ 2 2 (F (x 1 )) = 0. If deg(P 5 ) = 3d 0 , One can then verify that the leading coefficient of Q is the leading coefficient of the numerator of the rational function obtained from [(F (x u ) -x 1 ) 2 p 3 (x 2u )a(F (x u ))(x 2u -x 1 ) 2d0 p 5 (x 2u )] 4 after replacing x 2u by θ2(xu)

is a non-zero polynomial with at least T /2 different zeros. We thus have 88d 0 ≥ (t -2s)/2 and the claimed result.

The condition X(P ) = 0 in the statement of Theorem 4 holds obviously for almost all point P . The lower bound then holds if the group order E(F p ) is odd since in this case, the technical condition ψ 2 2 (F (X(P ))) = 0 is always satisfied. However, we obtain a weaker lower bound for the polynomial degree which holds for every curve E.

In the proof of Theorem 5, we use the following simple lemma:

Then there exists α ∈ F p such that ψ 2 2 (F (α)) = 0 and ψ 2 2 (α) = 0. Proof. There are exactly three distinct zeros α 1 , α 2 , α 3 ∈ F p of ψ 2 2 (X). For all index i ∈ {1, 2, 3}, there exists at least one β i ∈ F p such that F (β i ) = α i , because F is not a constant polynomial. Since for all i, j ∈ {1, 2, 3}, i = j, we have α i = α j , then the system F (X) = α i and F (X) = α j has no solution. It follows that the polynomial ψ 2 2 (F (X)) has at least three different zeros. Let d denote the degree of F and let us suppose that there does not exist α ∈ F p such that ψ 2 2 (F (α)) = 0 and ψ 2 2 (α) = 0. Then we have that ψ 2 2 (F (X)) has exactly three zeros which are the zeros of ψ 2 2 (X). If d = 1, then it will imply that F (X) = X which is impossible. If d ≥ 2, for all i ∈ {1, 2, 3}, the equation F (X) = α i has exactly one solution γ i of multiplicity d which is one of {α 1 , α 2 , α 3 }. Then γ 1 and γ 2 are the zeros of the (d -1)-derivative of F (X) which is of degree 1 and this is impossible because γ 1 = γ 2 . Hence in all cases, we obtain a contradiction. So there exists α ∈ F p such that:

for all n ∈ R. Denoting x k = X([k]P ) = X([k mod t]P ) and considering the set T = {n ∈ R/n/2, n + 1 ∈ R}, we have

, hence we have

, for all n ∈ T.

Finally, we consider the polynomial

.

The polynomial H(X) has at least T /2 zeros. We have F (F (X)) = X and by Lemma 3, it will imply that there exists α ∈ F p such that ψ 2 2 (F (F (α))) = 0 and ψ 2 2 (α) = 0. Hence, we have H(α) = -θ 2 (F (F (α)))ψ 2d0 2 (α) = 0, since θ 2 (X) and ψ 2 2 (X) have no common zeros. Therefore, H(X) is a non-zero polynomial and deg(H) ≤ 9d 2 0 . Then we get that 9d 2 0 ≥ R/2 and the result follows.

Conclusion

We studied the distribution of the Dodis-Yampolskiy pseudo-random function values over finite fields and over elliptic curves. We also proved lower bounds on the degree of polynomials interpolating the values of these functions in this two settings of practical interest. As future works, it would be interesting to study the distribution of k-tuples (V x (m), . . . , V x (m + k)) m and to study the linear complexity and minimal polynomials of the sequence generated by the Dodis-Yampolskiy functions over finite fields and over elliptic curves.