Charles Bouillaguet
email: charles.bouillaguet@lip6.fr

Florette Martinez
email: florette.martinez@lip6.fr

Damien Vergnaud
email: damien.vergnaud@lip6.fr

Cryptanalysis of Modular Exponentiation Outsourcing Protocols

Keywords: Secure outsourcing, Modular exponentiation, Privacy, Verifiability, Cryptanalysis

Public-key cryptographic primitives are time-consuming for resource-constrained devices. A classical problem is to securely offload group exponentiations from a (comparatively) weak device -the client -to an untrusted more powerful device -the server. A delegation protocol must usually meet two security objectives: privacy -the exponent or the base should not be revealed to a passive adversary -and verifiability -a malicious server should not be able to make the client accept an invalid value as the result of the delegated computation. Most proposed protocols relies on a secret splitting of the exponent and the base and a considerable amount of literature has been devoted to their analysis. Recently, Su, Zhang and Xue [The Computer Journal, 2020] and Rangasamy and Kuppusamy [Indocrypt 2018] proposed outsourcing protocols for modular exponentiations. They claim that their protocols achieve security (privacy and verifiability). We show that these claims are flawed and that their schemes are broken beyond repair. They remain insecure even if one increases significantly the proposed parameters (and consequently the protocols computational and communication complexities). Our attacks rely on standard lattice-based cryptanalytic techniques, namely the Coppersmith methods to find small integer zeroes of modular multivariate polynomials and simultaneous Diophantine approximation methods for the so-called approximate greatest common divisor problem.

INTRODUCTION

Group exponentiation is a fundamental operation in public-key cryptography as it is used in RSA-based and discrete-logarithm based protocols. Since the computational resources can be very limited on certain devices, it is natural, as most of the devices are online or directly connected to a powerful device, to consider securely delegating some sensitive and costly exponentiation to an untrusted device capable of carrying out large operations. A delegation protocol must usually meet two security objectives: privacy -the exponent or the base should not be revealed to a passive adversary -and verifiability -a malicious server should not be able to make the client accept an invalid value as the result of the delegated computation This paper presents several lattice-based attacks on two group exponentiation outsourcing protocols recently proposed by Su, Zhang and Xue [START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF] and Rangasamy and Kuppusamy [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF]. In both cases, the proposed protocols are simple and efficient and the authors claim that they achieve security (privacy and verifiability). We show that these claims are flawed and that their schemes are broken beyond repair.

Prior Work on Exponentiation Outsourcing Protocols

The problem of outsourcing cryptographic operations has already received a lot of attention but there has been a recent regain of interest with the development of mobile technologies. In 2005, Hohenberger and Lysyanskaya [START_REF] Hohenberger | How to securely outsource cryptographic computations[END_REF] proposed formal security definitions for securely outsourcing computations from a computationally limited device, called the client, to untrusted helpers, called the servers. Delegating a cryptographic operation presents many risks since they usually involve sensitive information which should not be revealed to

The Computer Journal, Vol. ??, No. ??, ????

Ch. Bouillaguet, F. Martinez and D. Vergnaud potential adversaries. Moreover, since the servers are not fully trusted, a delegation protocol should enable clients to verify the correctness of the result returned by the server with high probability. Obviously, to be of practical interest, these delegation protocols must have a computational cost for the client lower than that of the delegated computation.

Hohenberger and Lysyanskaya notably presented an efficient scheme to securely outsource group exponentiation to two, possibly dishonest, servers that are physically separated (and do not communicate). Since this separation of the two servers is actually a strong assumption, recent works focus on outsourcing group exponentiation to a single computationally stronger server. It has been a very active research topic in which numerous protocols have been proposed [START_REF] Matsumoto | Speeding up secret computations with insecure auxiliary devices[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] 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] Cavallo | Efficient and secure delegation of group exponentiation to a single server[END_REF][START_REF] Crescenzo | Secure delegation to a single malicious server: Exponentiation in RSA-type groups[END_REF]) and many of these proposals were subsequently broken [START_REF] Nguyen | On the insecurity of a server-aided RSA protocol[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][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF][START_REF] Mefenza | Cryptanalysis of server-aided RSA protocols with private-key splitting[END_REF]).

In 2018, Rangasamy and Kuppusamy [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF] presented a protocol named MExpSOS for outsourcing modular exponentiations to a single, malicious computational resource. Their protocol is presented for delegation of exponentiation modulo a prime number as well as modulo an RSA modulus. It is simple and efficient, and does not require any pre-computation from the client. Rangasamy and Kuppusamy claimed that their scheme achieve the two fundamental security properties, namely privacy of inputs and verifiability of outputs, and claimed that it is the "best to-date outsourcing scheme for single-server case". They also proposed another scheme based on similar ideas for simultaneous exponentiations.

In 2020, Su, Zhang and Xue [START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF] presented another protocol called MCExp for outsourcing exponentiations modulo an RSA modulus to a single, malicious computational resource. It requires pre-computation from the client but relies on similar ideas to those of the MExpSOS protocol. It is also simple and efficient and Su et al. claimed that it achieves privacy and verifiability. They also proposed another scheme for outsourcing simultaneous composite modular exponentiations.

Prior Work on Lattice-Based Cryptanalysis

Some attacks we present in the paper rely on Coppersmith's methods, a classical technique in latticebased cryptanalysis. These methods have been introduced in 1996 by Coppersmith to find small integer zeroes of modular polynomials of one or two variables [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]. Since their introduction, many generalizations of the methods have been proposed to deal with more variables (e.g., [START_REF] Howgrave-Graham | Finding small roots of univariate modular equations revisited[END_REF][START_REF] Blömer | A tool kit for finding small roots of bivariate polynomials over the integers[END_REF][START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants[END_REF][START_REF] Herrmann | Attacking power generators using unravelled linearization: When do we Ch[END_REF][START_REF] Bauer | Inferring sequences produced by nonlinear pseudorandom number generators using Coppersmith's methods[END_REF]) or multiple moduli (e.g., [START_REF] May | Solving systems of modular equations in one variable: How many RSAencrypted messages does eve need to know?[END_REF][START_REF] May | Implicit factoring: On polynomial time factoring given only an implicit hint[END_REF]). In this paper, we rely on variants proposed Ernst, Jochemsz, May and de Weger in 2005 [START_REF] Ernst | Partial key exposure attacks on RSA up to full size exponents[END_REF] for specific trivariate polynomial equations of small degree. The techniques from Ernst et al. are currently the best known for solving the particular equations we are studying in this article and any improvement in these techniques would provide an immediate improvement to our attacks.

We also present attacks based on another standard lattice-based cryptanalytic technique from simultaneous Diophantine approximation for the approximate greatest common divisor problem [START_REF] Lagarias | The computational complexity of simultaneous diophantine approximation problems[END_REF][START_REF] Howgrave-Graham | Approximate integer common divisors[END_REF][START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF]). This computational problem is to determine a secret integer p when one is given many samples of the form x i = p • q i + r i for small error terms r i . A simple approach for solving it relies on a simple lattice-based algorithm due to Lagarias [START_REF] Lagarias | The computational complexity of simultaneous diophantine approximation problems[END_REF] for simultaneous Diophantine approximation. The technique was first proposed by Howgrave-Graham in [START_REF] Howgrave-Graham | Approximate integer common divisors[END_REF], then expanded in [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF].

Contributions

We prove that the protocols MExpSOS and MCExp as proposed in [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF] and [START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF] are insecure. Both schemes do not achieve the claimed privacy and verifiability security properties (without increasing the size of the parameters to the point of making the delegation protocol more expensive than the modular exponentiation computation itself).

We first underline a major security break in MCExp from a single execution of the protocol, as two of its parameters are too small to resist exhaustive search. This allows us to obtain readily a multiple of the Euler totient function ϕ(N ) of the underlying RSA modulus N and then using a classical algorithm due to Rabin [START_REF] Rabin | Digitalized signatures and publickey functions as intractable as factorization[END_REF] to factor N and obtain the (supposedly) secret base and exponent of the delegated exponentiation.

We then consider different ways of fixing the scheme MCExp (by increasing only one of the small parameters, then both of them). Using Coppersmith's methods, we show that even the modified schemes are also broken, from a single execution of the protocol, for a wide range of parameters. For each variant, we present a simple attack that allows to factor N and retrieve the base and exponent of the delegated exponentiation. This information is sufficient to also break the verifiability property of MCExp.

