Thierry Mefenza
email: thierry.mefenza-nountu@u-paris2.fr

Damien Vergnaud
email: damien.vergnaud@lip6.fr

Cryptanalysis of Server-Aided RSA Protocols with Private-Key Splitting

Keywords: RSA, Exponentiation outsourcing, Lattice-based cryptanalysis, Coppersmith's methods, RSA-S1, RSA-S2

come

INTRODUCTION

Cryptographic operations are performed everywhere, from standard laptop to smart cards. The computational resources can be very limited on certain devices (like radio-frequency identification tags), and it becomes very natural, as most of the devices are online or directly connected to a powerful device (like a SIM card in a smart phone) to securely delegate some sensitive and costly operations to a device capable of carrying out cryptographic algorithms. Outsourcing cryptographic computations is a classical problem which was formalized in [START_REF] Hohenberger | How to securely outsource cryptographic computations[END_REF] (with protocols to outsource the computation of group exponentiation for instance).

Recently, Chevalier, Laguillaumie and Vergnaud [START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF] provided simple constructions for outsourcing group exponentiations in different settings (e.g. public/secret, fixed/variable bases and public/secret exponents) in groups of known prime order. They showed that their constructions are essentially optimal in terms of operations in the underlying group. Their constructions can be used in unknown order groups but it is not clear whether they are optimal in this context. In this paper, we analyze the security and the efficiency of delegation protocols for RSA exponentiations when the secret exponent is splitted using some algebraic decomposition.

Related Work

In the last 30 years, the question of how a computationally limited device may outsource group exponentiation to another, potentially malicious, but much more computationally powerful device has been a very active research topic (e.g. [START_REF] Matsumoto | Speeding up secret computations with insecure auxiliary devices[END_REF][START_REF] Laih | Two efficient server-aided secret computation protocols based on the addition sequence[END_REF][START_REF] Béguin | Fast serveraided RSA signatures secure against active attacks[END_REF][START_REF] Lim | Security and performance of server-aided RSA computation protocols[END_REF][START_REF] Castelluccia | Improving secure server performance by re-balancing SSL/TLS handshakes[END_REF][START_REF] Chen | New algorithms for secure outsourcing of modular exponentiations[END_REF][START_REF] Wang | Securely outsourcing exponentiations with single untrusted program for cloud storage[END_REF][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF]). Many solutions have been proposed and then cryptanalyzed in follow-up papers (e.g. [START_REF] Nguyen | On the insecurity of a server-aided RSA protocol[END_REF][START_REF] Merkle | Multi-round passive attacks on serveraided RSA protocols[END_REF][START_REF] Pfitzmann | Attacks on protocols for server-aided RSA computation[END_REF][START_REF] Jakobsson | Secure serveraided signature generation[END_REF][START_REF] Merkle | On the security of server-aided RSA protocols[END_REF][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF]).

In 2005, Hohenberger and Lysyanskaya [START_REF] Hohenberger | How to securely outsource cryptographic computations[END_REF] proposed a formal security definition for securely outsourcing computations. They showed how to securely outsource group exponentiation to two, possibly dishonest, servers that are physically separated (and do not communicate). Their protocol achieves security as long as one of them is honest (even if the computationally limited device does not know which one). In this paper, since this separation of the two servers is actually a strong assumption, we consider delegation to a single computationally stronger server.

In [START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF], Chevalier et al. proposed a taxonomy of exponentiation delegation protocols that covers all the practical situations : the group elements can be secret or public, variable or fixed, the exponents can be secret or public, and the result of the exponentiation can also be either public or secret. In this paper, we consider the main use case in the setting of RSA exponentiation: a client wants to delegate the computation of a signature

The Computer Journal, Vol. ??, No. ??, ???? given a public key (N, e), a public message (or hash value of a message) m and the secret signing exponent d. By outsourcing some exponentiations to a server, the delegation protocol outputs a (public) signature σ = m d mod N .

In all the proposed protocols, the basic idea is to let the server perform the main part of the computation, without giving it enough information to reconstruct the secret exponent d. Most proposed protocols are variants of two protocols (named RSA-S1 and RSA-S2) that were proposed by Matsumoto, Kato and Imai in 1988 [START_REF] Matsumoto | Speeding up secret computations with insecure auxiliary devices[END_REF]. Both schemes use a random linear decomposition of the RSA private exponent d. The goal of the present paper is to present attacks against these protocols for RSA exponentiations.

Our Contributions

Our contributions are manyfold:

• Analysis of protocols outsourcing a single exponentiation. As a first contribution, we analyze the delegation protocols in which the client outsources a single RSA exponentiation to the server. Such schemes generically decompose the secret exponent d among one of the following three sharing schemes: additive splitting, multiplicative splitting or mixed splitting. The security of the first scheme is closely related to the well-known partial-key exposure (e.g. see [START_REF] Zheng | Partial key exposure on rsa with private exponets larger than n[END_REF][START_REF] Aono | A new lattice construction for partial key exposure attack for RSA[END_REF][START_REF] Blömer | New partial key exposure attacks on RSA[END_REF][START_REF] Ernst | Partial key exposure attacks on RSA up to full size exponents[END_REF]). We propose attacks for the two other paradigms that makes use of ideas proposed by Boneh and Durfee in their seminal paper on the small secret exponent cryptanalysis of RSA [START_REF] Boneh | Cryptanalysis of RSA with private key d less than N 0.292[END_REF]. To counter active attacks against delegation protocols, Pfitzmann and Waidner [START_REF] Pfitzmann | Attacks on protocols for server-aided RSA computation[END_REF] suggested to renew the decomposition of the secret key after each signature generation in Server-Aided RSA protocols. We also present improved attacks against these serveraided protocols when the adversary is allowed to observe several executions of the protocol (with independent random decomposition). • Cryptanalysis of RSA-S1. In 2000, Merkle proposed an efficient lattice-based multi-round passive attack against RSA-S1. Merkle's attack is probabilistic and its success probability decreases rapidly if the linear decomposition of the secret exponent is limited to small dimensions. Nguyen and Shparlinski [START_REF] Nguyen | On the insecurity of a server-aided RSA protocol[END_REF] proposed one year later a single-round passive attack on the RSA-S1 Server-Aided protocol which recovers the factorization of the RSA modulus when a small public exponent e is used (namely e < N 1/2 ). We combine these two approaches and we propose a (heuristic) latticebased attack that works even if the public exponent is large and the linear decomposition of d is limited to small dimensions. We also propose and analyze a variant of the protocol RSA-S1 which is interesting for clients with limited memory. In this setting, the variant achieves better efficiency for the same security level. We propose a simple exponential-time algorithm that break all these security parameters using multi-evaluation of polynomials. In [START_REF] Nguyen | On the insecurity of a server-aided RSA protocol[END_REF], Nguyen and Shparlinski stated in their paper that: "Interestingly, it seems that the lattice-based attacks . . . do not apply to the RSA-S2 protocol." We also present two latticebased attacks against RSA-S2 that break most parameters proposed by Castelluccia et al. (even if one updates them in order to prevent our meet-inthe-middle attack).

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

PRELIMINARIES

Lattices

A lattice L is a discrete additive subgroup of a Euclidean space. If L is a lattice in the n-dimensional space R n , then we can also define L as the set of all linear integer combinations of linearly independent vectors b 1 , . . . , b k ∈ R n and:

L = { k j=1 a j b j : a j ∈ Z}.
The set B = {b 1 , . . . , b k } is called a basis of the lattice L and the integer k its dimension or rank. A lattice

L ⊂ R n has full rank if its dimension equals n. If B = {b 1 , . . . , b k } ⊂ R n is
a basis of a lattice L, then B can be represented by the matrix M with k rows and n columns having the basis vectors as rows and its determinant denoted det(L) is defined to be det(M M T ) 1/2 , where M T is the transpose matrix of M . If L is full rank, then its determinant is simply | det(M )|. The following lemma [START_REF] Minkowski | Geometrie der Zahlen[END_REF] relates the norm of the shortest vector in a lattice to its determinant. Lemma 2.1. (Minkowski) Let L be a lattice of dimension ω. there exists a non-zero vector v with Euclidean norm:

v √ ω det(L) 1/ω .
In 1982, Lenstra, Lenstra and Lovász introduced the famous LLL algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] which on input an arbitrary basis of a lattice L outputs in polynomial time a socalled reduced basis of L made of "short" vectors. The basis vectors of an LLL-reduced basis satisfies the following property. Lemma 2.2. ( [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF]) Let L be an integer lattice of dimension ω generated by k vectors with Euclidean norm at most B . In polynomial time in ω, k and log B, the LLL algorithm given as input this basis of L outputs a reduced basis of L formed by vectors v i , 1 i ω that satisfy:

v 1 v 2 . . . v i 2 ω(ω-1) 4(ω+1-i) det(L) 1 ω+1-i .
In particular, for i = 1, the LLL algorithm outputs a vector v 1 with norm v 1 2

ω-1 4

det(L)

1 ω . This approximation factor for the shortest vector of the reduced basis is exponentially large in the lattice dimension ω compared to the bound given by Lemma 2.1. However, in the following, we will often use the LLL algorithm as a "short vector oracle" (since this approximation factor translates in a constant factor for the upper-bound on the size of the roots in Coppersmith methods).

The Gaussian heuristic predicts the number of lattice points (for a random lattice) inside a measurable body and applied to Euclidean balls, it leads to the prediction that the length of the shortest vector in random lattice is equal to the bound given by Lemma 2.1 (up to some constant multiplicative factor). In the following, we will use the heuristic that if the norm of a specific vector is significantly smaller than the bound given by Lemma 2.1, then it is likely the shortest vector in L and that we can recover it (in polynomial time) using the LLL algorithm. We will apply this heuristic even if our constructed lattices are not random but it will be validated experimentally.

Coppersmith's Methods

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

Problem definition.

Let f 1 (y 1 , . . . , y n ), . . . , f s (y 1 , . . . , y n ) with indeterminates y i , for i ∈ {1, . . . , n} be irreducible multivariate polynomials defined over Z, having a root (x 1 , . . . , x n ) modulo an integer K namely f i (x 1 , . . . , x n ) ≡ 0 mod K. Our goal is to recover the desired root (x 1 , . . . , x n ) in polynomial time.

To do so, we create n polynomials (see below) hi (y 1 , . . . , y n ), i ∈ {1, . . . , n} having as root (x 1 , . . . , x n ) over the integers.

We hope that the n created polynomials define an algebraic variety of dimension 0 in order to recover the desired root in polynomial time.

This problem is generally intractable but becomes solvable in polynomial time (under some conditions) if the absolute value of each component of the root (x 1 , . . . , x n ) is upper-bounded by some values (X 1 , . . . , X n ) that depends on K and the degree of the polynomials f 1 , . . . , f s .

Polynomials collection.

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

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

Lattice construction.

In a second step, one denotes as M the set of monomials appearing in collection of polynomials P, and one writes the polynomials fi (y 1 X 1 , . . . , y n X n ) for i ∈ {1, . . . , r} as a vector b i ∈ (Z) ω , where ω = M. Namely If we put M = {m 1 , . . . , m ω }, where m i < m i+1 for a defined order < on M, for i ∈ {1, . . . , r} we can write fi (y 1 X 1 , . . . , y n X n ) = ω j=1 c ij m j for some coefficients c ij ∈ Z and then b i = (c i1 , . . . , c iω ) ∈ (Z) ω . Conversely, one can write a vector v ∈ (Z) ω as a polynomial f (y 1 X 1 , . . . , y n X n ) ∈ Q[y 1 , . . . , y n ] . One then constructs a lattice L generated by the vectors b 1 , . . . , b r and computes its reduced basis using the LLL algorithm.

Generating new polynomials.

In a third step, one combines Lemma 2.3 below [START_REF] Howgrave-Graham | Finding small roots of univariate modular equations revisited[END_REF] and the Lemma 2.2 to get n polynomials g 1 (y 1 , . . . , y n ),. . . ,g n (y 1 , . . . , y n ) having (x 1 , . . . , x n ) as a root over the integers. Lemma 2.3. (Howgrave-Graham) Let W be some positive integer. Let h(y 1 , . . . , y n ) be a polynomial over Z having at most ω monomials. Suppose that:

1. h(x 1 , . . . , x n ) = 0 mod W for some |x 1 | < X 1 , . . . , |x n | < X n and, 2. h(X 1 y 1 , . . . , X n y n ) W √ ω .
Then h(x 1 , . . . , x n ) = 0 holds over the integers.

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

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

Success Condition.

In our attacks, the number of polynomials in the first step is equal to the number of monomials that appears in the collection, so r = ω = M. In the analysis, we let (as usual in this setting) small terms contribute to an error term ε, and the simplified condition becomes:

det(L) < K mω .
We have no assurance that the n created polynomials are algebraically independent. Under the (heuristic) assumption that they define an algebraic variety of dimension 0, the previous system can be solved (e.g., using elimination techniques such as Gröbner basis) and the desired root recovered in polynomial time. In this paper, we assume that these polynomials define an algebraic variety of dimension 0 and we justify the validity of our attacks by computer experiments even when the dimension is non-zero.

Multi-exponentiation

Algorithm 1 computes the multi-exponentiation

t i=1 g xi i ∈ G,
for g 1 , . . . , g t ∈ G and x 1 , . . . , x t ∈ N (see [START_REF] Möller | Algorithms for multi-exponentiation[END_REF][START_REF] Avanzi | The complexity of certain multiexponentiation techniques in cryptography[END_REF] for details of different multi-exponentiation techniques).

Complexity: The precomputed table contains 2 tt -1 non-trivial entries that require one general multiplication each. The total cost is for the precomputation phase 2 t -t -1 multiplications and (2 t -1)/2 t multiplications on average and squarings. Although many time/memory tradeoffs are possible (e.g. using windows), for efficiency analysis, we consider in the following only delegation protocols that use this algorithm for client exponentiation.

DELEGATION OF A SINGLE MODULAR EXPONENTIATION

We focus in this section on protocols for outsourcing modular exponentiation (in groups of secret order) in which the client outsources only one exponentiation to the server. More precisely, we consider the setting where the client's public key is an RSA modulus N = pq where Algorithm 1 Multi-Exponentiation Algorithm Require: g 1 , . . . , g t ∈ G, x 1 , . . . , x t ∈ N with = max i∈{1,...,t} log x i and x j = -1 i=0 e i,j 2 i ∈ N and e i,j ∈ {0, 1} for i ∈ {0, . . . , -1} and j ∈ {1, . . . , t} Ensure:

g x1 1 • • • g xt t ∈ G for all non-zero t-tuples E = (E 1 , . . . , E t ) ∈ {0, 1} t do g E ← 1 i t ag Ei i £ Precomputation stage end for h ← 1 G for i from -1 to 0 do h ← h 2 E ← (e i,1 , e i,2 , . . . , e i,t ) h ← h • g E £ Multiply h by table entry g E = 1 k t g e i,k i
end for return h p and q are primes which are "balanced" (i.e. p and q are the same bit-size and p, q N 1/2 ) together with a public exponent e such that e N α for some α 0. In the rest of the paper, p and q have approximately the same sizes and p, q N 1/2 simply means that p and q are the same bit-size. Most standard implementations of RSA use very small public exponent such as e ∈ {3, 5, 17, 257, 65537} and the case α 0 is of very strong practical importance. The client's secret key is defined by d = e -1 mod ϕ(N ) where ϕ(N ) = (p -1)(q -1) is the Euler totient function.

The client has to compute c = m d mod N for some variable m ∈ Z * N (which is assumed to be public) and it is allowed to query the server on a single triple (m, r, N ) to get c = m r mod N . Using its knowledge of d and c , the client eventually outputs c. Using only the multiplicative structure of Z N , the client can compute c in essentially three different ways: In order to be computationally efficient for the client, these protocols should use small d 1 and d 2 . However, it is worth noting that the value r can be picked arbitrarily (and in particular it may be larger than ϕ(N )). We present attacks on these three protocols when d 1 and d 2 are too small.

• c = m d1 • c mod N ,

Server-Aided Protocol with Additive Splitting