As a final nail in MCExp's coffin, we present an even more devastating attack against the modified protocol when the adversary can passively eavesdrop several runs of the delegation protocol for the same exponent. This is a particularly important use-case for the RSA primitive in which the client may want to delegate the computation of signatures for a fixed secret signing exponent. Our attack relies methods for the approximate greatest common divisor problem. The methods used on this attack can also be used to improve the attack by Mefenza and Vergnaud [START_REF] Mefenza | Cryptanalysis of server-aided RSA protocols with private-key splitting[END_REF] on a server-aided RSA protocol with additive key splitting in the case where the adversary has access to several delegations. Finally, since MExpSOS is very close to the modified MCExp protocol, we can also apply our attack and show that MExpSOS does not achieve privacy and verifiability.

The remainder of this paper is organized as follows. Section 2 introduces the notations, the security definitions and describes the MCExp and MExpSOS outsourcing computation schemes. Section 3 reviews the lattice-based cryptanalytic techniques we used in the paper. Our attacks against the MCExp protocol when the client outsources a single exponentiation are described in Section 4. Eventually, Section 5 presents our devastating attacks against MExpSOS and MCExp in the case where the adversary is able to observe more than one exponentiation delegation.

PRELIMINARIES

Notations

All logarithms are base 2. We denote the security parameter by λ ∈ N which is given as input to all algorithms in unary form 1 λ . Algorithms are randomized unless otherwise stated, and PPT stands for "probabilistic polynomial-time," in the security parameter. We might use the terms "efficient" and PPT interchangeably. We denote random sampling from a finite set X according to the uniform distribution with x $ ← -X. We also use the symbol $ ← -for assignments from randomized algorithms, while we denote assignment from deterministic algorithms and calculations with the symbol ←. If n is an integer, we write Z n for the ring Z/nZ, Z * n for the invertible elements of Z n and ϕ(n) for the Euler totient function of n (with ϕ(n) = #Z * n ). As usual, the notation poly(λ) denotes any polynomial in λ and f ∈ negl(λ) denotes a function that decreases faster than the inverse of any polynomial in λ; such functions are called negligible.

Exponentiation Delegation: Definitions

In the following, we consider group exponentiation protocols in two different settings, namely public prime-order groups and in secret composite order groups. To simplify the exposition3 we consider only exponentiation in the multiplicative group of the residue ring Z N for some integer N ≥ 2. These settings are formalized thanks to a PPT algorithm GrpGen which is given as input a security parameter λ and outputs a pair par = (N, ϕ(N )) where log(N ) = poly(λ):

• we say that GrpGen is a prime-order group generator if for all λ ∈ N and all par = (N, ϕ(N )) output by GrpGen(1 λ ), N is a prime number (and thus ϕ(N ) = N -1); • we say that GrpGen is an RSA group generator if for all λ ∈ N and all par = (N, ϕ(N )) output by GrpGen(1 λ ), N = pq is the product of two distinct odd primes p and q (and thus ϕ(N ) = (p-1)(q-1)).

We consider the delegation of an exponentiation as a 2-party PPT interactive protocol between a client C and a server S. It is natural to assume that C knows the group Z * N in which it needs to perform an exponentiation and following [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF][START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF], we also assume that it knows its order ϕ(N ). We assume that S does not know the group Z * N a priori ; this approach somehow contradicts Kerckhoff's principles [START_REF] Kerckhoffs | La cryptographie militaire[END_REF] but it is adopted in [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF]. Anyway, we will show that the schemes from [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF][START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF] are insecure even with this very strong assumption.

Given a security parameter λ, a pair par = (N, ϕ(N )) output by GrpGen(1 λ ), u ∈ Z N and a ∈ Z ϕ(N ) , we denote as (y C , y S , tr) ← (C(1 λ , par, (a, u)), S(1 λ )) the protocol at the end of which C gets y C and S gets y S and the string tr denotes the full transcript of the interaction.

In the present paper, the protocols investigated are all of the same form: (1) C performs some private computation and then sends to S one or several bases and their corresponding exponents and a modulus (possibly different from N ) to the server; (2) S then performs the required exponentiations (whose bases, exponents and modulus were sent to him by C) and sends back the obtained values to C; (3) C finalizes the computations thanks to the values sent by S. The protocols only require one round of communication, their transcripts tr thus consist only of the strings sent at the end of steps (1) and ( 2) and the output of S is y S = ∅ the empty string.

The correctness requirement for delegation of a exponentiation means that when the server and the client follow honestly the protocol, the client's output is actually the expected exponentiation. Definition 2.1 (Correctness). Let λ be a positive integer. We say that (C, S) satisfies correctness if

Pr   yC = u a par = (N, ϕ(N )) ← GrpGen(1 λ ), u $ ← -ZN , a $ ← -Z ϕ(N ) , (yC, yS , tr) ← (C(1 λ , par, a, u), S(1 λ ))    = 1.
We define two (weak) security notions that we call instance-hiding and exponent-hiding and which are variants of the similar notion used in [START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF]. They formalize the idea that a passive adversary should not be able to retrieve the base and the exponent or the exponent (respectively) used in one or several runs of the delegation protocol. Exponent-hiding is naturally weaker than instance-hiding. Both notions are weaker than the indistinguishability notion from [START_REF] Cavallo | Efficient and secure delegation of group exponentiation to a single server[END_REF][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF] which is itself weaker than the simulationbased security notion from [START_REF] Hohenberger | How to securely outsource cryptographic computations[END_REF]. The protocols from [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF] and [START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF] were claimed to achieve the latter notion but we will actually show that they do not even achieve our weak instance-hiding and exponent hiding security properties (respectively).

The probabilistic computational experiments described in Figure 1 provide a formal description of these security notions. For the instance-hiding no-

The Computer Journal, Vol. ??, No. ??, ????

Ch. Bouillaguet, F. Martinez and D. Vergnaud

Experiment Exp ih (A, C, λ) par = (N, ϕ(N )) ← GrpGen(1 λ ) (a, u) $ ← -Z ϕ(N ) × Z N i ← 0, tr 0 ← ∅ (α, ch base, ch exp, aux, (a 0 , u 0 )) ← A(1 λ , par) while α = stop do if ch base = true then u i ← u if ch exp = true then a i ← a (y i , (α, ch base, ch exp, aux, (a i+1 , u i+1 )), tr i ) ← (C(1 λ , par, (a i , u i )), A(aux)) i ← i + 1 Return 1 if (a i , u i ) = (a, u) and 0 otherwise Experiment Exp eh (A, C, λ) par = (N, ϕ(N )) ← GrpGen(1 λ ) a $ ← -Z ϕ(N ) i ← 0, tr 0 ← ∅ (α, ch exp, aux, (a 0 , u 0 )) ← A(1 λ , par) while α = stop do if ch exp = true then a i ← a (y i , (α, ch exp, aux, (a i+1 , u i+1 )), tr i ) ← (C(1 λ , par, (a i , u i )), A(aux)) i ← i + 1 Return 1 if a i = a and 0 otherwise FIGURE 1.
Random Experiment for Instance-Hiding and Exponent-Hiding Security Notions tion, given a residue group description (N, ϕ(N )) output by GrpGen(1 λ ) for some security parameter λ, a base u ∈ Z N and an exponent a ∈ Z ϕ(N ) are picked uniformly at random. The adversary A is then allowed to run the delegation protocol multiple times with arbitrary inputs of its choice (a i , u i ) in such a way that it can set a i = a (if ch exp = true) or u i = u (if ch base = true). Setting both flags to true, the delegation protocol is run on the input challenge (a, u) and setting both flags too false, the delegation protocol is run on some instance completely chosen by A (but it may obtain some information from such executions). The memory of the adversary for these multiple executions is stored in the variable aux. Eventually, the adversary A succeeds in this experiment if, when it decides to stop by setting the flag α to stop, it outputs the challenge pair (a, u). The exponent-hiding security notion is defined similarly but focuses only on the exponent.

Definition 2.2 (Instance-hiding and Exponent-hiding). Let GrpGen be a group generator and let (C, S) be a client-server protocol for a delegated computation of exponentiation for GrpGen. Let τ : N → N and ε : N → [0, 1] be two functions. We say that (C, S) satisfies (τ, ε)-instance-hiding ( resp. (τ, ε)-exponenthiding) if, for any algorithm A, it holds that for all integer λ ∈ N

Pr[ν = 1|ν ← Exp ih (A, C, λ)] ≤ ε(λ) ( resp. P r[ν = 1|ν ← Exp eh (A, C, λ)] ≤ ε(λ) )
where Exp ih (A, C, λ) ( resp Exp eh (A, C, λ)). is the computational random experiment described in Figure 1 in which A runs in time at most τ (λ).

The interactive protocol (C, S) is deemed instancehiding-secure ( resp. exponent-hiding-secure) if for all polynomial τ : N → N and all ε : N → [0, 1], if (C, S) does not satisfy (τ, ε)-instance-hiding ( resp. (τ, ε)exponent-hiding), then ε is negligible.

Another important security definition called verifiability requires that the client should not accept a wrong value for the exponentiation which is delegated to the server. A delegation protocol that does not ensure verifiability may cause severe security problems (in particular if the exponentiation computation occurs in the verification algorithm of some authentication protocol).

Definition 2.3 (Verifiability).

Let GrpGen be a group generator and let (C, S) be a client-server protocol for a delegated computation of exponentiation for GrpGen. Let τ : N → N and ζ : N → [0, 1] be two functions. We say that (C, S) satisfies (τ, ζ)-verifiability if, for any algorithm A , it holds that for all integer λ ∈ N,

Pr     yC = u a par = (N, ϕ(N )) ← GrpGen(1 λ ), u $ ← -ZN , a $ ← -Z ϕ(N ) , (yC, yS , tr) ← (C(1 λ , par, a, u), A(1 λ ))     ≥ ζ(λ).
where A runs in time at most τ (λ).

In practice, it is actually important to achieve a stronger notion of verifiability in which the adversary is allowed to run several executions of the delegation protocol with the client (for the same parameters par = (N, ϕ(N ))) before trying to make them accept a wrong value in a subsequent execution. We say that (C, S) satisfies (τ, ζ)-strong verifiability if when A's total running time is upper-bounded by τ (λ) (over all their executions), then the probability that C outputs an erroneous value for u a is at least ζ(λ).

Exponentiation Delegation: Protocols

In this section, α, β, γ ≥ 0 denote real parameters specifying the sizes of various variables in the delegation protocols.

We first provide a short description of the classical "textbook" RSA public-key encryption scheme [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]: Key Generation: On input a parameter λ ∈ N, the algorithm picks uniformly at random two distinct prime numbers p and q of bit-length λ. It then computes N = pq and ϕ(N ) = (p -1)(q -1) the Euler's totient function of N . It picks an integer e ∈ {1, . . . , ϕ(N )} coprime with ϕ(N ) and computes the integer d ∈ {1, . . . , ϕ(N )} such that ed ≡ 1 mod ϕ(N ).

The key-generation algorithm outputs (N, e) as the public-key and (N, d) as the private key.

Encryption: To encrypt a plaintext m ∈ Z N for a public key (N, e), the encryption algorithm outputs c = m e mod N .

Decryption: To decrypt a ciphertext c ∈ Z N with a private key (N, d), the decryption algorithm outputs m = c d mod N .

The computation of m = c d mod N in the decryption algorithm requires O(log d) = O(log N ) multiplications in Z N . In some settings, this is too costly for a weak client and so the client can delegate part of this computation to a more powerful server. Obviously, the client wants to do so without revealing its private key d to the server.

RSA Delegation with Additive Splitting

In the server-aided protocol with additive splitting (see Figure 2), the client picks uniformly at randomly k in {1, . . . , N α } and s in {1, . . . , N β }, and computes the integer

A = d -s + k • ϕ(N ).
The client then sends c, A and N to the server which computes m = c A mod N and sends it back to the client. The client eventually computes and outputs m = m • c s mod N as the decryption of c.

The number of modular multiplications to be performed by the client is proportional to the bit-length of s (and thus the smaller is β, the more efficient is the delegation protocol). In this protocol, the base m is sent in clear to the server, so the instance-hiding and exponent-hiding security notions are identical. Since the value returned by the server is not checked in any way, the protocol does not achieve verifiability. Mefenza and Vergnaud [START_REF] Mefenza | Cryptanalysis of server-aided RSA protocols with private-key splitting[END_REF] pointed out that the best known attack on RSA with partial key exposure due to Joye and Lepoint [START_REF] Lepoint | Partial key exposure on RSA with private exponets larger than n[END_REF] can be used to attack the protocol with a single run of the delegation protocol (see below).

The Su-Zhang-Xue (MCExp) Protocol

Recently, Su, Zhang and Xue [START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF] presented a protocol called MCExp for privately and verifiably outsourcing a modular exponentiation u a mod N where N is an RSA modulus, a is some private exponent (but not necessarily the inverse of a public value modulo ϕ(N ) as in the previous section) and u is some private base.

In the MCExp protocol, the client picks two random secret values r, s in {2, . . . , 11}, and two random integers k 1 and k 2 of unspecified size. We assume that they are picked uniformly at random in {0, . . . , N α } and Figure 3 presents a generalized version of the MCExp protocol where s is picked uniformly at random in {0, . . . , N β } and r is picked uniformly at random in {0, . . . , N γ } (for some parameters β and γ).

The client then computes

A 1 = a -s + k 1 • ϕ(N ) and A 2 = a • r + k 2 • ϕ(N )
, and sends them (in a random order) together with ω 1 , ω 2 (two bases related to u) and the modulus N to the server which computes

R 1 = w A1 1 mod N and R 2 = w A2
2 mod N and two other4 modular exponentiations R 3 and R 4 (with bases and exponents which are not relevant for our attacks). It then sends all of this back to the client, which eventually computes u a (and uses the other values to check the validity of the computation). The values of A 1 and A 2 are thus known to the server, but not their order.

The values r and s are not known by the server and are used to check the validity of the output u a . More precisely, the client checks whether an equality of the form

R t1 3 R 1 S 1 u s r = R 4 R 2 S 2 (1)
holds (where t 1 is a "small" (private) exponents known by the client and S 1 , S 2 are pre-computed values in Z N ) and if it is the case, they output

R t1 3 R 1 S 1 u s
as the purported value for u a . Note that if, an adversary can guess the integer r and identifies correctly R 1 , R 2 , R 3 and R 4 , they can then set R1 = R 1 • v and R2 = R 2 • v r for an arbitrary element v ∈ Z N ; the 4-tuple ( R1 , R2 , R 3 , R 4 ) then still satisfies (1) and the client will output

R t1 3 R1 S 1 u s = R t1 3 R 1 vS 1 u s = u a • v which is different from u a for v = 1. Su et al. [1,
Theorem 1.8 ] claim that their scheme achieves (τ, α)verifiability for an unbounded τ and a constant α equal to 119/120. The previous remark shows that if a malicious server correctly guesses the integer r and the values R 1 and R 2 , then they can make the client accept an incorrect value. For MCExp protocol with r ∈ {2, . . . , 11}, this occurs with probability 1/10 • 1/4 • 1/3 = 1/120 ; as such [1, Theorem 1.8 ] therefore claims that this is the best possible attack.

In the following, we present several attacks against the privacy of the MCExp protocol (and variants with larger parameters). Namely, we show that it does not Ch. Bouillaguet, F. Martinez and D. Vergnaud

Client Server sk = (d, ϕ(N )) pk = (N, e) Input = c s $ ← -{0, . . . , N β }; k $ ← -{0, . . . , N α } A ← d -s + k • ϕ(N ) c, A, N ----------→ m ← c A mod N m ← ---------- m ← m • c s mod N Output m FIGURE 2.
Server-aided RSA decryption with additive splitting achieve the exponent-hiding security notion (and thus that Theorem 1.6 from [START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF] is also flawed). As a byproduct of our attacks, an adversary is able to retrieve the Euler totient function ϕ(N ), r and s in addition to the exponent a. Therefore, we also show that the scheme proposed by Su et al. does not achieve (τ, α)verifiability for τ = poly(n) and α larger than 11/12.

Client Server Inputs = a, u s $ ← -{0, . . . , N β }; r $ ← -{0, . . . , N γ } k 1 , k 2 $ ← -{0, . . . , N α } ; b $ ← -{0, 1} A 1 ← a -s + k 1 • ϕ(N ) A 2 ← ra + k 2 • ϕ(N ) A 1+b , A 2-b , N , (...) ---------------→ (... does some computation...) R 1 , R 2 , R 3 , R 4 ← --------------- (... does some computation...) Output u a

The Rangasamy-Kuppusamy (MExpSOS) protocol

In this section, we briefly recall the protocol MExpSOS proposed by Rangasamy and Kuppusamy in [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF]. In their protocol (see Figure 4), a client wants to privately and verifiably outsource a modular exponentiation u a mod N where N is either a prime number or an RSA modulus.

Rangasamy and Kuppusamy made the very strong assumption that the modulus N is unknown to the adversary (whereas following Kerckhoff's principles [START_REF] Kerckhoffs | La cryptographie militaire[END_REF], it is more natural to assume that the adversary knows the modulus since it is usually a part of the public parameters or the public key). Moreover, they add the privacy requirement that the delegation protocol should not reveal any information on N to a malicious server.

To mask the base u, the client generates an integer L = N which is a multiple of N (where is prime number large enough so that factoring L is assumed intractable) and sets U = u + N mod L (where N is another multiple of N ) as the base for the delegated exponentiation. Obviously, this integer L has to be the same for all delegated computation since otherwise a simple greatest common divisor computation would reveal N as gcd(L, L ) = gcd( N, N ) = N for = two distinct prime numbers.

The client chooses two random integers r, s uniformly at random in {0, . . . , N β } for some parameter 0 ≤ β < 1 as well as two integers k 1 and k 2 of unspecified size; we again assume that they are picked uniformly at random in {0, . . . , N α }. It computes the values

A 1 = a -s + k 1 ϕ(N ) and A 2 = a • r + k 2 ϕ(N )
and sends them to the server in a random order, along with U and L. The server computes R 1 = U A1 mod L and R 2 = U A2 mod L and sends them back to the client. The client checks whether (R 1 u s ) r ≡ R 2 mod N and then recovers u a as u a ≡ R 1 u s mod N .

As above, if an adversary can guess the integer r (and the correct order for R 1 and R 2 ), they can then set R1 = R 1 • v mod L and R2 = R 2 • v r mod L for an arbitrary value x; the pair ( R1 , R2 ) passes the verification equation the client will output u a • v mod N instead of u a mod N . Rangasamy and Kuppusamy [2, Theorem 2 ] claim that their scheme achieves (τ, α)-

The Computer Journal, Vol. ??, No. ??, ???? --------------(... does some computation...)

Client Server pk = ∅, sk = (a, ϕ(N ), N ) Inputs = u, a Secrets = N, ϕ(N ), p U = u + N ; L = N s, r $ ← -{0, . . . , N β }; k 1 , k 2 $ ← -{0, . . . , N α } ; b ← {0, 1} A 1 ← a -s + k 1 • ϕ(N ) A 2 ← ra + k 2 • ϕ(N ) U, L, A 1+b , A 2-b ---------------→ (... does some computation...) R 1 , R 2 ← -
Output u a verifiability for an unbounded τ and α equal to 2N α . The previous remark shows that if a malicious server correctly guesses the integer r and identifies R 1 and R 2 , then they can make the client accept an incorrect value. This occurs with probability 2N α and [2, Theorem 2 ] thus claims that this attack is the best possible.

In the following, we present several attacks against the privacy of the MExpSOS protocol. Namely, we show that it does not achieve the instance-hiding security notion (and thus that Theorem 1 from [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF] is also flawed). As a by-product of our attacks, an adversary is able to retrieve the modulus N , the Euler totient function ϕ(N ), r and s in addition to the pair (a, u). Therefore, we also show that the scheme proposed by Rangasamy and Kuppusamy for useful parameters does not achieve (τ, α)-verifiability for τ = poly(n) and a non-trivial α.

LATTICE-BASED CRYPTANALYSIS

A lattice L is a discrete subgroup of R n isomorphic to Z ω for some ω ∈ N. We denote by λ 1 (L), λ 2 (L), etc. the successive minima of the lattice and we define the volume of L by vol(L) = √ det BB t , where the rows of B span the lattice.

The LLL algorithm, due to Lenstra, Lenstra and Lovász [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] is one of the main tool of lattice-based cryptanalysis. We remind here some properties of a LLL-reduced basis, as seen in [34, Chapter 2 ] and refer the reader to [START_REF] Nguyen | The LLL Algorithm: Survey and Applications[END_REF] for additional details on lattice-based cryptanalysis.

Theorem 3.1. Let (b 1 , . . . , b ω ) be an LLL-reduced basis of a lattice L in R n (with δ = 3/4). Then

1. b 1 ≤ 2 (ω-1)/4 (vol L) 1/ω 2. For all i ∈ {1, . . . , ω}, b i ≤ 2 (ω-1)/2 λ i (L) 3. b 1 × • • • × b ω ≤ 2 ω(ω-1)/4 vol(L)
From Theorem 3.1, we obtain a useful corollary: Lemma 3.1. Let L be a lattice of dimension ω. In polynomial time, the LLL algorithm outputs two reduced basis vectors b 1 and b 2 , that satisfy

b 1 ≤ b 2 ≤ 2 ω 4 vol(L) 1 ω-1
Proof. We can assume without loss of generality that b i ≤ b i+1 in an LLL-reduced basis (we may swap basis vectors that violate this condition). Hence b 1 × ( b 2 ) ω-1 ≤ 2 ω(ω-1)/4 vol(L).

Raising to the power 1/(ω -1), we obtain: ( b 1 ) 1/(ω-1) × b 2 ≤ 2 ω/4 vol(L) 1/(ω-1) .

All we have to do left is noticing that b 1 is greater than 1 (we assume that the input basis has integer coordinates).

The Gaussian heuristic "predicts" that if L is a fullrank lattice and C is a measurable subset of R n , then the number of points of L∩C is roughly vol(C)/ vol(L). In particular, this asserts that the size of the shortest (non-zero) vector of L should be close to √ n vol(L) 1/n .

Approximate Common Divisor Problem

In this section, we recall a simple approach for solving the so-called approximate common divisor problem. It relies on a simple lattice-based algorithm due to Lagarias [START_REF] Lagarias | The computational complexity of simultaneous diophantine approximation problems[END_REF] for simultaneous Diophantine approximation. The technique was first proposed by Howgrave-Graham in [START_REF] Howgrave-Graham | Approximate integer common divisors[END_REF], then expanded in [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF].

We consider an adversary that is given t integers x i = pq i + r i where p is an n-bit integer, q i is an αn-bit integer and r i is a βn-bit integer, where β < 1. Since the r i 's are "small", the x i are approximate multiples of p and we have x i /x 0 q i /q 0 for i ∈ {1, . . . , t -1}. In other words, the rationals q i /q 0 are simultaneous rational approximations with the same denominator of the t -1 rationals x i /x 0 for i ∈ {1, . . . , t -1}. If the adversary can compute one such approximation, it can obtain q 0 and then r 0 as x 0 mod q 0 and p as (x 0 -r 0 )/q 0 . The Computer Journal, Vol. ??, No. ??, ????

Ch. Bouillaguet, F. Martinez and D. Vergnaud This means that we are looking for q 0 , . . . , q t such that x i /x 0 q i /q 0 for all i ∈ {1, . . . , t -1}. This can be rewritten by saying that q 0 x i -q i x 0 = q 0 r i -q i r 0 must be "small". Following [START_REF] Lagarias | The computational complexity of simultaneous diophantine approximation problems[END_REF], the adversary can thus construct the integer matrix:

M =        2 βn+1 x 1 x 2 . . . x t-1 0 -x 0 0 . . . 0 0 0 -x 0 . . . 0 . . . 0 0 0 . . . -x 0        (2)
The rows of M generate a lattice L of rank t that contains the "short" vector v = (q 0 , q 1 , . . . , q t-1 )M = (q 0 2 βn+1 , q 0 r 1 -q 1 r 0 , . . . , q 0 r t-1 -q t-1 r 0 ). Each coordinate of v is less than 2 × 2 n(α+β) in absolute value, so the norm of v is upper-bounded by

2 √ t × 2 n(α+β) . The volume of the lattice is vol(L) = | det(M )| = 2 βn+1 x t-1 0 ≈ 2 βn+(t-1)(α+1)n . Therefore if 2 √ t × 2 n(α+β) < √ t| det(M )| 1/t
then we expect by the Gaussian heuristic that v is a shortest non-zero vector in L (i.e. λ 1 (L) = v ) and that the second minima λ 2 (L) should be close to

√ t| det(M )| 1/t ≈ √ t2 (βn+(t-1)(α+1)n)/t .
Running the LLL algorithm on the matrix M yields a reduced basis whose first vector is guaranteed to be at most 2 t/2 times longer than the norm of v the (heuristically) shortest vector of the lattice (Theorem 3.1, item 2). Therefore, if

2 t/2 v ≤ 2 √ t × 2 t/2 2 n(α+β) < √ t2 βn/t+(t-1)(α+1)n/t
the length of the first vector output by LLL is strictly less than λ 2 (L) and it follows that the LLL algorithm will (heuristically) return a shortest vector of L.

If we forget about the constant terms, then this yields a condition on the exponents:

t 2 -2nt(1 -β) + 2n(1 -β + α) < 0 The discriminant ∆ = 4n 2 ((1 -β) 2 -2(1 -β + α)/n) is
necessarily positive for large enough n, so the inequation holds between the two roots:

t ± = n(1 -β) 1 ± 1 -2 1 -β + α n(1 -β) 2 .
We focus on the smallest possible value of t satisfying the constraints. Using the Taylor expansion 1 -√ 1 + 2x = x + O(x 2 ) near zero, we find that the small root is:

t -= 1 + α 1 -β + O(1/n).
This is the minimal required value of t so that the attack works using the LLL algorithm, and thus in polynomial time -subject to the condition that ∆ > 0, or equivalently n > 2(1 -β + α)/(1 -β) 2 .

Coppersmith's Methods

Some of our attacks requires the ability to find "small roots" of multivariate polynomials over the integers. To retrieve these values, we use variants of Coppersmith's methods [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] presented in [START_REF] Ernst | Partial key exposure attacks on RSA up to full size exponents[END_REF], that we now briefly present.

Let us consider a polynomial in Z[x, y, z]:

f (x, y, z) = ω i=1 a i x di y ei z fi .
We assume that there is "small root" (x 0 , y 0 , z 0 ) such that f (x 0 , y 0 , z 0 ) = 0 and that we are given bounds X, Y and Z such that |x 0 | < X, |y 0 | < Y and |z 0 | < Z.

For h(x, y, z) ∈ Z[x, y, z], we denote h(x, y, z) the Euclidean norm of the vector formed by its coefficients (i.e.

the root square sum of the coefficients of monomials in the polynomial). Lemma 3.2 (Howgrave-Graham). Let h(x, y, z) ∈ Z[x, y, z] be the sum of at most ω monomials and let X, Y, Z > 0. For any (x 0 , y 0 , z 0 ) ∈ Z 3 that satisfies

|x 0 | < X, |y 0 | < Y, |z 0 | < Z, if f (x 0 , y 0 , z 0 ) ≡ 0 mod c and f (xX, yY, zZ) < c √ ω , then f (x 0 , y 0 , z 0 ) = 0.
A possible strategy to find the small root (x 0 , y 0 , z 0 ) of a polynomial h consists in constructing a lattice L of dimension containing only polynomials g i such that g i (x 0 , y 0 , z 0 ) ≡ 0 mod c. Then we reduce the lattice basis using LLL, we extract the two first polynomials g 1 , g 2 from the reduced basis. If they satisfy the bound of Lemma 3.2, then these polynomial vanish on (x 0 , y 0 , z 0 ) over Z (not modulo c). Under the heuristic assumption that the polynomials f, g 1 , g 2 define an algebraic variety of dimension 0, then we can find our small root by solving a polynomial system in 3 variables and 3 equations (by computing a Groebner basis for example).

From Lemma 3.1, we know that the LLL algorithm returns two vectors satisfying b

1 ≤ b 2 ≤ 2 ω 4 vol(L) 1 ω-1 . Thus, the condition √ ω2 ω 4 vol(L)
1 ω-1 < c implies that polynomials corresponding to the two shortest reduced basis vectors of an LLL-reduced basis satisfy Howgrave-Graham's bound. In practice, we ignore terms that do not depend on c, and check only if vol(L) ≤ c ω-1 .

The difficulty is to optimize the value of c and to choose the correct polynomials g i to spawn the lattice. This problem has been addressed by Ernst et al. [START_REF] Ernst | Partial key exposure attacks on RSA up to full size exponents[END_REF]. Using polynomials g i of the form

x i y j z k f (x, y, z)X l Y v Z w and c • x i y j z k ,
Denoting W the value W = f (xX, yY, zZ) , they obtain the following results:

The Computer Journal, Vol. ??, No. ??, ????

Cryptanalysis of Modular Exponentiation Outsourcing Protocols Theorem 3.2 ( [START_REF] Ernst | Partial key exposure attacks on RSA up to full size exponents[END_REF]). With the above notations, for every ε > 0, there exist a W 0 such that, for every W ≥ W 0 , the following holds: there is a PPT algorithm that recovers a small root (x 0 , y 0 , z 0 ) of f (x, y, z) if there exists τ ≥ 0 in the two following cases: i) f (x, y, z) = a 0 + a 1 x + a 2 y + a 3 yz and

X 1+3τ Y 2+3τ Z 1+3τ +3τ 2 < W 1+3τ -ε .
ii) f (x, y, z) = a 0 + a 1 x + a 2 y + a 3 z + a 4 yz and

X 2+3τ Y 3+6τ +3τ 2 Z 3+3τ < W 2+3τ -ε .

ATTACKS AGAINST MCEXP USING A SINGLE DELEGATION

In this section, we describe polynomial-time attacks against the MCExp protocol for the exponent-hiding security notion after the adversary has passively observed a single exponentiation delegation. The attacks completely break the scheme since they recover in addition the (secret) factorization of N . The different attacks for the different variants of the protocol MCExp are summarized in Table 1.

A Straightforward Attack on the MCExp Protocol

As mentioned in the description of the protocol, the random masks s and r are picked in the very small set of integers {2, 3, . . . , 11}. It is therefore possible to exhaustively search their values. The adversary observe A 1+b and A 2-b . They do not know b, but there are only two possibilities to correctly identify A 1 and A 2 , so that any attack only has to be repeated twice. Once the adversary has guessed the values of b, r and s, they can then compute

r(A 1 -s) -A 2 = (rk 1 -k 2 )ϕ(N ),
and therefore learn a multiple of ϕ(N ). Note that there are only 200 possible values (10 for s, 10 for r, two possible choices for b) and that they can be explicitly computed.

In [START_REF] Rabin | Digitalized signatures and publickey functions as intractable as factorization[END_REF], Rabin provided a probabilistic polynomialtime algorithm which given an RSA modulus N = pq and a multiple of its Euler's totient function ϕ(N ), outputs the factorization (p, q) in expected polynomial time O(log(N ) 3 ). This in turns allows to reconstruct the secret key (by running the same algorithm as the legitimate user).