In the server-aided protocol with additive splitting (see N β and d 1 has to be found. This problem is actually very close to the so-called partial key exposure attacks which have been widely studied (e.g. see for instance [START_REF] Zheng | Partial key exposure on rsa with private exponets larger than n[END_REF][START_REF] Aono | A new lattice construction for partial key exposure attack for RSA[END_REF][START_REF] Blömer | New partial key exposure attacks on RSA[END_REF][START_REF] Ernst | Partial key exposure attacks on RSA up to full size exponents[END_REF][START_REF] Takayasu | Partial key exposure attacks on RSA: Achieving the boneh-durfee bound[END_REF][START_REF] Takayasu | A tool kit for partial key exposure attacks on RSA[END_REF]). We can simply apply the following result due to Joye and Lepoint [START_REF] Zheng | Partial key exposure on rsa with private exponets larger than n[END_REF] which is the best known attack for the partial key exposure with exponent blinding: N δ unknown, then for sufficiently large N , there exists a (heuristic) polynomial-time algorithm that can computes all of d provided that:

δ < α + β -1 for 1 < α + β < 3/2 α+β- √ 4(α+β) 2 -6(α+β) 3 for 3/2 < α + β < 2 Applying Theorem 3.1 with d = d 1 + r N β , β = β 1 +1
, and d 1 N δ , we obtain readily the following result (see also Figure 2):

Corollary 3.1.
There exists a (heuristic) polynomial-time passive adversary against the serveraided protocol with additive splitting that can recover the client secret d (for sufficiently large RSA modulus) provided that:

δ < β 1 + α for 0 < α + β 1 < 1/2 α+β1+1- √ 4(α+β1) 2 +2(α+β1)-2 3 for 1/2 < α + β 1 < 1

Server-Aided Protocol with Multiplicative Splitting

In the server-aided protocol with multiplicative splitting (see Fig. 3), the secret d is decomposed as

d = d 1 • r mod ϕ(N ),
where d 1 N δ is kept secret by the client and

r = (d/d 1 ) mod ϕ(N ) + kϕ(N )
is known where k is some unknown integer with k N β1 .

The goal of the adversary is to recover d 1 . There exists k N α+β1+δ such that:

e • r • d 1 = 1 + k • (N + (1 -p -q)).
In the following, we present two lattice-based attacks using this equation for the two settings when the public exponent e is "small" (i.e. α < 1) or arbitrary.

3.2.1.

Case where e is "small" (α < 1)

We put e = er N 1+α+β1 and we have:

1 + k (N + (1 -p -q)) = 0 mod e .
The polynomial f (x, y) = 1+x(N +y) has as root

X 0 = (k , 1 -p -q) modulo e , with |k | X = N α+β1+δ and |1-p-q| Y with Y N 1/2
(for large N ). We use the linearization u = xy + 1 as in the attack on RSA with small secret exponent proposed by Boneh and Durfee [START_REF] Boneh | Cryptanalysis of RSA with private key d less than N 0.292[END_REF] and simplified by Herrmann and May [START_REF] Herrmann | Maximizing small root bounds by linearization and applications to small secret exponent RSA[END_REF]. We thus obtain the linear polynomial f (u, x) = u + N x. We use the same collection of polynomials as in [START_REF] Herrmann | Maximizing small root bounds by linearization and applications to small secret exponent RSA[END_REF]:

x i f j (e ) m-j for i, j 0, i + j m y j f i (e ) m-i for 1 j t, m t j i m
With t = τ m, τ 1 (for some parameter τ to be optimized) having as root

X 0 = (k , 1 -p -q, k (1 - p -q) + 1) modulo (e ) m , with |k (1 -p -q) + 1| U = N α+β1+δ+1/2
. Thus we define a lattice L generated the coefficient vector of each polynomial f (Xx, Y y, U u), for f in the collection of polynomials P. One can put an appropriate order on the set P (see [START_REF] Herrmann | Maximizing small root bounds by linearization and applications to small secret exponent RSA[END_REF]) for details and obtain a lower triangular matrix with the diagonal elements X i U j (e ) m-j (for i, j 0 and i + j m) and U i Y j (e ) m-i (for 1 j t and m t j i m).

The lattice L is of dimension

ω = m i=0 m-i j=0 1 + τ m j=1 m i= m t j 1 = 1 2 + τ 2 m 2 + o(m 2 )
and has determinant det(L) = X sx Y sy U su (e ) s e , where

s x = m i=0 m-i j=0 i = 1 6 m 3 + o(m 3 ), s y = τ m j=1 m i= m t j j = τ 2 6 m 3 + o(m 3 ), s u = m i=0 m-i j=0 j + τ m j=1 m i= m t j i = 1 6 + τ 3 m 3 + o(m 3 ), Client Server pk = (N, e), sk = (d, ϕ(N )) d 1 R ← -{0, . . . , N δ }; k R ← -{0, . . . , N β1 } r ← d -d 1 + k • ϕ(N ) m, r, N ----------→ c ← ----------c ← m r mod N c ← c • m d1 mod N Output c FIGURE 1. Server-Aided RSA Protocol with Additive Splitting δ α + β 1 0 1 0 1/2 FIGURE 2. Cryptanalysis of Server-Aided RSA Protocol with Additive Splitting s e = m i=0 m-i j=0 (m -j) + τ m j=1 m i= m t j (m -i) = 1 3 + τ 6 m 3 + o(m 3 ).
For large m, we can find all the solutions of the modular equation f (x, y) = 0 mod e if the following condition holds: det(L) < ((e ) m ) ω , that is

1 3 + τ 3 (α + β 1 + δ) + 1 2 1 6 + τ 3 + τ 2 6 < 1 6 + τ 3 (1 + β 1 + α).
To maximize δ, we choose τ max = 1 -2δ and obtain the inequality 2δ 2 -4δ + 1 -α -β 1 > 0 and the following result:

Theorem 3.2. There exists a (heuristic) polynomialtime passive adversary against the server-aided protocol with multiplicative splitting that can recover the client secret d (for sufficiently large RSA modulus) provided that:

δ < 1 - 1 + α + β 1 2
Remark 1. In our result, we used as usual in the setting of Coppersmith's methods the simplified success condition rather than the original condition for sufficiently large modulus N . For N of bit-length larger than 256, the bound of Theorem 3.2 can be reached for m 6. For N of bit-length respectively 128, the bound can be reached for m 8. Thus by sufficiently large modulus, we mean that the bit-length of the modulus is at least 128, which is always the case in practical applications of cryptography.

Remark 2. We do not have a passive attack against the protocol with multiplicative splitting if α + β 1 > 1 (in particular if e is of the same size as N ).

3.2.2.

Case where e is arbitrary. In order to attack the protocol for arbitrary public exponent e, we have to consider a stronger attack scenario. As mentioned in the introduction, it has been suggested several times to renew the decomposition of the secret exponent for each invocation of the protocol. In this paragraph, we present an attack against the server-aided protocol with multiplicative splitting when the adversary is allowed to observe k 2 different executions of the protocol (with independent random values).

We thus suppose that d is decomposed k times as

d = d i • r i with d i U = N δ for i ∈ {1, . . . , k}, with r i = (d/d i mod ϕ(N )) + k i ϕ(N ) N 1+β1
where k i N β1 . For j ∈ {2, . . . , k}, we have:

d j r j -d 1 r 1 = 0 mod ϕ(N ),
thus for j ∈ {2, . . . , k}, there exists k j N β1+δ such that:

d j r j -d 1 r 1 + k j (p + q -1) = 0 mod N.
Then for j ∈ {2, . . . , k}, we obtain a polynomial f j (y 1 , . . . , y k , z 2 , . . . , z k ) having as root X = (d 1 , . . . , d k , k 2 (p + q -1), . . . , k k (p + q -1)) modulo N with:

f j = r j y j -y 1 r 1 + z j mod N
We put f j = f j -z j for j ∈ {2, . . . , k}, K = N 1/2+β1 and ω = 2k -1 and we define the ωdimensional lattice L spanned by the rows of the following matrix: Client Server pk = (N, e), sk = (d, ϕ(N ))

d 1 R ← -{0, . . . , N δ }; k R ← -{0, . . . , N β1 } r ← (d/d 1 mod ϕ(N )) + k • ϕ(N ) m, r, N ----------→ c ← ----------c ← m r mod N c ← c d1 mod N Output c FIGURE 3. Server-Aided RSA Protocol with Multiplicative Splitting A =                  K K . . . K 0 f 2 . . . f k ↓ ↓ ↓ N . . . N                  y 1 y 2 . . . y k
The right-hand side is formed by all vectors coming from the set of polynomials {f 2 , . . . , f k }. We have

det(L) = K k N k-1 . The lattice L contains the vector v = (Kd 1 , . . . , Kd k , k 2 (p + q -1), . . . , k k (p + q -1)) with the Euclidean norm v = O( √ ωU K).
If we can find the vector v, then we will be able to recover the unknowns d j for j ∈ {1, . . . , k}. By Lemma 2.1 and our heuristic from Section 2.1, the vector v is likely to be the shortest vector in the lattice L if the following condition holds:

v √ ω det(L) ω , which is equivalent to U N (k-1)(1/2-β 1 ) 2k-1
Therefore, by using the LLL algorithm (the LLL algorithm is also used in the forthcoming results) we can heuristically recover (d 1 , . . . , d k ) with d i < N δ as long as:

δ < (k -1)(1/2 -β 1 ) 2k -1 .
Theorem 3.3. There exists a (heuristic) polynomialtime passive adversary against the server-aided protocol with multiplicative splitting that can recover the client secret d (for sufficiently large RSA modulus) after eavesdropping k 2 different executions of the protocol provided that:

δ < (k -1)(1/2 -β 1 ) 2k -1 .
The results from Theorems 3.2 and 3.3 are illustrated on Figure 4 (where the red zones indicate the values δ for which the protocol with multiplicative splitting is insecure).

δ α + β 1 0 1 0 1/4 0.292 k = 8 k = 4 k = 2 δ β 1 0 1 0 1/4

Server-Aided Protocol with Mixed Splitting

In the server-aided protocol with mixed splitting (see Fig. 5), the secret d is decomposed as

d = d 1 + d 2 • r mod ϕ(N ),
where d 1 N δ1 , d 2 N δ2 are kept secret unknown and

r = (d -d 1 )/d 2 mod ϕ(N ) + k • ϕ(N )
is known where k is some unknown integer with k N β1 . The goal of the adversary is to recover d 1 and d 2 .

There exists k N α+β1+δ2 such that:

e(d 1 + d 2 r) = 1 + k (N + (1 -p -q)).
In the following, we present two lattice-based attacks using this equation for the two setting when the public exponent e is "small" (i.e. α < 1) or arbitrary.

3.3.1.

Case where e is "small" (α < 1)

We put e = e • r N 1+α+β1 and we have: The trivariate polynomial f (x, y, z) = 1 + x(N + y) -ez has as root

1 + k (N + (1 -p -q)) -ed 1 = 0 mod e . Client Server pk = (N, e), sk = (d, ϕ(N )) d 1 R ← -{0, . . . , N δ1 }; d 2 R ← -{0, . . . , N δ2 } k R ← -{0, . . . , N β1 } r ← ((d -d 1 )/d 2 mod ϕ(N )) + k • ϕ(N ) m, r, N ----------→ c ← ----------c ← m r mod N c ← c d2 • m d1 mod N Output c
X 0 = (k , 1 -p -q, d 1 ) modulo e , with |k | X = N α+β1+δ2 , |1 -p -q| Y = N 1/2 and |d 1 | Z = N δ1
. We consider the following collection of polynomials:

x i z k f j (e ) m-j for i, j, k 0, i + j + k m y j z k f i (e ) m-i for i, k 0, i + k m; 1 j t With t = τ m (for some parameter τ to be optimized). If we proceed as in the previous section (by putting an appropriate order an the set of monomials and the set of polynomials), we obtain a lattice L of dimension

ω = i+j+k m 1 + i+k m;1 j t 1 = 1 6 + τ 2 m 3 + o(m 3 )
and det(L) = X sx Y sy Z sz (e ) s e , where:

s x = i+j+k m i + j + i+k m;1 j t i = 1 12 + τ 6 m 4 + o(m 4 ), s y = i+j+k m j + i+k m;1 j t i + j = 1 24 + τ 2 4 + τ 6 m 4 + o(m 4 ), s z = i+j+k m k + i+k m;1 j t k = 1 24 + τ 6 m 4 + o(m 4 ),
and

s e = i+j+k m m -i + i+k m;1 j t m -i = 1 8 + τ 3 m 4 + o(m 4 ).
We can thus find all the solutions of the modular equation f (x, y, z) = 0 mod e if det(L) < ((e ) m ) ω , i.e.

1 12 + τ 6 (α + β 1 + δ 2 ) + 1 2 1 24 + τ 6 + τ 2 4 +δ 1 1 24 + τ 6 < 1 24 + τ 6 (1 + β 1 + α).
To maximize δ 1 and δ 2 , we choose τ max = 1-2(δ1+δ2)

3 and obtain the inequality

-24(δ 2 1 +δ 2 2 )-48δ 1 δ 2 +42δ 1 +60δ 2 -15+18(α+β 1 ) < 0.
Theorem 3.4. There exists a (heuristic) polynomialtime passive adversary against the server-aided protocol with mixed splitting that can recover the client secret d (for sufficiently large RSA modulus) provided that:

-24(δ 2 1 +δ 2 2 )-48δ 1 δ 2 +42δ 1 +60δ 2 -15+18(α+β 1 ) < 0.
Furthermore if δ 1 = δ 2 = δ, we obtain the following corollary: Corollary 3.2. There exists a (heuristic) polynomial-time passive adversary against the serveraided protocol with mixed splitting (with δ 1 = δ 2 = δ) that can recover the client secret d (for sufficiently large RSA modulus) provided that:

δ < 17 -129 + 192(α + β 1 ) 32 .
Theorem 3.4 can be slightly improved by following the technique of [START_REF] Peng | Cryptanalysis of dual rsa[END_REF] for attacking the dual RSA. If δ 1 = δ 2 = δ, we show that there exists a (heuristic) polynomial-time passive adversary that can recover the client secret d (for sufficiently large RSA modulus) provided that: δ < (6 -15 + 24(α + β 1 ))/12.

We put the linearization u = xy + 1 as in the cryptanalysis of the dual RSA [START_REF] Peng | Cryptanalysis of dual rsa[END_REF] and we obtain the linear polynomial f (u, x, z) = u + N x -ez. We use the same collection of polynomials as in [START_REF] Peng | Cryptanalysis of dual rsa[END_REF]:

   x i z k f j (e ) m-j for i, j, k 0, i + j + k m y j z k-i f i (e ) m-i for 1 j t, m t j k m, 0 i k. With t = τ m, τ
1 (for some parameter τ to be optimized) having as root

X 0 = (k (1 -p -q) + 1, k , 1 -p -q, d 1 ) modulo (e ) m , with |k | X = N α+β1+δ2 , |1 -p -q| Y = N 1/2 , |d 1 | Z = N δ1 and |k (1 -p -q) + 1| U = XY .
If we put an appropriate order on the set of monomials and on the set of polynomials, we obtain a lattice L whose matrix is a lower triangular matrix with diagonal elements:

X i Z k U j (e ) m-j for i, j, k 0, i + j + k m, Y j Z k-i U i (e ) m-i for 1 j t, m t j k m, 0 i k.
The lattice L is of dimension

ω = i+j+k m 1+ t j=1 m k= 1 τ j k i=0 1 = 1 6 + τ 3 m 3 +o(m 3 )
and has determinant det(L) = U su X sx Y sy Z sz (e ) s e , where:

s u = i+j+k m j+ t j=1 m k= 1 τ j k i=0 i = 1 24 + τ 8 m 4 +o(m 4 ), s x = i+j+k m i = 1 24 m 4 + o(m 4 ), s y = t j=1 m k= 1 τ j k i=0 j = τ 2 8 m 4 + o(m 4 ), s z = i+j+k m k + t j=1 m k= 1 τ j k i=0 k -i = 1 24 + τ 8 m 4 + o(m 4 )
,

s e = i+j+k m m -i + t j=1 m k= 1 τ j k i=0 m -i = 1 8 + 5τ 24 m 4 + o(m 4 ).
We can thus find all the solutions of the modular equation f (u, x, y, z) = 0 mod e if the following condition holds:

det(L) < ((e ) m ) ω , that is 1 12 + τ 8 (α + β 1 + δ 2 ) + 1 2 1 24 + τ 8 + τ 2 8 +δ 1 1 24 + τ 8 < 1 24 + τ 8 (1 + β 1 + α).
To maximize δ 1 and δ 2 , we choose τ max = 1-2(δ1+δ2) 2 and obtain the inequality

-24(δ 2 1 +δ 2 2 )-48δ 1 δ 2 +40δ 1 +56δ 2 -14+16(α+β 1 ) < 0.
Theorem 3.5. There exists a (heuristic) polynomialtime passive adversary against the server-aided protocol with mixed splitting that can recover the client secret d (for sufficiently large RSA modulus) provided that:

-24(δ 2 1 +δ 2 2 )-48δ 1 δ 2 +40δ 1 +56δ 2 -14+16(α+β 1 ) < 0.
Furthermore if δ 1 = δ 2 = δ, we obtain the following corollary:

Corollary 3.3.
There exists a (heuristic) polynomial-time passive adversary against the serveraided protocol with mixed splitting (with δ 1 = δ 2 = δ) that can recover the client secret d (for sufficiently large RSA modulus) provided that: δ < 6 -15 + 24(α + β 1 ) 12 .

Theorem 3.5 slightly improved Theorem 3.4 but the improvement is mainly theoretical and in the following we have only implemented the attack corresponding to Theorem 3.4.

Experimental Results

We have implemented the attack in Sage 7.6 on a MacBook Air laptop computer (2,2 GHz Intel Core i7, 4 Gb RAM 1600 MHz DDR3, Mac OSX 10.10.5) for a 2048-bit modulus N and for e = 3 (α 0). We ran experiments for several values of β 1 , namely β 1 ∈ {0.002, 0.25, 0.5}. We suppose that d 1 , d 2 < N δ and the table below lists the theoretical bound

δ theo = 17 - √ 129 + 192β 1 32
and the experimental bound δ exp . The size of the manipulated integers grows with β 1 . After the Gröbner basis computations, we obtained a system of polynomials of dimension 1 but were always able to find the desired root (by factoring the first polynomial of the Gröbner with gives p + q -1 and thus N 's factorization). We run 2 7 experiments for each choice of parameters and Table 1 gives the average running times (in seconds) of the LLL algorithm and the Gröbner basis computation. In order to attack the protocol for arbitrary public exponent e, we consider again the stronger attack scenario where the adversary is allowed to observe k 2 different executions of the protocol (with independent random values). We suppose that d is decomposed k times as d = d

(i) 1 + r i d (i) 2 mod ϕ(N ) with d (i) 1 N δ1 , d (i) 2
N δ2 unknown for i ∈ {1, . . . , k}, and

r i = (d -d (i) 1 )/d (i) 2 mod ϕ(N ) + k i ϕ(N ) N 1+β1
where k i N β1 is unknown. For i ∈ {2, . . . , k}, we have:

d (i) 1 + r i d (i) 2 -d (1) 1 + r 1 d (1) 2 = 0 mod ϕ(N ),
thus for i ∈ {2, . . . , k}, there exists k i N β1+δ2 such that:

d (i) 1 + r i d (i) 2 -d (1) 1 + r 1 d (1) 2 + k i (p + q -1) = 0 mod N.
Then using the same technique as for e arbitrary in the multiplicative splitting, we can recover (d

(1) 1 , d (1) 2
. . . , d (k) 1 , d (k)
2 ) as long as:

k(δ 1 + δ 2 ) + (1/2 + β 1 + δ 2 )(k -1) < k -1,
that is:

kδ 1 + (2k -1)δ 2 < (k -1)(1/2 -β 1 ).
Theorem 3.6. There exists a (heuristic) polynomialtime passive adversary against the server-aided protocol with mixed splitting that can recover the client secret d (for sufficiently large RSA modulus) after eavesdropping k 2 different executions of the protocol provided that:

kδ 1 + (2k -1)δ 2 < (k -1)(1/2 -β 1 ). Corollary 3.4.
There exists a (heuristic) polynomial-time passive adversary against the serveraided protocol with mixed splitting (with δ 1 = δ 2 = δ) that can recover the client secret d (for sufficiently large RSA modulus) after eavesdropping k 2 different executions of the protocol provided that:

δ < k -1 3k -1 (1/2 -β 1 ).
Our results are illustrated on Figure 6 (where the red zones indicate the values δ for which the protocol with multiplicative splitting is insecure). In 1988, Matsumoto, Kato and Imai [START_REF] Matsumoto | Speeding up secret computations with insecure auxiliary devices[END_REF] proposed the following protocol, known as RSA-S1, in which a client computes an RSA exponentiation with secret exponent (e.g. a signature), with the help of an untrusted powerful server. In the following, we assume that the server is honest-but-curious (i.e. we consider only passive adversaries).

δ α + β 1 0 1 0 1/4 0.176 k = 8 k = 4 k = 2 δ β 1 0 1 1/4
• Step 1. The client picks uniformly at random n 1 "small" integers d i ∈ Z, for i ∈ {1, . . . , n} with d i ∈ {0, . . . , U } for some integer U .

• Step 2. The client picks uniformly at random n elements r i ∈ Z N , for i ∈ {1, . . . , n} from the set of vectors satisfying the congruence:

d 1 • r 1 + • • • + d n • r n = d mod ϕ(N ).
• Step 3. The client sends the (n + 2)-tuple (m, r 1 , . . . , r n , N ) to the server. • Step 4. The server computes and sends to the client z i = m ri mod N , for i ∈ {1, . . . , n}.

• Step 5.. The client computes n i=1

z di i = z d1 1 . . . z dn n mod N which is equal to m d mod N .
Remark 3. Depending on the memory capacity of the client, the final exponentiation performed by the client in Step 5.

may be done by multivariate exponentiation with multiplication complexity 2 • log 2 (U ) + 2 n + O(1) and memory complexity 2 n or by independent single exponentiation with multiplication complexity 2 • n • log 2 (U ) + n + O(1) and memory complexity n. Obviously, many tradeoffs are possible, but we consider only these two settings in the following for efficiency comparison.

Previous Cryptanalysis of RSA-S1.

In this section, we briefly recall the two main attacks known on the RSA-S1 Protocol (more details are given in [START_REF] Nguyen | On the insecurity of a server-aided RSA protocol[END_REF]).

4.2.1. Meet-in-the-Middle Attack. Since m e(d1r1+•••dnrn) = m ed = m mod N for all m ∈ Z *
N , a meet-in-the-middle attack against RSA-S1 consists, assuming for simplicity n even, in computing and storing in a hash table for (d n/2+1 , . . . , d n ) ∈ {0, . . . , U } n/2 in this hash table. This simple approach allows to recover the secret exponent d in time complexity O(U n/2 ) and memory complexity O(U n/2 ).

m e(d1r1+•••d n/2

Lattice-based Attack.

Nguyen and Shparlinski [START_REF] Nguyen | On the insecurity of a server-aided RSA protocol[END_REF] proposed a lattice-based attack on the (one-round) RSA-S1 protocol when a small public exponent e N α is used, for some α 0. They showed that one can recover the secret d as long as the sizes of each unknown d i , for i ∈ {1, . . . , n} satisfies:

U < N 1-2α 2(n+1) .
In particular, their attack can be successful only for α < 1/2.

New Attack against RSA-S1 for Large e

In this section we propose a k-rounds lattice attack (with k

2) on the RSA-S1 Server-Aided protocol which works for any public exponent e.

When the RSA-S1 Server-Aided protocol is performed in k-rounds, the passive adversary knows k decompositions of the secret d (namely, we have d

= n i=1 r (j) i d (j)
i mod (p-1)(q-1), for j ∈ {1, . . . , k} where the integers r (j) i are known to the server and the integers d (j) i are kept secret by the client and d (j) i < U , for some integer U ). The goal is to recover the integers d (j) i , for i ∈ {1, . . . , n} and j ∈ {1, . . . , k}. We suppose that e N α , r (j) i N and that p and q have the same size (p, q N 1 2 ). Then for j ∈ {2, . . . , k}, we have:

n i=1 r (j) i d (j) i - n i=1 r (1) i d (1) i = k j (p -1)(q -1),
for some integer k j U . Then for j ∈ {2, . . . , k}, we obtain a polynomial f j (z 1,1 , . . . , z 1,n , . . . , z k,1 , . . . , z k,n , z 2 , . . . , z k ) having as root

X = (d (1)
1 , . . . , d (1) n , . . . , d

(k) 1 , . . . , d (k) n , k 2 (p + q -1), . . . , k k (p + q -1))
modulo N with:

f j = z j + n i=1 r (j) i z j,i - n i=1 r (1)
i z 1,i mod N

We put f j = f j -z j for j ∈ {2, . . . , k}, K = N 1/2 and ω = nk + k -1, M 1 = {z 1,1 , . . . , z 1,n , . . . , z k,1 , . . . , z k,n } = {m 1 , . . . , m ω1 } with ω 1 = M 1 = nk and m 1 = z 1,1 , . . . , m n = z 1,n , . . . , m ω1 = z k,n . Each polynomial f j can be expressed as a vector with respect to the order < on M 1 (with m i < m i+1 ). We define the ω-dimensional lattice L spanned by the rows of the following matrix:

A =                  K K . . . K 0 f 2 . . . f k ↓ ↓ ↓ N . . . N                  m 1 m 2 . . . mω 1
The right-hand side is formed by all vectors coming from the set of polynomials {f 2 , . . . , f k }. We have det(L) = K nk N k-1 . The lattice L contains the vector

v = (Kd (1)
1 , . . . , Kd (1) n , . . . , Kd

1 , . . . , Kd (k) n , -k 2 (p + q -1), . . . , -k k (p + q -1)) with the Euclidean norm v = O( √ ωU K). If we can find find the vector v, then we will be able to recover the unknowns d (j) i for j ∈ {1, . . . , k} and i ∈ {1, . . . , n}. By Lemma 2.1 and our heuristic from Section 2.1, the vector v is likely to be the shortest vector in the lattice L if the following condition holds: 1) . Therefore, we can recover the secret d as long as the sizes of each unknown d (j) i for j ∈ {1, . . . , k} and i ∈ {1, . . . , n} satisfies:

v √ ω det(L) ω , which is equivalent to U N k-1 2(nk+k-
U < N k-1 2(nk+k-1) → k→∞ N 1 2(n+1) .
Remark 4. For fixed k and for α 1/2, our attack is successful while the one of Nguyen and Shparlinski does not work. For fixed k and for 1/4 α < 1/2, our bound is better than the one of Nguyen and Shparlinski. For 0 < α < 1/4, our asymptotic bound is better than the bound of Nguyen and Shparlinski. And for α = 0, our asymptotic bound is the same as the bound of Nguyen and Shparlinski.

Experimental Results

The table below lists the theoretical bound δ theo = k-1 2(nk+k-1) (U < N δ ) and the experimental bound δ exp for a 2048-bit modulus N and for e N 1/2 with a few number of rounds (2 k 4) and a few number of unknown blocks in each decomposition of the secret d (n ∈ {2, 3}). We run 2 7 experiments for each choice of parameters and Table 2 gives the average running times (in seconds) of the LLL algorithm (using the same configuration as above).

ANALYSIS OF A VARIANT OF RSA-S1 SERVER-AIDED PROTOCOL

In this section, we describe and analyze a variant of the server-aided protocol RSA-S1 which might be useful in cases where the client has strong memory constraints and cannot use multi-exponentiation techniques. In this setting, the final exponentiation in the protocol RSA-S1 is simply done by performing independently n multiplications with exponents of size U .

Description of a New Server-Aided Protocol

Our variant of the RSA-S1 protocol works as follows:

• Step 1. The client picks uniformly at random n 1 "small" integers d i ∈ Z, for i ∈ {1, . . . , n} with d i ∈ {0, . . . , U } for some integer U .

• Step 2. The client picks uniformly at random n elements r i ∈ Z N , for i ∈ {1, . . . , n} from the set of vectors satisfying the congruence:

d = r 1 •d 1 +r 2 •(d 1 d 2 )+• • •+r n •(d 1 d 2 . . . d n ) mod ϕ(N ), • Step
z 1 • z 2 • z 3 z 4 • • • (z dn n ) • • • d4 d3 d2 d1 mod N.
which is equal to m d mod N .

In this protocol, the final operation performed by the client is inherently sequential and it is not possible to use multi-exponentiation techniques. The linear random decomposition is replaces by a degree n multi-variate polynomial, one can evaluate using n multiplications using Horner rule. The client final operation consists therefore in n independent single exponentiation (that cannot be parallelized) with multiplication complexity 2

• n • log 2 (U ) + n + O(1)
and memory complexity n. Its efficiency for fixed U is similar to the one of the protocol RSA-S1 but we will see that this protocol (we call RSA-S1H) seems more resistant to cryptanalysis. It is worth noting that a meet-in-the-middle attack against RSA-S1H can be mounted even if the group order is unknown to the adversary (see [START_REF] Coron | A new baby-step giant-step algorithm and some applications to cryptanalysis[END_REF] for instance). It allows to recover the secret exponent d in time complexity O(U n/2 ) and memory complexity O(U n/2 ).

A One-Round Attack on RSA-S1H Server-Aided Protocol

In this section, we propose a one-round passive attack on RSA-S1H protocol when a small public exponent e is used (for instance e = 3).

Description of the Attack

The secret d is decomposed once as

d = r 1 d 1 + r 2 d 1 d 2 + • • •+r n d 1 d 2 . . . d n mod (p-1)(q -1)
, where the integers r 1 , . . . , r n N are known and the integers d i U , for i ∈ {1, . . . , n} are kept secret by the client. We suppose that e N α with 0 < α < 1/2 very small and that p and q have the same size (p, q N 1 2 ) . In order to recover the secret d, the goal is to recover the integers d i , for i ∈ {1, . . . , n}. We have modulo N with s = p + q -1 and :

e(r 1 d 1 +r 2 d 1 d 2 +• • •+r n d 1 d 2 . . . d n ) = 1 mod (p-1)(q-1),
f j = z j + n i=1 r (1) i z 1,i - n i=1 r (j) i z j,i mod N Putting g j = z j + n i=1 r (1)
i U i-n z 1,i - n i=1 r (j)
i U i-n z j,i mod N, one can easily verify that g j has as root X = (U n-1 d

(1) 1 , . . . , d

1 . . . d (1) n , . . . , U n-1 d (k) 1 , . . . , d (k) 1 . . . d (k) n , k (2) s, . . . , k (k) s) modulo N . We put f j = g j -z j for j ∈ {2, . . . , k}, K = N 1/2 and ω = nk + k -1, M 1 = {z 1,1 , . . . , z 1,n , . . . , z k,1 , . . . , z k,n } = {m 1 , . . . , m ω1 } with ω 1 = M 1 = nk and m 1 = z 1,1 , . . . , m n = z 1,n , . . . , m ω1 = z k,n . Each polynomial f j can be expressed as a vector with respect to the order < on M 1 (with m i < m i+1 ). Then we define the ω-dimensional lattice L spanned by the rows of the following matrix:

A =                  K K . . . K 0 f 2 . . . f k ↓ ↓ ↓ N . . . N                  m 1 m 2 . . . mω 1
The right-hand side is formed by all vectors coming from the set of polynomials {f 2 , . . . , f k }. We have det(L) = K nk N k-1 . The lattice L contains the vector v =(KU n-1 d

(1) 1 , . . . , Kd

1 . . . d (1) n , . . . , KU n-1 d (k) 1 , . . . , Kd (k) 1 . . . d (k) n , -k (2) s, . . . , -k (k) s)

with the Euclidean norm v = O( √ ωU n K). If we can find find the vector v, then we will be able to recover the unknowns d (j) i for j ∈ {1, . . . , k} and i ∈ {1, . . . , n}. By Lemma 2.1 and the Gaussian heuristic, the vector v is likely to be the shortest vector in the lattice L if the following condition holds:

v √ ω det(L) ω ,
which is equivalent to

U N k-1 2n(nk+k-1)
Therefore, we can recover the secret d as long as the sizes of each unknown d • Step 0. The client computes integers d p < p and d q < q such that d p = d mod p -1 and d q = d mod q -1. • Step 1. The client picks uniformly at random n 1 pairs of "small" integers (d i , d i ) ∈ Z 2 , for i ∈ {1, . . . , n} with d i , d i ∈ {0, . . . , U } for some integer U .

• Step 2. The client picks uniformly at random n elements r i ∈ {0, . . . , V } (for some integer V ), for i ∈ {1, . . . , n} from the set of vectors satisfying the congruence:

d 1 • r 1 + • • • + d n • r n = d p mod p -1. d 1 • r 1 + • • • + d n • r n = d q mod q -1.
• Step 3. The client sends the (n + 2)-tuple (m, r 1 , . . . , r n , N ) to the server.

U < N 1-2 -2n+2 2n+1 -2n+2 2 (1-2 - 1 2n+1 )-ε (2n+1) .

EFFICIENCY OF SERVER-AIDED RSA PROTOCOLS

In this section, we compare the efficiency of the protocols studied in the previous sections. We consider 3072-bit RSA moduli and different values for n ∈ {1, 2, 4, 8}. Since our two families of attacks (for small and arbitrary public exponents), succeed asymptotically (when k goes to ∞) for the same bound U , we do not distinguish them in the comparison. For RSA-S1 and RSA-S2, we distinguish two settings depending on whether the client has enough memory to perform multi-exponentiation in Step 5. of these two protocols.

  which corresponds to an additive splitting of the secret key as d = d 1 + r mod ϕ(N ); • c = c d1 mod N , which corresponds to a multiplicative splitting of the secret key as d = r • d 1 mod ϕ(N ); • c = m d1 c d2 mod N , which corresponds to a mixed splitting of the secret key as d = d 1 + r • d 2 mod ϕ(N ).

Fig. 1 )

 1 , the secret d is decomposed as d = d 1 + r mod ϕ(N ), where d 1 N δ is kept secret by the client and r = [(d -d 1 ) mod ϕ(N )] + kϕ(N ) is known where k is some unknown integer with k N β1 . Putting d = d 1 + r, then d = d mod ϕ(N ) and d N β , with β = 1+β 1 . The adversary knows r N β that is an approximation of d

  Theorem 3.1 (Joye-Lepoint). Let N = pq be a product of two primes, e N α be an integer, d = e -1 mod ϕ(N ) and d = d + ϕ(N ) N β be an integer. If d = d + d 0 with d known, d 0

FIGURE 4 .

 4 FIGURE 4. Cryptanalysis of Server-Aided RSA Protocol with Multiplicative Splitting (left: small e N α ; right: arbitrary e, k ∈ {2, 4, 8} rounds)

FIGURE 5 .

 5 FIGURE 5. Server-Aided RSA Protocol with Mixed Splitting

FIGURE 6 .

 6 FIGURE 6. Cryptanalysis of Server-Aided RSA Protocol with Mixed Splitting (left: small e N α ; right: arbitrary e, k ∈ {2, 4, 8} rounds)

  r n/2 ) mod N for all (d 1 , . . . , d n/2 ) ∈ {0, . . . , U } n/2 and searching m 1-e(d n/2+1 r n/2+1 +•••dnrn)

3 .

 3 The client sends the (n + 2)-tuple (m, r 1 , . . . , r n , N ) to the server. • Step 4. The server computes and sends to the client z i = m ri mod N , for i ∈ {1, . . . , n}. • Step 5.. The client computes

1 .

 1 (j) i for j ∈ {1, . . . , k} and i ∈ {1, . . . , n} satisfies: Description of RSA-S2 Matsumoto, Kato and Imai [3] also proposed another protocol, known as RSA-S2 which employs the Chinese Remainder Theorem to speed up the client's computation.

•

  Cryptanalysis of RSA-S2. The protocol RSA-S2 employs the Chinese Remainder Theorem to speed up the client's computation. Castelluccia,

	Mykletun and Tsudik [7] revisited in 2006 the RSA-
	S2 protocol to propose a technique for re-balancing
	RSA-based client/server handshakes.	They
	mentioned a meet-in-the-middle attack against
	RSA-S1 but claimed that " this attack . . .
	does not apply to the RSA-S2 protocol ". They
	proposed several security parameters for RSA-S2.

TABLE 1 .

 1 Experimental Results (Theorem 3.4) -Average running times (in seconds) of the LLL algorithm and the Gröbner basis computation 3.3.3. Case where e is arbitrary.

	β1	δ theo	δexp	m dimension LLL time(s) Gröbner basis time(s)
	0.002 0.175	0.17	5	77	8.89	0.026
	0.25	0.115 0.115	4	50	1.51	0.011
	0.5	0.062	0.06	4	65	24.07	14.97

TABLE 3 .

 3 Efficiency

			log 2 (N )	1	2	3	4	5	6	7	8	9	10
			RSA-S1	2048	512	341	256	204	170	146	128	113	102	93
		RSA-S1H	2048	512	170	85	51	34	24	18	14	11	9
			RSA-S1	3072	768	512	384	307	256	219	192	170	153	139
		RSA-S1H	3072	768	256	128	76	51	36	27	21	17	13
							comparisons (RSA-S1 and RSA-S1H)
	n	δ theo	δexp	dimension	LLL time(s)
	2	0.083	0.082	3		0.002205
	3	0.0416	0.0414	4		0.001315
	4	0.025	0.024	5		0.001572
	TABLE 4. Experimental Results (RSA-S1H) -Average
	running times (in seconds) of the LLL algorithm and the
	Gröbner basis computation

TABLE 5 .

 5 • Step 4. The server computes and sends to the client z i = m ri mod N , for i ∈ {1, . . . , n}. • Step 5.. The client computes Experimental Results (RSA-S2) -Average running times (in seconds) of the LLL algorithm and the Gröbner basis computation recover the secret d as long as the sizes of each unknownd 1 i , d 2 i , c 1 i , c2i , for i ∈ {1, . . . , n} satisfies:

	n
	z di i = z d1 1 . . . z dn n mod p
	i=1

If one of this gcd's is actually equal to N for some (d n/2+1 , . . . , dn) ∈ {0, . . . , U } n/2 and one can obtain a prime divisor of N by looking (in time Õ(U n/2 )) for the vector (d 1 , . . . , d n/2 ) ∈ {0, . . . , U } n/2 for which gcd(m e•(d 1 r 1 +•••+dnrn) -m, N ) is non-trivial.

Acknowledgments. The authors are supported in part by the French ANR ALAMBIC Project (ANR-16-CE39-0006).

then there exists an integer k eU n such that:

Thus we obtain a linear polynomial f (x 1 , . . . , x n+1 ) having as root X = (d 1 , d 1 d 2 , . . . , d 1 d 2 . . . d n , k(p + q -1) -1) modulo N with :

Putting f = n+1 i=1 d i x i (with d i = er i for i ∈ {1, . . . , n} and d n+1 = 1) and f = n+1 i=1 d i x i (with d i = d i U i-n mod N for i ∈ {1, . . . , n} and d n+1 = 1), one can easily verify that f has as root

modulo N . We define the n + 1-dimensional lattice L spanned by the rows of the following matrix:

with K = N 1/2 . We have det(L) = N e n K n and the lattice L contains the vector v =(-k(p + q -1) + 1, eKU n-1 d 1 , eKU with the Euclidean norm v = O( √ n + 1U n K). If we can find find the vector v, then we will be able to recover the unknowns d i for i ∈ {1, . . . , n}. By Lemma 2.1 and the Gaussian heuristic, the vector v is likely to be the shortest vector in the lattice L if the following condition holds: n+1) . Therefore, we can recover the secret d as long as the sizes of each unknown d i for i ∈ {1, . . . , n} satisfies:

If e is very small (namely α 0), we can thus heuristically recover the secret d as long as the sizes of each unknown d i for i ∈ {1, . . . , n} satisfies:

Furthermore, from θ = -k(p + q -1) + 1, and the d i 's for i ∈ {1, . . . , n}, one may compute k as k = ed -θ N , where

-k and yield the factorization of N in polynomial time.

Efficiency comparisons.

Table 3 gives for a 2048-bit and a 3072-bit RSA modulus and for a very small public exponent e (α 0), the theoretical lower bound

) on the number of bits of each secret d i , i ∈ {1, . . . , n} in the decomposition of the secret d in the RSA-S1 protocol with linear polynomial (resp. RSA-S1H) to prevent our lattice-based attacks (for n 10).