All that is left to do is to run Rabin's algorithm on the 200 candidates multiple of ϕ(N ): one of them is going to reveal the factorization of the RSA modulus N . Once the adversary knows the factorization of N and thus ϕ(N ), it also knows the values b, r and s with certainty and from A 1 it can simply retrieve the (secret) exponent a as [A 1 mod ϕ(N )] + s. The MCExp protocol therefore does not achieve (τ, ε)-exponent hiding for τ = Ω(log(N ) 3 ) and ε = 1.

As explained in Section 2.3.2, when the adversary knows b and r, they can make the client accept an incorrect value as the result for the delegated exponentiation with probability 1. The MCExp protocol therefore does not achieve (τ, ζ)-verifiability for τ = Ω(log(N ) 3 ) and ζ = 0.

We implemented this attack for a modulus N of 2048 bits and α = 1 (i.e., k 1 , k 2 N ): it runs in only 1.7s on a laptop.

Generalizations of MCExp

In its original presentation, the MCExp protocol is thus practically broken, mainly because of the bad design decision to limit r and s to extremely small numbers. In the rest of this paper, we show that the problem is in fact more fundamental.

As described in Figure 3, we now consider a generalization of the MCExp protocol where the two parameters r and s can be chosen in larger sets that prevent exhaustive search. More precisely, we assume that s and r are integers picked uniformly at random with 0 ≤ s < N β and 0 ≤ r < N γ where β, γ ≥ 0 are constant parameters. Because the client must perform two exponentiations with exponents s and r, it follows that β + γ should be quite smaller than 1, otherwise the computational load of the client is not significantly reduced and the protocol misses the point.

Let t = p + q -1 so that ϕ(N ) = N -t. When p and q are balanced, it always holds that t ≤ 3N 1/2 . Let us also denote by k := rk 1 -k 2 , which is unknown.

When the attacker can only observe a single delegation, a simple attack strategy consists in solving the following non-linear system over the integers:

           rA 1 -A 2 -kN = rs -kt |s| ≤ N β |r| ≤ N γ |t| ≤ 3N 1/2 |k| ≤ N α+γ (3)
The actual secret parameters (s, r, t, k) are a solution of this system. If this solution is unique, then solving (3) guarantees the recovery of all secrets. This in turn allows the adversary to factor N by computing ϕ(N ) and solving the quadratic equation X 2 -tX + N = 0 (whose roots are p and q). However, depending on the values of α, β, γ, this system may have more than one solution. For instance, if (s, r, t, k) satisfies the equation, then (s + k, r, t + r, k) also does, assuming that α < β and γ < 1/2. In the sequel, we focus on cases where (3) has a single solution.

Attack using Euclidean Division

Let us assume that r is known. Define B := rA 1 -A 2 , whose value is also known. Equation [START_REF] Hohenberger | How to securely outsource cryptographic computations[END_REF]

B/N = (rs + kN -kt)/N = k + (rs -kt)/N So the quotient of the Euclidean division of B by N is B/N = k + rs -kt N If 0 ≤ rs -kt < N , then B/N = k. If -N ≥ rs -kt, then B/N = k -1.
By assumption on the efficiency of the delegation protocol, we have β + γ < 1 and thus rs ≤ N β+γ < N/2 (for λ sufficiently large). If we assume moreover that α + γ < 1/2, then we have