To prevent meet-in-the-middle attacks, it is necessary to use parameters U and n such that U n/2 2 κ where κ is the security parameter. For instance, to achieve 128-bits security with log 2 (N ) = 3072, one can use for n = 4 a value U 2 76 = 2 max(76,256/4) for RSA-S1H (instead of U 2 256 for RSA-S1) and for n = 10 a value U 2 25.6 = 2 max (13,256/10) for RSA-S1H (instead of U 2 139 for RSA-S1).

Experimental Results.

The table below lists the theoretical bound δ theo = 1 2n(n+1) (U < N δ ) and the experimental bound δ exp for a 1024-bit modulus N and for e = 3 a few number of unknown blocks in each decomposition of the secret d (n ∈ {2, 3, 4}). We run 2 7 experiments for each choice of parameters and Table 4 gives the average running times (in seconds) of the LLL algorithm (using the same configuration as above).

A k-Round Attack on RSA-S1H Server-Aided Protocol

In this section, we propose a k-round attack on RSA-S1H protocol which works for any public exponent e.

Description of the Attack

The secret d is decomposed k 2 times as d = r

n mod (p -1)(q -1) for j ∈ {1, . . . , k}, where the integers r U , for i ∈ {1, . . . , n} are kept secret by the client. For j ∈ {1, . . . , k}, we put