kt = (rk 1 -k 2 )t ≤ N γ N α • 3N 1/2 < N/2 (for λ
sufficiently large) and we easily recover k as B/N or B/N + 1.. Then, once k is known, we have B -kN = rs -tk. If β + γ < α, we have rs < k with overwhelming probability, and we can recover both rs and t by computing the Euclidean division of B -kN by k. With t, we obtain ϕ(N ), and therefore we can factor N in polynomial time by solving a quadratic equation.

An interesting application is the following. Assume that r is small enough to be guessed by the adversary (which is the case when 2 ≤ r ≤ 11 in the original MCExp protocol), and that β < α < 1/2. The attack presented in this section shows that observing a single delegation is enough to factor N instantly in this setting in time O(log(N ) 2 ). As in Section 4.1, the knowledge of r, p, q is sufficient for the adversary to compute s and then the secret exponent a (and also to break the verifiability property of the protocol).

To sum up, the modified MCExp protocol where r is picked uniformly at random in {2, . . . , 11} and s is picked uniformly at random in {0, . . . , N β } with β < α < 1/2 does not achieve (τ, ε)-exponent hiding nor (τ, ζ)-verifiability for τ = Ω(log(N ) 2 ), ε = 1 -negl(λ) and ζ = negl(λ). This attack was tested successfully in practice with a modulus N of 2048 bits, k 1 and k 2 of 992 bits, s of 960 bits and r = 11 ; it takes 0.1ms.

Attack using Linearization

In this section, we present an attack on the modified MCExp protocol when r is unknown (i.e. picked in a set too large to allow exhaustive search). In this case, we could try to partially solve (3) the easy way, by getting rid of the non-linear term rs -kt. Indeed, a solution of (3) is also a solution of the integer linear program:

   |rA 1 -kN -A 2 | ≤ N α+γ+1/2 |r| ≤ N γ |k| ≤ N α+γ (4)
It is not immediately obvious whether or not (4) admits other solution than the "right" values of (r, k), but it does not matter because there is a very efficient way to find the right ones.

Solving (4) amounts to finding a vector close to the vector (0, A 2 ) in the Euclidean lattice L spanned by the rows of:

G = xN 2α+2γ A 1 0 N .
where x > 1 is a constant to be determined later. We claim that if α + 2γ < 1/2, then (r, -k)G is (heuristically) the lattice vector closest to (0, A 2 ). Because solving the Closest Vector Problem in dimension two can be done efficiently, it follows that r and k can both be retrieved efficiently when this condition is met. Combined with the "Euclidean division attack" of the previous section, this shows that a single delegation is sufficient to factor N in polynomial time even when r is not necessarily extremely small, when β < α and α + 2γ < 1/2.

We now prove this claim. The volume of the lattice is vol(L) = xN 1+2α+2γ . By the Gaussian heuristic, we estimate that the length of the shortest vector is ≈ √ xN 1/2+α+γ . Let d denote the distance between (r, -k)G and (0, A 2 ). We have

d 2 = r 2 x 2 N 4α+4γ + (rA 1 -kN ) 2 ,
which can be upper-bounded by

d 2 ≤ x 2 N 4α+6γ + N 1+2α+2γ .
By hypothesis, N 2α+4γ /N quickly goes to zero when N is large. Therefore, for large enough N , we have d 2 ≤ 2N 1+2α+2γ , regardless of the value of x. In fact, x = log N , or even x = N ε (for a small enough ε) would also work.

Thus, for a sufficiently large x and for N large enough, the distance between (0, A 2 ) and (r, -k)G should always be smaller than the length of the shortest vector of the lattice, so that (r, -k)G should be the lattice vector closest to (0, A 2 ).

The Computer Journal, Vol. ??, No. ??, ????

In the range of parameters β < α and α + 2γ < 1/2, as in the previous section, this shows that the modified MCExp protocol does not achieve (τ, ε)-exponent hiding nor (τ, ζ)-verifiability for τ = poly(λ), ε = 1 -negl(λ) and ζ = negl(λ) (assuming the Gaussian heuristic for the family of Euclidean lattice L).This attack was tested successfully in practice with a modulus N of 2048 bits, k 1 and k 2 of 496 bits, s of 480 bits and r of 256 bits ; it takes 30ms.

Attack when s is Somewhat Large using

Coppersmith's Methods

The two previous attacks require α ≤ 1 2 . In this section, we lift this restriction, and focus on the case where r is still very small (smaller than 11 as in the original protocol) but s is not. In this case, it is still possible to do an exhaustive search on r and thus we assume it to be known. We also assume that α > 1/2 and that β < α.

We show that it is heuristically possible, for a range of values of the parameters α and β, to recover in polynomial-time the factorization of N by finding small roots of a polynomial in three variable using the technique exposed in Section 3.2.

In this setting, B/N is no longer equal to k or k -1, but k * = B/N is still a good approximation of k. Hence, we can rewrite k as k = k * + k . The new parameters k * and k are respectively upper-bounded by N 1/2 and N α-1/2 . Equation ( 3) is equivalent to f (s, t, k ) = 0, where f is the tri-variate polynomial:

f (x, y, z) = N • (k * + y) -z • (k * + y) + r • x -B, = N • k * -B + r • x -k * • z + N y -k * • yz.
We want to find a small root of f , expecting it to be (s, k , t). To make Coppersmith's method work, we first need to compute the bounds:

X ≈ N β , Y ≈ N α-1/2 , Z ≈ N 1/2 ,
and finally, W ≈ N 1/2+α . By Theorem 3.2, finding the small root in polynomial time is feasible for parameters α, β such that there exists τ ≥ 0 satisfying:

X 2+3τ Y 3+6τ +3τ 2 Z 3+3τ < W 2+3τ -ε . (5)
The optimal τ (the one which will gives us the largest ranges for α and β) is τ = -α+β-1 2α-1 . We are thus led to distinguish two cases:

• if α + β > 1,
then τ is negative and the optimal value of τ is zero. In this case, (5) becomes α(ε + 1) + 2β < 1 -ε/2 and no pair (α, β) satisfies both conditions; • if α + β ≤ 1, then τ is positive and substituting it into (5) yields

4α 2 ε + α 2 + 2αβ -3β 2 + 2β -ε -1 < 0.
This is true when

3β < α + 1 -4α 2 (1 + 3ε) + 2α -(2 + 3ε). β α 0 1/2 1/2 FIGURE 5.
Attacks based on Coppersmith methods with small r. In blue the parameters that can be broken by the "Euclidean division" of Section 4.3, in red the parameters broken by the attack based on finding small roots of Section 4.5. The black dots mean that the attack has been carried out in practice when N is 2048-bit long. In the hatched area, the attack is known to be practically feasible for this particular size of N .