x t and we suppose that e N α with 0 < α. In order to recover the secret d, the goal is to recover the integers d (j) i , for some j ∈ {1, . . . , n} and for all i ∈ {1, . . . , n}. For j ∈ {2, . . . , k}, we have

1 , . . . , d (1) n )-P j (d

, then there exists an integer k (j) U n such that:

1 , . . . , d (1) n )-P j (d

For each j ∈ {2, . . . , k}, we thus obtain a linear multivariate polynomial over Z N f j (z 1,1 , . . . , z 1,n , . . . , z k,1 , . . . , z k,n , z 2 , . . . , z k ) having as root the (nk + k -1)-tuple

1 . . . d (1) n , . . . , d

and uses the Chinese Remainder Theorem to recover 3 σ = m d mod N satisfying σ p = m dp mod p and σ q = m dq mod q.

Time/Memory Tradeoff Attack using

Multi-Evaluation of Polynomials

be a polynomial of degree less than ∆ = 2 d . The multipoint evaluation problem is the task of evaluating P at ∆ distinct points α 0 , . . . , α ∆-1 ∈ Z N . Using Horner's evaluation rule, it is easy to propose a solution that uses O(∆ 2 ) addition and multiplication in Z N but it is well-known that there exists an algorithm with quasi-linear complexity O(∆ log 2 ∆) = Õ(∆) operations in Z N using a divide-and-conquer approach [START_REF] Bostan | Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator[END_REF][START_REF] Fiduccia | Polynomial evaluation via the division algorithm: The Fast Fourier Transform revisited[END_REF].

The multipoint evaluation of univariate polynomials has found numerous application in cryptanalysis (e.g. [START_REF] Coron | Cryptanalysis of the RSA subgroup assumption from TCC 2005[END_REF][START_REF] Chen | Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers[END_REF]). In this paragraph, we show that this technique allows to break the RSA-S2 Protocol in time Õ(U n/2 ).

For simplicity, we assume that n is even (but the attack can readily be extended to odd n). Let m be some random element of Z * N . We have m e•dp = m mod p (since d p is the inverse of e modulo p -1). With high probability, we have m e•dp = m mod q (for d p = d q ). Therefore, we have with overwhelming probability gcd(m e•dp -m, N ) = p. In the setting of RSA-S2, a passive adversary knows integers r 1 , . . . , r n such that

In order to apply a meet-in-the-middle approach, one may be tempted to first compute m e•(d1r1+•••+d n/2 r n/2 ) for all vectors (d 1 , . . . , d n/2 ) ∈ {0, . . . , U } n/2 in time Õ(U n/2 ) and then compute m e•(d n/2+1 r n/2+1 +•••+dnrn) for all vectors of integers (d n/2+1 , . . . , d n ) ∈ {0, . . . , U } n/2 in time Õ(U n/2 ). However, in order to compute all possible gcd's, we have to consider all the pairs and the overall time complexity is Õ(U n ).

Using multi-evaluation of polynomials, one can simply consider the polynomial

(m e•(d1r1+•••+d n/2 r n/2 ) X-m) 3 Given the (precomputed) values αp = q • (q -1 mod p) and αq = p • (p -1 mod q), we have

The degree of P is ∆ = U n/2 and one can compute its evaluation at the ∆ points m e•(d n/2+1 r n/2+1 +•••+dnrn) for (d n/2+1 , . . . , d n ) ∈ {0, . . . , U } n/2 in time Õ(∆) = Õ(U n/2 ).

We can then simply compute gcd(P (m e•(d n/2+1 r n/2+1 +•••+dnrn ), N )

for each vector (d n/2+1 , . . . , d n ) ∈ {0, . . . , U } n/2 and with high probability we will obtain one non-trivial 4 factor of N .

Remark 5. As mentioned above, Castelluccia, Mykletun and Tsudik [START_REF] Castelluccia | Improving secure server performance by re-balancing SSL/TLS handshakes[END_REF] revisited in 2006 the RSA-S2 protocol. They proposed several security parameters for RSA moduli of bit-size 1024, 1536 and 2048. For these parameters the time and memory complexity term U n/2 of our attack are only equal to 2 36 , 2 40 and 2 44 (respectively) and these parameters are therefore broken.

A One-Round Attack using Herrmann-May Technique

In this section, we propose a one-round attack on RSA-S2 protocol using Herrmann-May technique that is a Coppermith's technique to find small solutions of a linear polynomial modulo an unknown prime number, where a multiple of that prime is known. In our attack, we suppose that a very small public exponent e (for instance e = 3) is used and that small random elements r i 's are used (V < p).

Description of the Attack

The secrets d p and d q are decomposed once as

, where the integers r 1 , . . . , r n p are known and the integers d i , d i U = N γ , for i ∈ {1, . . . , n} are kept secret by the client. We suppose that e N α with α 0 and that p and q have the same size (p, q N 1 2

) . The goal is to recover the integers d i , d i , for i ∈ {1, . . . , n}. In the following, we show how to recover the integers d i , for i ∈ {1, . . . , n} and the same technique can be used to recover the others integers d i , for i ∈ {1, . . . , n}. We have

then there exists an integer k eU such that e(r

). Thus we have:

where the prime p is unknown, we only know the modulus N which is a multiple of p. We obtain a linear polynomial f (x 1 , . . . , x n+1 ) having as root X = (d 1 , d 2 , . . . , d n , k) modulo p with :

We use the following theorem proved by Herrmann and May in [START_REF] Herrmann | Solving linear equations modulo divisors: On factoring given any bits[END_REF] to find the root X = (d 1 , d 2 , . . . , d n , k): Theorem 6.1. Let ε > 0 and let N = pq be a sufficiently large composite integer with a divisor p N β . Let g(x 1 , . . . , x ) ∈ Z[x 1 , . . . , x ] be a monic polynomial in variables. We can find heuristically all solutions (y 1 , . . . , y ) of the equation f (x 1 , . . . , x ) = 0 mod p with

The time and space complexity of the algorithm is polynomial in log 2 N and ( c0 ε ) , where c 0 is Euler's constant.

Applying Theorem 6.1 with β = 1 2 and a very small ε > 0, we can heuristically find the root

Therefore, if N sufficiently large and e is very small (namely α 0), for a very small ε > 0 we can heuristically recover the secret d i , d i , for i ∈ {1, . . . , n} as long as the sizes of each unknown d i , d i for i ∈ {1, . . . , n} satisfies:

. Remark 6.

• We can find the roots in polynomial time whenever n + 1 O(log 2 (log 2 N )).

• In the proof of Theorem 6.1, Herrmann and May used Coppermith's method with the following collection of polynomials which share a common root modulo p t : g i2,...,i ,j = x i2 2 . . . x i g j N max(t-j,0) , where i 2 , . . . , i ∈ {0, . . . , m} such that

• In the previous theorem, the bounds of the unknowns d i , d i , for i ∈ {1, . . . , n} are identical and there is no condition on the bound U of the unknowns. In particular, the results from [START_REF] Takayasu | Better lattice constructions for solving multivariate linear equations modulo unknown divisors[END_REF] cannot be applied in this setting.

Experimental Results

The table below lists the theoretical bound

(U < N δ theo ) and the experimental bound δ exp for a 1024-bit modulus N = pq and p, q N 1/2 , for e = 3 and with a few number of unknown blocks in each decomposition of the secrets d p and d q (n 5). In our experiments, we obtained after the LLL reduction and the Gröbner basis computations, a system of polynomials of dimension 1 but were always able to find the desired root. We run 2 4 experiments for each choice of parameters and Table 5 gives the average running times (in seconds) of the LLL algorithm and the Gröbner basis computation (using the same configuration as above).

Remark 7. Castelluccia et al. proposed parameters in [START_REF] Castelluccia | Improving secure server performance by re-balancing SSL/TLS handshakes[END_REF] for n = 2. Even if one doubles the bit-size of the proposed U in order to prevent the meet-in-the-middle attack from the previous section, we obtain for RSA moduli of bit-size 1024, 1536 and 2048, U equal to 2 72 , 2 80 and 2 88 , i.e. U N 0.070 , U N 0.052 an U N 0.044 (respectively). Our attack works for U N 0.0635 and the last two (updated) parameters are therefore broken in practice.

A Two-Round Attack using Herrmann-May technique

In this section, we give a description of a Two-Round attack on RSA-S2 protocol using Herrmann-May technique when an arbitrary public exponent e is used. The secrets d p and d q are decomposed twice as

, where the integers r 1 i , r 2 i p for i ∈ {1, . . . , n} are known and the integers d

, for i ∈ {1, . . . , n} are kept secret by the client. We suppose that e N α with α > 0 arbitrary and that p and q have the same size (p, q N 1 2 ) . The goal is to recover the integers

where the prime p is unknown. If we proceed as in the previous section, for a very small ε > 0, we can heuristically find X = (d


Thierry Mefenza

Damien Vergnaud

Msc2010 11t71

Polynomial Interpolation of the Generalized Diffie-Hellman and Naor-Reingold Functions

Keywords: Naor-Reingold function, Generalized Diffie-Hellman function, polynomial interpolation, finite fields

In cryptography, for breaking the security of the Generalized Diffie-Hellman and Naor-Reingold functions, it would be sufficient to have polynomials with small weight and degree which interpolate these functions. We prove lower bounds on the degree and weight of polynomials interpolating these functions for many keys in several fixed points over a finite field.

Introduction

The security of most cryptographic protocols relies on some unproven computational assumption which states that a well-defined computational problem is intractable (i.e. cannot be solved by a Turing machine in polynomial time). In group-based cryptography, we generally consider a cyclic group G (denoted multiplicatively) generated by some element g and the so called computational Diffie-Hellman assumption states that it is difficult to compute the element g xy from known elements g x and g y (for x and y picked uniformly at random between 1 and the order G). This assumption is the basis of the Diffie-Hellman key exchange [START_REF] Diffie | New directions in cryptography[END_REF] and the most efficient means known to solve this computational problem in groups used for cryptography is to solve the standard discrete logarithm problem (i.e. given h an element picked uniformly at random in G, compute x such that g x = h). Unfortunately, even the computational Diffie-Hellman assumption by itself is generally not sufficient to assess the security of protocols proposed and used in group-based cryptography. Cryptographers have then proposed much stronger assumptions in order to analyze the security of cryptosystems. For instance, the decision Diffie-Hellman assumption [START_REF] Boneh | The decision Diffie-Hellman problem[END_REF] states that given a cyclic group G given some elements g, g x and g y , no efficient algorithm can distinguish between g xy and an element picked uniformly at random in G. This assumption has been used in numerous important cryptographic applications.

In 1997, based on the decision Diffie-Hellman assumption, Naor and Reingold [START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF][START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF] proposed an efficient pseudo-random function family (i.e. 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). Their function takes inputs in {0, 1} n (for some parameter n) and outputs an element in a group G of prime order with generator g. The secret key is an ndimensional vector a = (a 1 , . . . , an) ∈ ((Z/ Z) * ) n and the Naor-Reingold function is defined as

fa : {0, 1} n -→ G (x 1 , . . . , xn) -→ fa(x 1 , . . . , xn) = g n i=1 a x i i mod
To simplify the notation, given an n-dimensional vector a = (a 1 , . . . , an) ∈ ((Z/ Z) * ) n and a variable x that will denote indifferently an n-bit string (x 1 , . . . , xn) ∈ {0, 1} n or an integer x ∈ {0, 1, . . . , 2 n -1} (which implicitly defines (x 1 , . . . , xn) ∈ {0, 1} n the bit representation of x with extra leading zeros if necessary), we denote a x the element in F = (Z/ Z) defined by a x = a x1 1 • • • a xn n mod . In addition, when the generator g is fixed, we will denote [x] = g x for any x ∈ F . With this notation, the Naor-Reingold function is simply defined by fa(x) = g a x = [a x ]. It is shown in [START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF][START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF] that the Naor-Reingold function is pseudo-random if the decision Diffie-Hellman assumption holds in the group G. Two interesting candidates for G are a subgroup of the multiplicative group of a (prime) finite field and a subgroup of the points of an elliptic curve defined over a finite field.

With the development of pairing-based cryptography, new assumptions in cyclic groups G were proposed to base the security of more complex or more efficient protocols. Joux [START_REF] Joux | A one round protocol for tripartite Diffie-Hellman[END_REF] notably constructed a one-round tripartite key exchange whose security requires the tripartite decision Diffie-Hellman assumption (or decision "Triffie-Hellman" assumption) which states that given group 1 elements g, g x , g y and g z no efficient algorithm can distinguish between g xyz and an element picked uniformly at random in G. Many generalizations of the decision Diffie-Hellman assumption were proposed (e.g. [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF][START_REF] Bresson | Provably secure authenticated group diffiehellman key exchange[END_REF]) and can be stated as follows: given an integer n and some specific values of the Naor-Reingold function, no efficient algorithm can distinguish another value of the Naor-Reingold function from an element picked uniformly at random in G. A salient example is the n-partite decision Diffie-Hellman assumption: given some elements g, g a1 , . . . , g an no efficient algorithm can distinguish between g a1...an and an element picked uniformly at random in G. therein). For the decision Diffie-Hellman assumption, it would be sufficient to know a trivariate polynomial f (X 1 , X 2 , X 3 ) over a finite field of small weight (even if it is of high degree) satisfying: f ([x], [y], [xy]) = 0, for all pairs (x, y) ∈ S for a large subset S ⊆ {0, . . . , -1} 2 . Typically, the complexity of a polynomial is measured by its degree, but a more accurate complexity measure could also be the number of monomials (or weight). Lower bounds on degree of polynomials interpolating Diffie-Hellman triples are also known (see [START_REF] Shparlinski | Cryptographic applications of analytic number theory[END_REF] and references therein) but there is no result on the weight of such polynomials.

Several number-theoretic properties and complexity measures have been studied for the Naor-Reingold pseudo-random functions over finite fields as well as over elliptic curves: distribution (see [START_REF] Ling | On the multidimensional distribution of the Naor-Reingold pseudo-random function[END_REF][START_REF] Shparlinski | On the Naor-Reingold pseudo-random function from elliptic curves[END_REF] and references therein), period (see [START_REF] Ibeas | On the period of the Naor-Reingold sequence[END_REF]), linear complexity (see [START_REF] Gómez | On the linear complexity of the Naor-Reingold sequence[END_REF][START_REF] Shparlinski | Linear complexity of the Naor-Reingold pseudo-random function[END_REF][START_REF] Shparlinski | On the linear complexity of the Naor-Reingold pseudorandom function from elliptic curves[END_REF][START_REF] Cruz | On the linear complexity of the Naor-Reingold sequence with elliptic curves[END_REF]) and non-linear complexity (see [START_REF] Banks | Non-linear complexity of the Naor-Reingold pseudo-random function[END_REF]). Recently [START_REF] Mefenza | Polynomial interpolation of the Naor-Reingold pseudo-random function[END_REF], the authors of the present paper proved lower bounds on the degree of polynomials interpolating the Naor-Reingold pseudo-random function at several points for fixed keys (over a finite field and over the group of points on an elliptic curve over a finite field). They left open the problem to give lower bounds on the degree of general multivariate polynomials that interpolate the Naor-Reingold function in several fixed points for many keys. The main goal of this paper is to give such lower bounds for the Naor-Reingold and the generalized Diffie-Hellman functions over a finite field (e.g. given g a1 , . . . , g an ∈ G, distinguish between g a1...an from an element picked uniformly at random in G [START_REF] Bresson | Provably secure authenticated group diffiehellman key exchange[END_REF] and other problems from the matrix Diffie-Hellman framework [?]). We prove that polynomials interpolating these functions (implicitly or explicitly) on a large set have degree and weight in O(1) (i.e. exponential in the so-called security parameter in the cryptographic context).

Our contributions. In order to break the security of the Naor-Reingold pseudorandom function, it would be sufficient to have an efficiently computable k-variate polynomial f (X 1 , . . . , X k ) over a finite field (of low weight) satisfying:

f [a x 1 ], . . . , [a x k ] = [a x k+1 ],
for all a = (a 1 , . . . , an) ∈ S for a large subset S ⊆ (F * ) n , for some k ≥ 1 and for some known values x 1 , . . . , x k+1 ∈ {0, • • • , 2 n -1}. One can easily see that this polynomial interpolation is a generalization of the polynomial interpolation of the computational Diffie-Hellman assumption in the case n = 2, k = 2, x 1 = (1, 0), x 2 = (0, 1) and x 3 = (1, 1). Adapting the known lower bounds on the polynomial interpolation on the discrete logarithm and the Diffie-Hellman Problem in subgroups of the multiplication group of a finite field (e.g. [21-25, 10, 11] and references therein), we prove that a low-weight multivariate polynomial cannot reveal information on the functions values. Using the same methods, we also prove that no low weight polynomial f over a finite field can satisfy: f ([a 1 ], . . . , [an], [a 1 . . . an]) = 0, for all a = (a 1 , . . . , an) ∈ S for a large subset S ⊆ (F * ) n . In particular, for n = 2, this means that a low weight polynomial cannot break the decision Diffie-Hellman assumption.

Preliminaries

Let p be an odd prime number and q a prime power of p. We denote by Fp the finite field with p elements and the elements of Fp are identified with the set of integers

{0, • • • , p -1}
and Fq an extension of the prime finite field Fp. Given g ∈ F * q with prime order (with | q -1) we can consider the Naor-Reingold pseudo-random function defined over G = g : fa

(x) = g a x = [a x ] ∈ G ⊂ F * q ,
for a secret key a = (a 1 , . . . , an) ∈ (F * ) n where as above x will denote indifferently an n-bit string (x 1 , . . . , xn) ∈ {0, 1} n or an integer x ∈ {0, 1, . . . , 2 n -1} (with x = n i=1 x i 2 i-1 ). In the following, we will use the following lemmas (see [START_REF] Kiltz | On the interpolation of bivariate polynomials related to Diffie-Hellman mapping[END_REF]) where the weight w(f ) (or sparsity) of a polynomial f (X 1 , . . . , Xn) ∈ Fq[X 1 , . . . , Xn] is the number of its non-zero coefficients.

Lemma 1 [ [START_REF] Kiltz | On the interpolation of bivariate polynomials related to Diffie-Hellman mapping[END_REF]] Let D be an integral domain, n ∈ N and f ∈ D[X 1 , . . . , Xn] a polynomial of total degree d with at least N zeros in T n with components in T . If f is not the zero polynomial, then we have

d ≥ N |T | n-1 .
Lemma 2 [ [START_REF] Kiltz | On the interpolation of bivariate polynomials related to Diffie-Hellman mapping[END_REF]] Let γ ∈ Fq be an element of order d, G the group generated by γ, n a positive integer, and f ∈ Fq[X 1 , . . . , Xn] be a nonzero polynomial of local degree at most d -1 in each variable with at least N zeros in G n . If f is not the zero polynomial, then we have

w(f ) ≥ d n d n -N .

Polynomial Interpolation

In this section, q is a prime power, n is an integer and g ∈ F * q is an element of prime order (with | q -1). We prove results on the multivariate polynomial interpolation of the Naor-Reingold functions over a finite field and generalized Diffie-Hellman problems. We consider polynomials that interpolate values of these functions for fixed values in {0, • • • , 2 n -1} and a large set of keys. First, we consider an interpolation by a polynomial with k variables, with k ≤ n.

Theorem 1 Let 1 ≤ k ≤ n be an integer. Let S ⊆ (F * ) n , with |S| = ( -1) n -s with |S| > k( -1) n-1 . Let x 1 , . . . , x k+1 ∈ {1, • • • , 2 n -1} be pairwise distinct and let f ∈ Fq[X 1 , . . . , X k ], be a polynomial satisfying: f [a x 1 ], . . . , [a x k ] = [a x k+1
], for all a = (a 1 , . . . , an) ∈ S.

(1)

If the elements x i , i ∈ {1, . . . , k} seen as vectors over F n 2 are linearly independent over

F 2 , then: deg(f ) ≥ -1 2 - s ( -1) n-1 and if deg Xi (f ) ≤ -1
2 , for all i ∈ {1, . . . , n}, we have

w(f ) ≥ k/2 2 1/2 ( k -( -1) k + 2s/( -1) n-k ) 1/2 .
In particular, for s = o( n ), we have deg(f ) = Ω( ) and and if deg Xi (f ) ≤ -1 2 , for all i ∈ {1, . . . , n}, we have w(f ) = Ω( k/2 ).

Proof For any i ∈ {1, . . . , k + 1}, we denote x i = x i 1 . . . x i n its binary representation and put xi = x i 1 . . . x i k 0 . . . 0 which is obtained from x i by considering the k first positions of its binary representation and replacing the n -k last positions by 0. We suppose without loss of generality that the elements xi , i ∈ {1, . . . , k} seen as vectors over F n 2 are linearly independent over F 2 . Since |S| > k( -1) n-1 , we have w(f ) ≥ 2 by the following claim:

Claim If w(f ) = 1 then (1) holds for at most k( -1) n-1 keys a ∈ (F * ) n . Proof If w(f ) = 1, then f is a monomial and there exists (α 1 , . . . , α k ) ∈ {0, . . . , - 1} k such that α 1 a x 1 + • • • + α k a x k = a x k+1 mod (where f is the monomial f (X 1 , . . . , X k ) = X α1 1 . . . X α k k ). We prove by induction on k that the number of a ∈ (F * ) n such that α 1 a x 1 + • • • + α k a x k = a x k+1 does not exceed k( -1) n-1 .
1. For k = 0, the equation a x k+1 = 0 has no solution and the statement is clearly true. 2. Otherwise, because x k+1 = x k , there exists j such that the j-th component of x k+1 is different from the j-th component of x k . Then the above equation can be written in the form A = Ba j where A and B do not depend on a j . If B = 0, then for any vector (a

1 , • • • , a j-1 , a j+1 , • • • , an) ∈ (F * ) n-1
, the value of a j is defined uniquely. If B = 0, then A = 0 and by induction, the number of (a

1 , • • • , a j-1 , a j+1 , • • • , an) ∈ (F * ) n-1 does not exceed (k -1)( -1) n-2 .
Therefore, the number of solutions does not exceed (k -1)

( -1) n-1 + ( - 1) n-1 = k( -1) n-1
, and the result follows.

There is some t ∈ {1, . . . , n} such that x k+1 t = 1 and let T 0 = {i : x i t = 1} ⊆ {1, . . . , k} that we denote T 0 = {i 1 , . . . , iv}, with i j < i j+1 for j ∈ {1, . . . , v -1}. Let

T = {(a 1 , . . . , a k ) ∈ (F * ) k : a = (a 1 , . . . , a k , b k+1 , . . . , bn) ∈ W } satisfies |T | ≥ ( -1) k -2s/( -1) n-k
. For all a 0 = (a 1 , . . . , a k ) ∈ T , putting a = (a 1 , . . . , a k , b k+1 , . . . , bn), we have:

         f [a x 1 ], . . . , [a x k ] = [a x k+1 ] f [a x 1 ], . . . , [a x i 1 -1
], [2a

x i 1
], [a

x i 1 +1 ], . . . . . . , [a x iv -1 ], [2a x iv ], [a x iv +1 ], . . . , [a x n ] = [2a x k+1
] Since the elements xi , i ∈ {1, . . . , k} seen as vectors over F n 2 are linearly independent over F 2 , one can verify that the set

T 1 = [a x 1 ], . . . , [a x k
] ∈ (F * q ) k : a = (a 0 , b k+1 , . . . , bn) ∈ W, and a 0 ∈ T is of the same cardinality as T . Hence the polynomial

F (X 1 , . . . , X k ) = f (X 1 , . . . , X 2 i1 , . . . , . . . , X 2 iv , . . . , X k ) -f 2 (X 1 , . . . , X k )
has at least |T | ≥ ( -1) k -2s/( -1) n-k zeros. Since w(f ) ≥ 2, one can see that F is a nonzero polynomial and deg F ≤ 2 deg f . By Lemma 1, we obtain:

deg(f ) ≥ -1 2 - s ( -1) n-1 .
Furthermore if deg Xi (f ) ≤ -1 2 , for all i ∈ {1, . . . , n}, and since w(F ) ≤ 2w(f ) 2 , then by applying Lemma 2 we have:

w(f ) ≥ k/2 2 1/2 ( k -( -1) k + 2s/( -1) n-k ) 1/2 .
Remark 1 The previous proof uses only the fact that the xi are linearly independent and we need this assumption to prove that the set T 1 has the same cardinality as T . Note that if xi = 2 n+i-k-1 for i ∈ {1, . . . , k}, then the set T 1 is of the same cardinality as T and Theorem 1 holds. Theorem 1 is more general and applies to numerous settings. For instance for k = 3, x1 = 1000 . . . 0, x2 = 1100 . . . 0 and x3 = 1010 . . . 0, the set T 1 is of the same cardinality as T and the vectors x1 , x2 , x3 are linearly independent.

Remark 2 In Equation (1), if we replace each [a x i

] by X i , for i ∈ {1, . . . , k + 1}, the polynomial f (X 1 , . . . , X k ) -X k+1 has k + 1 indeterminates and has at least N zeros in G k+1 , where N is the cardinality of the set

(a x 1 , . . . , a x k+1 ) ∈ (F * ) k+1 : a ∈ S .
We do not know a lower bound on N but obviously we have N ≤ ( -1) k+1 . By applying Lemma 1, we obtain

deg(f ) ≥ N ( -1) k .
If the vectors x i , for i ∈ {1, . . . , k} are linearly independent, then N ≥ ( -1) n . Thus we have n ≤ k + 1 and deg(f ) ≥ ( -1) n-k . The result is non-trivial only for k = n -1 (and in this case we obtain deg(f ) ≥ -1) but is much less general than Theorem 1.

Remark 3 Note that all the previous results on the polynomial interpolation of the Diffie-Hellman function dealt with k = n = 2, x 1 = 10, x 2 = 01 and x 3 = 11 while our results are more general and holds for many k, n and x i , for i ∈ {1, . . . , k}. In the special case, k = n = 2, x 1 = 10, x 2 = 01, x 3 = 11 and s = o( n ), Mahassni and Shparlinski obtained in [START_REF] Mahassni | Polynomial representations of the Diffie-Hellman mapping[END_REF] the bound deg(f ) ≥ /128 while we obtain the bound deg(f ) ≥ /2. The remainding theorems of the paper cannot be compared with the known results on the polynomial interpolation of the Diffie-Hellman map (since k > n).

Now we consider an interpolation by a polynomial with k variables and k > n with some technical conditions on the input values

x i ∈ {0, • • • , 2 n -1} for i ∈ {1, . . . , k}.
Theorem 2 Let k > n be some integer. Let S ⊆ (F * ) n , with |S| = ( -1) n -s. Let x 1 , . . . , x k+1 ∈ {0, • • • , 2 n -1} be pairwise distinct such that x 1 = 2 n-1 = (1, 0, . . . , 0),

x k+1 1 = 1 and x i 1 = 0 for i ∈ {2, . . . , k} and let f ∈ Fq[X 1 , . . . , X k ], with k > n be a polynomial satisfying:

f [a x 1 ], . . . , [a x k ] = [a x k+1
], for all a = (a 1 , . . . , an) ∈ S.

We have

deg(f ) ≥ -1 2 - s ( -1) n-1 .
Proof Let W be the set of vectors a ∈ (F * ) n such that a = (a 1 , . . . , an) ∈ S, (a 1 + 1, . . . , an) ∈ S and a = (1, a 2 , . . . , an) satisfies a

x k+1
= α mod for all α ∈ {1, . . . , d}, where d denotes the degree of f .

Claim We have |W | ≥ ( -1) n -2s -deg(f )( -1) n-1 .
Proof It is worth noting that, since k > n, we cannot prove Theorem 2 in the same way as we proved Theorem 1. Let α ∈ {1, . . . , d}, the number of a ∈ (F * ) n such that a

x k+1 = α mod does not exceed ( -1) n-1 . Indeed, since x k = x 1 , there exists j ∈ {2, . . . , n} such that x k+1 j = 1, then for any vector (a 1 , . . . , a j-1 , a j+1 , • • • , an) ∈ (F * ) n-1 , the value of a j is defined uniquely by this equation. Since the number of vectors a = (a 1 , . . . , an) ∈ S such that (a 1 + 1, . . . , an) / ∈ S does not exceed s, the result follows.

By the pigeonhole principle, there exists

b = (1, b 2 , . . . , bn) ∈ (F * ) n such that the set T = {a 1 ∈ F : a = (a 1 , b 2 , . . . , bn) ∈ W } satisfies |T | ≥ -1 -deg(f ) - 2s ( -1) n-1 .
Then for all a 1 ∈ T , putting a = (a 1 , b 2 , . . . , bn), we have:

   f [a 1 ], [b x 2 ] . . . , [b x k ] = [a x k+1 ] f [a 1 + 1], [b x 2 ], . . . , [b x k ] = [(a 1 + 1, b 2 , . . . , bn) x k+1 ] = [b x k+1 ].[a x k+1 ]
We have for all

a 1 ∈ T f g.[a 1 ], [b x 2 ], . . . , [b x k ] -[b x k+1 ]f [a 1 ], [b x 2 ] . . . , [b x k ] = 0
and the polynomial

F (X) = f gX, [b x 2 ], . . . , [b x k ] -[b x k+1 ]f X, [b x 2 ] . . . , [b x k ] has at least -1 -deg(f ) - 2s ( -1) n-1 zeros. The polynomial f (X, [b x 2 ], . . . , [b x k ]
) is a nonzero polynomial by the first equation of the previous system and has degree smaller than deg(f ). Let d 0 its degree, then b x k+1 = d 0 mod by construction of W and it follows that the leading monomial of F is nonzero which implies that the polynomial F is nonzero. We also have deg(F ) ≤ deg(f ) and hence, by Lemma 1, we obtain:

deg(f ) ≥ -1 -deg(f ) - 2s ( -1) n-1 ,
and the result follows.

Remark 4 The technical condition on x 1 seems necessary since using another x 1 , we obtain the polynomial

F (X) = f X 2 , [b x 2 ], . . . , [b x k ] -f 2 X, [b x 2 ] . . . , [b x k ] ,
and it is unknown how to show that this polynomial is nonzero (without adding new technical conditions on the b's and thus on the a's).

Theorem 2 can be applied to give lower bounds on the degree of interpolating polynomials for several generalized Diffie-Hellman problems (with k > n variables) from [START_REF] Bresson | Provably secure authenticated group diffiehellman key exchange[END_REF].

Since the weight of a polynomial is a more discerning complexity estimate, we now prove a lower bound on the weight of an interpolation by a polynomial with k variables and k > n (and without any condition on the input values

x i ∈ {0, • • • , 2 n -1} for i ∈ {1, . . . , k}). Theorem 3 Let k > n be some integer. Let S ⊆ (F * ) n , with |S| = ( -1) n -s. Let x 1 , . . . , x k+1 ∈ {1, • • • , 2 n -1} be pairwise distinct and let f ∈ Fq[X 1 , . . . , X k ] be a polynomial satisfying: f [a x 1 ], . . . , [a x k ] = [a x k+1
], for all a = (a 1 , . . . , an) ∈ S, for some different values x 1 , . . . ,

x k+1 ∈ {1, • • • , 2 n -1}. Then w(f ) ≥ -3 - s ( -1) n-1 2 + 2k + s ( -1) n-1 1/2 .
Proof Let I = {i ∈ {1, . . . , k} : x i n = 1} that we denote I = {i 1 , . . . , iv} with

i 1 < i 2 < • • • < iv. Let A = {α i = (α 1 i , . . . , α v i ) ∈ {0, . . . , deg(f )} v }
be a set of cardinality at most w(f ) which will be given explicitly later in the proof and W A be the set of vectors a ∈ (F * ) n such that:

1. a = (a 1 , . . . , an) ∈ S 2. a satisfies α 1 i a x i 1 -1 + • • • + α v i a x iv -1 = a x k+1 -1 for all α i ∈ A Claim We have |W A | ≥ ( -1) n -T 0 , where T 0 = s + w(f )k( -1) n-1 .
Proof For a fixed tuple α i ∈ A, by proceeding exactly as in the proof of Claim 1 one can prove by induction in v that the number of a ∈ (F * ) n such that α 1 i a

x i 1 -1 + • • • + α v i a x iv -1 = a x k+1 -1 does not exceed v( -1) n-1 . Since the cardinality of A is at most w(f ) and v ≤ k, we thus have |W A | ≥ |S| -kw(f )( -1) n-1 .
There exists by the pigeonhole principle b = (b 1 , . . . , b n-1 , 1) ∈ (F * ) n such that

T = {an ∈ F : a = (b 1 , . . . , b n-1 , an) ∈ W A } satisfies |T | ≥ -1 - T0 ( -1) n-1 .
Then for all an ∈ T , we have:

f [b x 1 ], . . . , [b x i 1 -1 ], [b x i 1 an], [b x i 1 +1 ], . . . . . . , [b x iv -1 ], [b x iv -1 an], [b x iv +1 ], . . . , [b x k ] = [b x k+1 -1 an].
Let

H(X) = f [b x 1 ], . . . , [b x i 1 -1 ], X b x i 1 -1 , [b x i 1 +1 ], . . . . . . , , [b x iv -1 ], X b x iv -1 , [b x iv +1 ], . . . , [b x k ] -X b x k+1 -1
and K(X) the polynomial obtained from H(X) by reducing the exponents of every monomial modulo . If we choose A to be the set of vectors obtained from the multivariate polynomial f by considering the monomials with variables X i1 , . . . , X iv from each monomial of f , then A is of cardinality at most w(f ) and does not depend on b. One can see that K(X) is a nonzero polynomial by the choice of b and has degree less than with at least |T | zeros. Hence by Lemma 2, we obtain:

w(f ) + 1 ≥ w(K) ≥ 1 + T0 ( -1) n-1
, and (w(f ) + 1) 2( -1) n-1 + s + w(f )k( -1) n-1 ≥ ( -1) n . We thus have:

w(f ) 2 2( -1) n-1 + s + 2k( -1) n-1 ≥ ( -1) n -2( -1) n-1 -s,
and the result follows.

Theorem 3 gives a lower bound on the weight of explicit polynomials interpolating the Naor-Reingold pseudo-random function and it immediately gives a lower bound on the weight of explicit polynomials interpolating the n-partite Diffie-Hellman problem by some well chosen inputs:

Corollary 1 Let S ⊆ (F * ) n , with |S| = ( -1) n -s. Let f ∈ Fq[X 1 , . . . , Xn] be a polynomial satisfying f ([a 1 ], . . . , [an]) = [a 1 . . . an] for all a = (a 1 , . . . , an) ∈ S. We have w(f ) ≥ -3 - s ( -1) n-1 2 + 2n + s ( -1) n-1 1/2 .
The next theorem extends the previous approach and gives a lower bound on the weight of implicit polynomials interpolating the generalized Diffie-Hellman problem.

Theorem 4 Let S ⊆ (F * ) n , with |S| = ( -1) n -s. Let f ∈ Fq[X 1 , . . . , X n+1 ] be a polynomial satisfying: f ([a 1 ], . . . , [an], [a 1 . . . an]) = 0, for all a = (a 1 , . . . , an) ∈ S, then

w(f ) ≥ ( -1) n-1 2( -1) n-1 + s 1/2 . Proof Let (α, β) ∈ {0, . . . , deg(f )} 2 } with (α, β) = (0, 0). Let A = {(α , β ) ∈ {0, . . . , deg(f )} 2 }
be a set of cardinality at most w(f ) with (α, β) / ∈ A and let W A be the set of vectors a ∈ (F * ) n such that:

1. a = (a 1 , . . . , an) ∈ S 2. a satisfies α + β(a 2 . . . an) = α + β (a 2 . . . an) mod for all (α , β ) ∈ A Claim We have |W A | ≥ ( -1) n -s -w(f )( -1) n-1 .

Proof Given (α , β ) ∈ A, the number of a ∈ (F * ) n such that α + β(a 2 . . . an) = α + β (a 2 . . . an) mod does not exceed ( -1) n-1 . Indeed, we have α -α + (β -β )(a 2 . . . an) = 0 mod , and we can easily see that β -β = 0 mod (since otherwise, we have α -α = 0 mod ). Therefore, for any vector (a 1 , a 3 , • • • , an) ∈ (F * ) n-1 , the value of a 2 is defined uniquely.

Since the total number of couples (α , β ) does not exceed w(f ), the number of a ∈ S such that a / ∈ W A does not exceed w(f )( -1) n-1 .

There Let H(X) = f (X, [b 2 ], . . . [bn], X b2...bn ) and K(X) the polynomial obtained from H(X) by reducing the exponents of every monomial modulo . If we choose A independent of b and of cardinality at most w(f ), as in the proof of Theorem 3 (but this time with variables X 1 and X n+1 ) , then K(X) is not a zero polynomial by the choice of b and has degree less than with at least |T | zeros. Hence by Lemma 2, we obtain:

w(f ) ≥ w(K) ≥ 1 + w(f ) + s ( -1) n-1
, and the result follows.

Conclusion

In this paper, we proved lower bounds on the degree of multivariate polynomial representations of the Naor-Reingold function in several fixed points for many keys over a finite field. We also proved such bounds on the generalized Diffie-Hellman function over a finite field. It is interesting to extend these results to the group of rational points of an elliptic curve over a finite field. Using techniques from [START_REF] Mefenza | Polynomial interpolation of the Naor-Reingold pseudo-random function[END_REF], one can extend the results of Theorem 2 to this setting but is unclear how to adapt the techniques from Theorem 1, Theorem 3, and Theorem 4 for elliptic curves. Another natural open problem is to generalize our bounds to a smaller set of keys.

W

  = a ∈ (F * ) n : a = (a 1 , . . . , an) ∈ S and (a 1 , . . . , a t-1 , 2a t , a t+1 , . . . , an) ∈ S , then by the the union bound, |W | ≥ ( -1) n -2s. By the pigeonhole principle, there exists (b k+1 , . . . , bn) ∈ (F * ) n-k such that the set

  exists by the pigeonhole principle b = (b 2 , . . . , bn) ∈(F * ) n-1 such that T = {a 1 ∈ F : a = (a 1 , b) ∈ W A } satisfies |T | ≥ -1 -w(f ) -s ( -1) n-1 .Then for all a 1 ∈ T , we have:f ([a 1 ], [b 2 ], . . . [bn], [a 1 b 2 . . . bn]) = 0.

Acknowledgments. The authors are supported in part by the French ANR JCJC ROMAnTIC project (ANR-12-JS02-0004) and by the Simons foundation Pole PRMAIS.