It must be noted that this bound is exactly the same bound as in the Joye-Lepoint attack against RSA with partial key-exposure [START_REF] Lepoint | Partial key exposure on RSA with private exponets larger than n[END_REF] (see Section 4.7). For any given pair (α, β), there is a threshold W 0 such that the attack (heuristically) works for all W > W 0 (assuming that the generated polynomials define an algebraic variety of dimension 0). In practice, this means that it only works for "large enough" N . As in the previous sections, this is sufficient to (heuristically) break the exponent-hiding and verifiability properties of the modified MCExp protocol in polynomial-time for this range of parameters.

Experiments. Several factors make the practical assessment of the attack difficult. First of all, the above analysis implies that, given α and β, the attack only works for large enough N . It is not easy to determine what ranges of α, β are actually breakable for practical sizes of N .

We thus decided to fix the size of N to a practical value (2048 bits) and ran a series of experiments. The actual algorithm of [START_REF] Ernst | Partial key exposure attacks on RSA up to full size exponents[END_REF] uses two integer parameters which are determined asymptotically in its analysis (summarized in Theorem 3.2). Running the algorithm in practice requires finding actual values of those parameters.It is fairly easy and fast to find automatically pairs such that finding the small root is (heuristically) guaranteed to succeed (for instance by exhaustive search over a small space). If N is too small, then no such pair may exist.

In Figure 5, the dashed line show the largest β for which parameters are known to exist and make the Ch. Bouillaguet, F. Martinez and D. Vergnaud attack work with this particular size of N . This is visibly well below the bound "for large enough N ".

In practice, the algorithms performs better than what the theory predicts (it even succeeds for values of α, β outside of the promised area). This phenomenon is documented [START_REF] Herrmann | Maximizing small root bounds by linearization and applications to small secret exponent RSA[END_REF]. Smaller parameters may work, and manually tuning them could lead to better execution times or may allow the attack to work for a smaller N . This process is nevertheless error-prone and timeconsuming.

We have tested the attack with k 1 , k 2 of 1500 bits and s of 256 bits. It succeeded with m = 4, t = 2, and spent 64h LLL-reducing a lattice of dimension 133 with 14-Kbit coefficients.

Attack when r is Somewhat Large using

Coppersmith's Methods

We finally consider the setting where one increases the range of the multiplicative mask r while s is kept small (less than 11). We consider the polynomial:

f (x, y, z) = A 2 + x • (A 1 -s) -yN -yz
It admits a small root (r, k, t), that we will find using the same method as before. We first need to compute the bounds: X ≈ N γ , Y ≈ N α+γ , Z ≈ N 1/2 and finally, W ≈ N 1+α+γ . By Theorem 3.2, we are searching for τ ≥ 0 such that

X 1+3τ Y 2+3τ Z 1+3τ +3τ 2 < W 1+3τ -ε . (6)
Hence, we are searching for parameters α, γ, τ ≥ 0 such that:

N γ(1+3τ ) N (α+γ)(2+3τ ) N (1+3τ +3τ 2 )/2 < N (1+α+γ)(1+3τ ) .
The optimal τ is τ = 1/2 -γ, and with this value inequality (6) become

α(1 + ε) < 7 8 -ε - 7 2 + ε γ + 3 2 γ 2
Once again, once α and γ are given such that this constraint is satisfied for some , the attack will (heuristically) only work for large enough N . Again, this attack is sufficient to (heuristically) break the exponent-hiding and verifiability properties of the modified MCExp protocol in polynomial-time for this range of parameters.

Experiments. We tested the attack in practice (see Figure 6). It requires larger values of n to actually work than the previous one. When N is 2048-bit long, the attack worked with k 1 , k 2 of 1152 bits and r of 64 bits, using m = 4, t = 2. It spent 3900s LLL-reducing a lattice of dimension 98 with 19-Kbit coefficients. In blue, the parameters that can be attacked with the linearization attack of Section 4.4. In red, the parameters that can be attacked with the attack in this section. The black dots mean that the attack has been carried out in practice when N is 2048-bit long. In the hatched area, the attack is known to be practically feasible for this particular size of N .

Comparison With Known Attacks Against

Server-Aided RSA Protocol with Additive Splitting

In the special case where the delegated exponentiation is an RSA signature (or an RSA decryption) with a secret exponent d, additional knowledge is available to the adversary, namely the fact that ed ≡ 1 mod ϕ(N ) for an exponent e which is usually part of the client's public key. In this case, the MCExp protocol can be seen as a special case of the server-aided RSA protocol with additive splitting (by just focusing on A 1 and ignoring A 2 ). Both protocol reveal a "blinded" version of the secret key. Mefenza and Vergnaud [START_REF] Mefenza | Cryptanalysis of server-aided RSA protocols with private-key splitting[END_REF] pointed out that the best known attack on RSA with partial key exposure due to Joye and Lepoint [START_REF] Lepoint | Partial key exposure on RSA with private exponets larger than n[END_REF] can be used to attack the protocol, by extracting the secret exponent from A 1 .

Theorem 4.1 (Joye-Lepoint attack). There exists a (heuristic) polynomial-time passive adversary against the server-aided protocol with additive splitting that can recover the client secret d (for sufficiently large RSA modulus) from the observation of a single delegation, provided that:

β < α + δ for 0 < δ + α < 1/2 δ+α+1- √ 4(δ+α) 2 +2(δ+α)-2 3 for 1/2 < δ + α < 1
The size of the public exponent e intervenes in the complexity of the Joye-Lepoint attack, while it plays no role in our case. For instance, the Joye-Lepoint attack could be completely prevented by choosing a random e modulo ϕ(N ). The MCExp protocol thus introduces additional weaknesses compared to the simple serveraided protocol with additive splitting.

With a small public exponent, the complexity of the Joye-Lepoint attack is essentially the same as that of the attack with small r of Section 4.5 -which is not surprising since it essentially solves the same problem. However, the Joye-Lepoint attack is not sensitive to the value of r, and thus could potentially break parameters that are out of the reach of all our attacks, such as α = 3/4, β = γ = 1/8.

ATTACKS AGAINST MCEXP AND MEXP-SOS WITH SEVERAL DELEGATIONS

In the previous section, we presented several attacks against the modified MCExp protocol using a single run of the protocol. They considerably reduce the range of parameters usable to obtain an efficient scheme secure in this limited setting. In this section, we present more devastating attacks in the case where the adversary is able to observe more than one exponentiation delegation (with independent random decomposition). To prevent the attacks described in this section, a client can store the random decomposition used for each exponent or generate it as a pseudo-random function of the exponent. However, this approach increases the computational or memory complexity of the limited device and may not be usable in practice. Moreover, to counter active attacks, 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. Renewing the random masks is also interesting to prevent side-channel attacks which are a major threat against implementations of cryptographic algorithms (especially on computationally limited devices).

The method is described for the server-aided RSA with additive splitting and we show that it applies to the MCExp and MExpSOS protocols.

Attack against MCExp with small r using Two Delegations

We first present another simple attack which applies when r is small enough to be guessed by the adversary and the client delegates two exponentiations for the same exponent a. This is for instance the case if the client performs two RSA signatures (even if the adversary does not know the associated public exponent).

In this setting, the adversary can recover the factorization of N in polynomial time, regardless of the size of s.

As in the previous section, this approach breaks the exponent-hiding security notion of MCExp (with two runs in the random experiment Exp eh (A, C, λ)) for τ (λ) = poly(λ) and ε(λ) = 1 and its strong-verifiability (using the knowledge acquired after two sessions to obtain the factorization of N and the random mask r used in the second session, the adversary is able to make the client output an incorrect value).

We suppose that the adversary can obtain two delegations with the same a. We have

A 1 = a -s + k 1 ϕ(N ) A 2 = ra + k 2 ϕ(N ) A 1 = a -s + k 1 ϕ(N ) A 2 = r a + k 2 ϕ(N )
We assume that we know r,r and the order of A 1 , A 2 and A 1 , A 2 (which corresponds to an exhaustive research over only 400 possibilities) then we can compute r A 2 -rA 2 = (r k 2 -rk 2 )ϕ(N ) and run Rabin's algorithm using this multiple of ϕ(N ) (as in Section 4.1).

Attack against Server-Aided RSA with Additive Splitting

We present a direct application of the approximate common divisor algorithm described in Section 3.1 to attack the server-aided protocol with additive splitting when the adversary is allowed to observe t ≥ 2 different executions of the protocol. The adversary observes a sequence of t transcripts A i ← d -s i + k i • ϕ(N ) for i ∈ {0, . . . , t -1}, where each s i and each k i are chosen independently at random in their range. For all i ∈ {1, . . . , t-1}, we simply compute B i = A i -A 0 (which cancels the "large" unknown d term), and we obtain B i = (q i -q 0 )ϕ(N ) + (r i -r 0 ) for i ∈ {1, . . . , t -1}. This is exactly an instance of the approximate common divisor problem, and the algorithm of Section 3.1 finds the approximate common divisor ϕ(N ) in polynomial time, provided that:

1. log(N ) > 2(1 -β + α)/(1 -β) 2 , 2. t > 1 + α/(1 -β).
With N of 2048 bits and s of 256 bits, the first condition translates to α < 783.125. Observing 8α/7 + O(1) delegations are sufficient in practice to factor the modulus N . For instance, with α = 15, so that A is 32Kbit-long, then observing 20 delegations is sufficient. The attack reduces a dimension-20 lattice with 22-Kbit coefficients, which takes about 15s.

Preventing the attack would require choosing α to be so large that the first condition is not satisfied. Using α = log(N )/2 is sufficient, but in this case the multiple k i 's have Ω(log(N ) 2 ) bits and the client must compute the product k i •ϕ(n), which is more costly than performing the exponentiation directly.

Attack against MCExp with large s and r

The previous attack can readily be generalized to attack the modified MCExp protocol with large s and r. The technique consists in simply forgetting the A 2 's and

The Computer Journal, Vol. ??, No. ??, ????

Ch. Bouillaguet, F. Martinez and D. Vergnaud using only the A 1 's. The range of the r's is therefore irrelevant and the attack applies for all γ > 0. We are thus in the same setting as in the server-aided RSA protocol from Section 5.2, except that for each delegation, we have to guess the order of A 1 and A 2 .

We have to observe t = 1 + α/(1 -β) delegations, and try all the 2 t possible cases 5 and each trial takes polynomial time in log(N ) and t. For α = O(1) and β = O(1), this attack allows to obtain the factorization of N in polynomial time. As in Section 4.5, this approach breaks the exponent-hiding security notion of MCExp (with t runs in the random experiment Exp eh (A, C, λ)) for τ (λ) = poly(λ) and ε(λ) = 1 and its strongverifiability (using the knowledge acquired after t -1 sessions to obtain the factorization of N and the random mask r used in the last session, the adversary is able to make the client output an incorrect value).

For more concrete parameters, with α = 1 and both r, s of 256 bits, the attack requires observing 4 delegations. There are 16 possibles orders of the pairs (A 1 , A 2 ), therefore the basic procedure has to be repeated 16 times. This takes 0.1s in total.

For the protocol to be useful, it is necessary that β be much smaller than 1. Making the attack difficult in practice requires a large value of α, for instance α = 128. This adds to the computational load of the client. Indeed, delegating an RSA signature for a 2048-bit modulus then requires transmitting 0.5 Mbit to the server. It also requires the server to perform a large exponentiation (with an exponent of 262,144 bits, we measured a running time of 0.3s on a laptop for the exponentiation). Asymptotically, using β = 1/2 and α = Ω(log(λ) 2 ) for instance, makes our attack not polynomial-time (but it also makes the delegation scheme useless in practice).

Attack against MExpSOS

Finally, we show that the previous attack can also be applied to the protocol MExpSOS. The exponents sent by the client to the server MExpSOS are also of the form A 1 = a -s + k 1 ϕ(N ) and A 2 = a • r + k 2 ϕ(N ) (in a random order) where a is the exponent of the delegated computation. As above, we have to observe t = 1 + α/(1 -β) delegations, and try all the 2 t possible cases in order to obtain the value ϕ(N ). The difference is that the (adversarial) server does not know the modulus N itself but only some multiple L = N .

If N is prime then ϕ(N ) = N -1 and the adversary can readily obtain N . If N is an RSA modulus, an adversary can also simply recovers N from ϕ(N ) and L. Indeed, for a random prime number (in the range that makes L difficult to factor) and a random integer x ∈ Z N , we have x ϕ(N ) ≡ 1 mod N by Fermat's little 5 If the four exponents used in MCExp are of the same bitlength (see Section 2.3.2), this increase the number of possible cases to 12 t but does not change the asymptotic complexity of our attack. theorem whereas x ϕ(N ) = 1 mod with overwhelming probability. Therefore, we have gcd(x ϕ(N ) -1, L) = N with overwhelming probability. This is sufficient to obtain N and then factor it using the knowledge of ϕ(N ). In addition, when the adversary has obtained N , they can simply recover the base of the delegated exponentiation as u = U mod N . This approach therefore breaks the instance-hiding security notion of MExpSOS and its strong-verifiability.

We implemented this attack. For concrete parameters, with N a 2048-bit RSA modulus, a 1024bit prime number (to prevent factoring attacks), α = 1 and both r, s of 256 bits, the attack requires observing 4 delegations. There are 16 possibles orders of the pairs (A 1 , A 2 ), therefore the basic procedure has to be repeated 16 times. This takes 0.3s in total. As above, to prevent this attack, using β = 1/2, the delegation protocol requires α = Ω(log(λ) 2 ) and this makes the delegation scheme useless in practice.

CONCLUSION

We presented several lattice-based attacks on two protocols recently proposed by Su, Zhang and Xue [START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF] and Rangasamy and Kuppusamy [START_REF] Rangasamy | Revisiting single-server algorithms for outsourcing modular exponentiation[END_REF]. In both papers, the authors extended their approach and proposed protocols for simultaneous modular exponentiations. These extensions rely on the same masking techniques and our cryptanalytic methods also apply to these generalized protocols.

Chevalier et al. [START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF][START_REF] Chevalier | Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[END_REF] proved lower bounds on the efficiency of generic private exponentiation outsourcing protocols in prime order groups.

These bounds suggest that for a variable base private modular exponentiation delegation (which is the case of interest for RSA decryption/signature), it is probably difficult to improve the client efficiency by more than a constant factor. It remains open to provide more efficient provably secure protocols and complexity lower bounds for exponentiation protocols in groups of unknown composite order.

Another interesting problem is to provide lower bound on the communication and computational complexities of verifiable exponentiation delegation.

FIGURE 3 .

 3 FIGURE 3. Partial description of the MCExp Protocol. The (...) notation means "some data" (not relevant in this paper).

FIGURE 4 .

 4 FIGURE 4. Partial description of the MExpSOS Protocol.

2 FIGURE 6 .

 26 FIGURE 6. Attacks based on Coppersmith's methods. In blue, the parameters that can be attacked with the linearization attack of Section 4.4. In red, the parameters that can be attacked with the attack in this section. The black dots mean that the attack has been carried out in practice when N is 2048-bit long. In the hatched area, the attack is known to be practically feasible for this particular size of N .

TABLE 1 .

 1 Summary of the attacks against the MCExp protocol B = rs + kϕ(N ). If rs is sufficiently small, then this implies that B kN , hence the quotient B/N should be close to k. Indeed, dividing by N yields:

		Ch. Bouillaguet, F. Martinez and D. Vergnaud
	§	Type	α		β	γ
	4.1	Straightforward	arb.		0	0
	4.3 Euclidean division ≤ 1/2		< α	0
	4.4 4.5 4.6	Linearization Coppersmith Coppersmith	≤ 1/2 > 1/2 arb.	(α + 1 -	< α √ 4α 2 + 2α -2)/3 0	< 1/4 -α/2 0 (7 -2 √ 7 + 6α)/6

becomes:

The Computer Journal, Vol. ??, No. ??, ????

It is worth noting that most of our attacks can be applied directly to exponentiation in general groups.

In[START_REF] Su | Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud[END_REF], it is mentioned that the four exponents are sent in a random order. In this paper, we assume that we can distinguish A 1 and A 2 from the two other exponents (which is natural since they have a priori different bit-lengths). If the four exponents are of the same bit-length this increase only the complexity of the attacks from Section 4 by a constant factor 6.

ACKNOWLEDGMENT

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

DATA AVAILABILITY STATEMENT

There are no new data associated with this article.