1 Introduction

Cloud computing [2, 3, 10] is a promising next-generation computing paradigm which primarily relies on technologies such as virtualization, utility computing, Service Oriented Architecture, and so forth. Cloud computing is capable to provide seemly unlimited “virtualized” resources to users as services across the Internet while hiding platform and implementation details from users. The services are invoked by users in a pay-per-use manner. With this paradigm computation/storage intensive tasks can be performed even by resource-constrained users through being outsourced to resource-abundant cloud servers. As compared to setting up their own infrastructures, cloud users can tremendously save their capital expenditures via the usage of cloud computing, not to mention other benefits such as reliability and high scalability of the system.

Promising as it is, this paradigm also brings forth new challenges and security concerns when users want to securely outsource the computation of cryptographic operations to the untrusted cloud servers. Firstly, the servers are not fully trusted and sometimes the computations outsourced to the cloud are so critical that it is imperative to rule out accidental errors during the outsourcing computation process. Therefore, the basic security requirements of outsourcing computation are verifiability and efficiency, which require that the client should be able to verify the correctness of the values returned by the worker, and the verification process should require substantially less computation efforts than doing the computation from scratch. Sometimes the input and output of the computation task contain sensitive information of the client, such as the client’s private key or medical records, therefore, it is desirable to protect the secrecy of the client’s input and output, which implies the security requirement of privacy of outsourcing computation.

The problem of secure outsourcing expensive computations has been well studied in the cryptography community. Matsumoto [26] firstly introduced the idea of speeding up secret computations using insecure auxiliary devices. Chaum and Pedersen [11] presented “wallets with observers” that allows a piece of hardware installed on the client’s device to carry out some computation for each transaction. Golle and Mironov [19] introduced the concept of ringers to elegantly solved the problem of verifying computation completion for the “inversion of one-way function” class of outsourcing computation. In recent years, the outsourcing computation becomes the hot topic of research in the computer theory community and cryptography community due to the advancement of cloud computing, and many beautiful works have been done in this area, such as [6, 7, 13, 15].

As we know, modular exponentiation is one of the basic operations among most of current cryptosystems, such as DSS, RSA, and ElGmal et al. For an n-bit exponent a, the traditional square-and-multiply method requires 1.5n modular multiplications on average. Thus, it is a very time-consuming operation for limited computation resources. The applications of fast exponentiation include speeding up signature verification of the above mentioned schemes. For these scheme, the online generation of message signature can be done quickly because the part of the signature that requires exponentiation can be precomputed. However, the verification of the signature needs online exponentiation because the message signature is used in the exponentiation.

In this paper, we mainly focus on how to efficiently and securely outsource modular exponentiation computation to cloud servers.

Contributions

Our contributions on outsourcing computation of modular exponentiation is multi-fold.

Firstly, we propose two secure modular exponentiation outsourcing schemes without any complicated computations utilizing two untrusted servers. One is fixed base-variable exponent exponentiation outsourcing and the other is fixed exponent-variable base exponentiation outsourcing. The variable exponent or variable base means that the exponent or the base is kept privacy against the cloud sever in the respective schemes. With the help of cloud servers, t exponentiations can be computed by the user within only O(n+t) multiplications, where n is the number of bits of the exponent. Compared with [12, 21, 23], our schemes are more efficient. And the computational savings will increase when the batch size grows bigger.

Secondly, the first two schemes are provable secure and the security can be reduced to the Subset Sum Problem, which has been proven to be NP-complete problem. In addition, the schemes achieve approximately 3/4 error detection probability, which means that if the cloud server returns a sequence of values that contains wrong ones, the client can detect it with probability at least 3/4, which is greater than previous secure outsourcing computation schemes of modular exponentiations.

Finally but more importantly, in the third scheme, we present a new method to achieve the verifiability so that the scheme only needs one server. The model of the scheme is more practical and the security analysis shows that the error detection probability can reach approximately 1.

Related works

In [15], Gennaro et al. showed how to delegate arbitrary computations by increasing the client’s offline complexity and public-key size based on fully homomorphic encryption [16] an Yao’s garbled circuit. In [13], Chung et al. proposed an improved generic outsourcing computation protocol without utilizing garbled circuit, whereas the client needs to pre-compute some values to verify the result. In [6], Barbosa and Farshim gave a modular construction of delegatable homomorphic encryption from fully homomorphic encryption, functional encryption and MAC, and showed how one can build a secure outsouring computation scheme generically from delegatable homomorphic encryption. However, the use of fully homomorphic encryption resulting in protocols of limited practical relevance.

In theoretical community, researchers have devoted considerable attention to the outsourcing computation of arbitrary functions. Indeed, after computing the delegated function f on input x and sending the result y, the server can use various types of proof systems to convince the client the correctness of the result. These works contain interactive proofs [5, 17], efficient arguments based on probabilistically checkable proofs [24, 25], CS proofs [27] and the muggles proofs [18]. However, utilizing proofs systems in outsourcing computation protocols can merely realize the security requirement of verifiability. The security requirement of input and output privacy cannot be satisfied solely by the proof systems.

For the outsourcing computation of specific functions, plenty of research works have been proposed. Benjamin and Atallah [4, 8] addressed the problem of secure outsourcing for widely applicable linear algebra computations. However, the proposed protocols required the expensive operations of homomorphic encryptions. Atallah and Frikken [1] further studied this problem and gave improved protocols based on the so-called weak secret hiding assumption. Benabbas et al. [7] presented the first practical outsourcing computation scheme for high degree polynomial functions based on the approach of [15]. Papamanthou et al. [28] further studied the problem and proposed a publicly verifiable outsourcing computation scheme. In 2011, Green et al. [20] proposed new methods for efficiently and securely outsourcing decryption of attribute-based encryption (ABE) ciphertexts. Based on this work, Parno et al. [29] showed a construction of a multi-function computation delegation scheme. In 2012, Waters [30] proposed an outsourcing computation for attribute-based encryption where the ciphertext update can be efficiently securely outsourced to the server.

Many works have been done towards speeding up the modular exponentiation computation by utilizing untrusted servers. In [23], Jakobsson showed how to generate secure server-aided signature by outsourcing the exponentiation computation task to the untrusted servers who may all be controlled by one and the same adversary. To blind the exponent and ensure the verifiability of the result. The protocol in [23] includes the algorithm of problem transformation which consists of replication, dependency, blinding and permutation. However, the user has to precompute a set of modular exponentiations in order to recover the result and check its correctness, which is what we want to perform at first place. And parameters have to be chosen to balance the efficiency and security requirements. Therefore, [23] is efficient for small batch size. Hohenberger and Lysyanskaya [21] presented the outsource-secure algorithm for modular exponentiation by utilizing two untrusted servers. In [12], Chen et al. gave a new algorithm for outsourcing computation of modular exponentiation, and the algorithm is superior in both efficiency and verifiability compared with [21]. Although both [21] and [12] ensure the exponent privacy and base privacy simultaneously, the protocols still require complicated precomputations (modular exponentiations) and the probabilities that the malicious server is detected are only \(\frac{1}{2}\) and \(\frac{2}{3}\), respectively.

Organization

The rest of the paper is organized as follows: In Sect. 2, we present the system model and security definitions of our schemes. In Sect. 3, three schemes of secure outsourcing computation schemes of modular exponentiations are proposed. The security and complexity analysis in specified in Sect. 4. And Sect. 5 concludes the paper.

2 System model and security definitions

The system model and security definitions of our schemes are formally specified in this section.

2.1 System model

An outsourcing computation scheme is a two-party protocol between a client C a server S. The client chooses a function and an input which he provides to the server. Note that the input is always blinded into x′ before sending it to the sever considering abut the input privacy. The server is expected to evaluate the function on the input and respond with the output together with a proof that the result is correct. The client then verifies that the output provided by the server is indeed the output of the function computed on the input provided. In the following description, the computation task is denoted as given f and an input x to compute f(x). Unlike the previous outsourcing computation protocols [13, 15], since no public key operations are needed in our schemes, the KenGen(⋅) algorithm is excluded in our scheme, and the random numbers used in our scheme are generated on the fly. Formally, our scheme consists of three algorithms, which are described as follows.

  • σ x ← ProbGen(x,τ,f). The problem generation algorithm uses the secret input τ to encode the input x as a public value σ x , and sends σ x to the server S.

  • σ y ← Compute(f,σ x ). Given σ x and the outsourcing function f, the server works out an encoded output σ y and returns it to the client.

  • y∪⊥ ← Verify(σ y ,τ). Using the secret input τ, the verification algorithm converts the server’s encoded output into the output of the function, e.g. y=f(x) or outputs ⊥ indicating that σ y does not represent the valid output of f on x.

2.2 Security definitions

An outsourcing computation scheme should be correct, verifiable and private. In the following description, we will give the formal definition of these security definitions, respectively. Intuitively, an outsourcing scheme is correct if the problem generation algorithm produces values that allow an honest cloud server to compute values that will verify successfully and correspond to the function f(⋅) on those inputs.

Definition 1

(Correctness)

An outsourcing computation scheme is correct if for the outsourcing function f and input x, satisfy that if σ x ← ProbGen(x,τ) and σ y ←Compute(f,σ x ), then y←Verify(σ y ,τ).

An outsourcing computation scheme is secure if it satisfies the security definition of verifiability, which means that a malicious sever can not persuade the client to accept an incorrect output. We formalize this intuition with the following experiment. Experiment \(\mathbf{Exp}_{A}^{verif}[f,\kappa]\) Query and response:

  • For i=1,…,l=poly(κ), \(x_{i}\leftarrow A(x_{1},\sigma _{x_{1}},\beta_{1},\ldots,x_{i-1}, \sigma_{x_{i-1}},\beta_{i-1})\).

  • \(\sigma_{x_{i}}\leftarrow{\textsf{ProbGen}}(x_{i},\tau_{i})\).

  • \(\sigma_{y_{i}}\leftarrow A(x_{1},\sigma_{x _{1}},\beta_{1},\ldots,x_{i-1},\sigma_{x_{i-1}},\beta_{x_{i-1}},\sigma_{x_{i}})\).

  • \(\beta_{i}={\textsf{Verify}}(\tau_{i},\sigma_{y_{i}})\).

Challenge:

  • \(x\leftarrow A(x_{1},\sigma_{x_{1}},\beta_{1},\ldots,x_{l},\sigma _{x_{l}},\beta_{l})\).

  • σ x ←ProbGen(x,τ).

  • \(\sigma_{y}\leftarrow A(x_{1},\sigma_{x_{1}},\beta_{1},\ldots,x_{l},\sigma _{x_{l}},\beta_{l},\sigma_{x})\).

  • \(\hat{y}\leftarrow{\textsf{Verify}}(\tau,\sigma_{y})\).

  • if \(\hat{y}\neq f(x)\) and \(\hat{y}\neq\bot\), output 1, else 0.

In the query phase, the malicious servers are given oracle access to generate the encoding of multiple problem instances, and also oracle access to the result of the verification algorithm on arbitrary strings on those instances. The adversary succeeds if he convince the client to output wrong result for a given input value. Our goal is to make the adversary succeed only with negligible probability.

Definition 2

(Verifiability)

For an outsourcing computation scheme, we define the advantage of an adversary \(\mathcal{A}\) in the experiment above as:

$$\mathit{Adv}_A^{verif}[f,\kappa]=\mathit{Prob}\bigl[\mathbf{Exp}_A^{verif}[f,\kappa]=1\bigr]. $$

An outsourcing computation scheme satisfies the security of verifiability if for any adversary A running in probabilistic polynomial time

$$\mathit{Adv}_A^{verif}[f,\kappa]<\mathit{neg}(\kappa) $$

where neg(κ) is a negligible function of the input.

The security definition of privacy contains input privacy and output privacy. Below, we define the input privacy based on a typical indistinguishability argument that guarantees no information about the inputs is leaked. The security definition of output privacy can be described similarly, however, we omit the definition owning to that the output results are public values in our scheme. For more information, please refer to [15].

Intuitively, an outsourcing computation scheme is input private when the outputs of the problem generation algorithm ProbGen over two different inputs are indistinguishable. Formally, we define the input privacy with the following experiment. Experiment \(\mathbf{Exp}_{A}^{Ipriv}[f,\kappa]\) Query and response:

  • For i=1,…,l=poly(κ), \(x_{i}\leftarrow A(x_{1},\sigma _{x_{1}},\ldots,x_{i-1}, \sigma_{x_{i-1}})\).

  • \(\sigma_{x_{i}}\leftarrow{\textsf{ProbGen}}(x_{i},\tau_{i})\).

Challenge:

  • \((x_{c0},x_{c1})\leftarrow A(x_{1},\sigma_{x_{1}},\ldots,x_{l},\sigma_{x_{l}})\).

  • The client randomly selects a bit b← R {0,1} and sends \(\sigma_{x_{cb}}\leftarrow{\textsf{ProbGen}}(x_{cb},\tau)\) to the adversary.

  • \(\hat{b}\leftarrow A(x_{1},\sigma_{x_{1}},\ldots,x_{l},\sigma _{x_{l}},x_{c},\sigma_{x_{c}})\).

  • If \(\hat{b}=b\), output1, else 0.

In the above experiment, the adversary is given the oracle access of the problem generation algorithm in the query and challenge phase, the adversary succeeds if he can distinguish the output of the problem generation algorithm in the challenge phase.

Definition 3

(Input privacy)

For an outsourcing computation scheme, we define the advantage of an adversary in the above experiment as

$$\mathit{Adv}_A^{Ipriv}[f,\kappa]=\mathit{Prob}\bigl[\mathbf{Exp}_A^{Ipriv}[f,\kappa]=1\bigr]-\frac{1}{2}. $$

An outsourcing computation scheme is input private if for any adversary A running in probabilistic polynomial time

$$\mathit{Adv}_A^{Ipriv}[f,\kappa]<\mathit{neg}(\cdot) $$

where neg(⋅) is a negligible function of its input.

In this paper, we use a weak input privacy definition considering the applications of our schemes. As we know, in the cryptosystem, the exponents are always the private keys of the user. Thus, the adversary is not able to query the problem generation algorithm arbitrarily in the real world. Therefore, the security definition of input privacy can be formalized as follows.

Definition 4

(Weak input privacy)

Let T be a computational task and l(⋅) an arbitrary function. We say that the outsourcing of T is ϵ-private with respect to l if the adversary has only negligible advantage ϵ in computing l(i) for some private input i if performing the outsourcing work and seeing the public input and output of the user, compared to a setting where he only sees the public input and output of the user. In some papers, the privacy security requirement also expressed as input privacy.

3 Construction

In this paper, we propose three generic constructions for secure outsourcing of exponentiations. The first two protocols needs two non-collusion servers, while the third only requires one server. All the computations are executed within the cyclic group G p , where p is a secure prime, and g is the generator of G p . The schemes consist of three subprotocols: ProbGen, Compute, and Verify.

3.1 Protocol 1. Fixed base-variable exponent exponentiation secure outsource

As described in Fig. 1, the fixed base-variable exponent scheme works as follows:

  • σ x  ← ProbGen(x,τ,f). Given (g,x 1),(g,x 2),…,(g,x t ) as input that corresponding to an implicit request to compute \((g^{x_{1}},g^{x_{2}},\ldots,g^{x_{t}})\), where x i ∈Z p , i∈[1,t], U first blinds the exponent vector (x 1,x 2,…,x t ) by generating a set of n pseudo-random numbers A={a 1,a 2,…,a n } in a manner that m of which can be summed to x i , for each i∈[1,t]. The set can be constructed as randomly selecting m−1 numbers b 1,b 2,…,b m−1 from Z p , and then set \(c_{k}=x_{k}-\sum_{j=1}^{m-1}b_{j}\), 1≤k≤t. Let B={b 1,b 2,…,b m−1}. Then rest m−1 redundant numbers r 1,r 2,…,r m−1 are randomly selected from Z p . Finally, U re-randomizes the set of these numbers A′=(b 1,b 2,…,b m−1,c 1,c 2,…,c t ,r 1,r 2,…,r m−1) using a pseudo-random permutation function π:[1,n]→[1,n] to a permutated set A=(a 1,a 2,…,a n ), where n=2(m−1)+t. Then, U sends σ x =(A,g,p) to two independent cloud servers CS 1 and CS 2.

  • σ y ← Compute(f,σ x ). CS 1 and CS 2 return the corresponding exponentiation pair \(\sigma _{y}=(v_{i1},v_{i2})=(g^{a_{i}},g^{a_{i}})\), i∈[1,n] to U one by one. v 1=v 2 will not hold with overwhelming probability if either of them is dishonest.

  • y∪⊥ ← Verify(σ y ,τ). Upon receiving the value pair σ y =(v i1,v i2), U first checks whether they are equal or not. If v i1≠v i2, U concludes that the cloud servers are dishonest and aborts the protocol. Otherwise, U does the computation as follows, for 1≤i≤n, and k∈[1,t]:

    • S base =S base ⋅v i1, if \(a_{\pi^{-1}(i)}\in B\)

    • S j =S j ⋅v i1, if \(a_{\pi^{-1}(i)}=c_{j}\), j∈[1,t].

    At the end of the protocol, U completes the exponentiations as:

    $$g^{x_i}=S_i\cdot S_{base},\quad \mbox{for all}\ 1\leq i\leq t. $$
Fig. 1
figure 1

Secure fixed base-variable exponent exponentiation outsourcing

Full size image

3.2 Protocol 2. Fixed exponent-variable base exponentiation secure outsource

As described in Fig. 2, the fixed exponent-variable base scheme works almost the same as fixed base-variable exponent scheme.

  • σ x  ← ProbGen(x,τ,f) Given (g 1,x),(g 2,x),…,(g t ,x) as input that corresponding to an implicit request to compute \((g_{1}^{x},g_{2}^{x},\ldots,g_{t}^{x})\), where x∈Z p , g 1,g 2,…,g t ∈G p , U first blinds the base vector (g 1,g 2,…,g t ) by generating a set of n pseudo-random numbers A={h 1,h 2,…,h n } in a manner that m of which can be multiplied to g i , for each i∈[1,t]. The set can be constructed as choosing m−1 numbers \(h_{b_{1}},h_{b_{2}},\ldots,h_{b_{m-1}}\) randomly from G p , and then set \(h_{c_{k}}=g_{k}/\prod_{j=1}^{m-1}h_{b_{j}}\), for 1≤k≤t. Let \(H_{B}=\{h_{b_{1}},h_{b_{2}},\ldots,h_{b_{m-1}}\}\). The rest m−1 elements \(h_{r_{1}},h_{r_{2}}, \ldots,h_{r_{m-1}}\) can be randomly selected from G p . Finally, U re-randomizes the set of these numbers \(A'=(h_{b_{1}},h_{b_{2}},\ldots,h_{b_{m-1}},h_{c_{1}},h_{c_{2}},\ldots ,h_{c_{t}},h_{r_{1}},h_{r_{2}},\ldots, h_{r_{m-1}})\) using a pseudo-random permutation π:[1,n]→[1,n] to the set A=(h 1,h 2,…,h n ), where n=2(m−1)+t. Then, U sends σ x =(A,x,p) to the cloud servers CS 1 and CS 2.

  • σ y ← Compute(f,σ x ). CS 1 and CS 2 return the corresponding values \((v_{i1},v_{i2})=(h_{i}^{x},h_{i}^{x})\) to U one by one. v 1=v 2 will not hold if either of them is dishonest.

  • y∪⊥ ← Verify(σ y ,τ). Upon receiving the value pair (v i1,v i2) from the cloud servers, U first checks whether they are equal or not. If v i1≠v i2, U concludes that the cloud servers are dishonest and aborts the protocol. Otherwise, U does the computations as follows, for 1≤i≤n and:

    • M base =M base ⋅v i1 if \(a_{\pi^{-1}(i)}\in B\)

    • M j =M j ⋅v i1, if \(a_{\pi^{-1}(i)}=c_{j}\), j∈[1,t].

    At the end of the protocol, U completes the exponentiations as:

    $$g_i^x=M_i\cdot M_{base},\quad \mbox{for~all}\ 1\leq i\leq t. $$
Fig. 2
figure 2

Secure fixed exponent-variable base exponentiation outsourcing

Full size image

3.3 Protocol 3. Outsourcing computation of exponentiation with one server

In this subsection, we present a new outsourcing computation protocol in one sever model. The protocol is superior in both the verifiability and security compared with the above schemes. In the previous constructions, verifiability of the result is realized through the comparison of the values returned by the two cloud servers. Although verification process is quite efficient, we can not distinguish the honest server from the malicious server when there are inequalities. Below, we present the protocol for fixed base-variable exponent computations, and the protocol for fixed exponent-variable base computations can be constructed similarly.

  • σ x  ← ProbGen(x,τ,f). Given (g,x 1),(g,x 2),…,(g,x t ) as input that corresponding to an implicit request to compute \((g^{x_{1}},g^{x_{2}},\ldots,g^{x_{t}})\), where x i ∈Z p , i∈[1,t], U first blinds the exponent vector (x 1,x 2,…,x t ) by generating a set of n pseudo-random numbers A={a 1,a 2,…,a n }. The set can be constructed as randomly selecting m−1 numbers b 1,b 2,…,b m−1 and m−1 numbers \(b_{1}',b_{2}', \ldots,b_{m-1}'\)from Z p , and then set \(c_{k}=x_{k}-\sum_{j=1}^{m-1}b_{j}\), 1≤k≤t and \(c_{k}'=x_{k}-\sum_{j=1}^{m-1}b_{j}'\), 1≤k≤t. Let B={b 1,b 2,…,b m−1}, \(B'=\{b_{1}',b_{2}', \ldots,b_{m-1}'\}\). Finally, U re-randomizes the set of these numbers using a pseudo-random permutation function π:[1,n]→[1,n] to a permutated set A={a 1,a 2,…,a n }, where n=2(m+t−1). Then, U sends σ x =(A,g,p) to the server S.

  • σ y ← Compute(f,σ x ). S returns the corresponding exponentiation pair \(\sigma_{y}=(v_{1},\ldots ,v_{2n})=(g^{a_{i}})\), for all i∈[1,2n] to U.

  • y∪⊥ ← Verify(σ y ,τ). Upon receiving σ y , U does the following verification to verify the validity of the values.

    • S base =S base ⋅v i if \(a_{\pi^{-1}(i)}\in B\)

    • S k =S k ⋅v i if \(a_{\pi^{-1}(i)}=c_{j}\), j∈[1,t].

    • \(S_{base}' = S_{base}'\cdot v_{i}\) if \(a_{\pi^{-1}(i)}\in B'\)

    • \(S_{j}'=S_{j}'\cdot v_{i}\) if \(a_{\pi^{-1}(i)}=c_{j}'\), j∈[1,t].

    • Then U verifies \(S_{i}\cdot S_{base}\stackrel{?}{=}S_{i}'\cdot S_{base}'\), for all i∈[1,t].

    If all the values are correct, U outputs the result as \(g^{x_{i}}=S_{i}\cdot S_{base}\), for all 1≤i≤t.

4 Security and complexity analysis

4.1 Security analysis

Unlike previous cryptographic protocols of which the security is based on hard problem assumptions, such as factoring, DLP. We capture the security of our schemes through a reduction to Subset Sum Problem (SSP), which is an important problem in complexity theory and cryptography. The Subset Sum Problem is a NP-complete problem and can be defined as follows:

Definition 5

(Subset Sum Problem)

Given a weight set of integers (a 1,a 2,…,a n ) and sum s, find a subset of which the elements sum to s, ie., determine the variables x 1,x 2,…,x N ∈{0,1}, such that \(s=\sum_{1}^{N}x_{i}a_{i}\).

SSP is a special case of the knapsack problem [22]. We have to mention that not all of the SSP problems are difficult. The difficulty of SSP depends on the density of the set (a 1,a 2,…,a n ), which is defined as

$$d=\frac{n}{\log_2\max_{1\leq i\leq n}a_i}. $$

In our schemes, we set the density of the set to be

$$d=\frac{n}{\log_2\max_{1\leq i\leq n}a_i}\approx1. $$

Modular Subset Sum Problem (MSSP) is a transformation of traditional SSP, in which M,a 1,a 2,…,a N ,b∈{0,1}l and find x 1,x 2,…,x N ∈{0,1}, such that \(b=\sum_{1}^{N}x_{i}a_{i} \operatorname{mod} M\). It has been proved that MSSP is equivalent to the traditional SSP in [9].

The most powerful method known to date to solve the Subset Sum Problem is lattice-based [14] method, which reduces the problem to the problem of finding a shortest vector in a lattice. In practice, lattice basis reduction methods such as LLL algorithm or the Block-Korkine-Zolotarev (BKZ) reduction algorithm [14, 31] provide suitable approximations to the shortest lattice vector. They perform well for a small number of weights but breaks down for N>200. For an increasing number of weights the quality of the approximation becomes insufficient for proving a solution to the Subset Sum Problem.

Theorem 1

The protocols satisfy the security requirement of input privacy.

Proof

Semantically, for the fixed base-variable exponent exponential outsource scheme, the security requirement of input privacy means that the malicious adversary (server) knows nothing about the exponent. This security requirement is very important because the exponent is always the secret key of the user. In the following specification, we give a formal proof for Protocol 1. The security proof of input privacy for Protocols 2 and 3 can be constructed similarly, so we omit the details.

  • Firstly, the malicious adversary obtains the set A={a 1,a 2,…,a n }. Later, the user may publish an exponentiation \(g^{x_{i}}\) as public parameter of the signature schemes or encryption scheme. Assume that there exist an adversary \(\mathcal{A}\) can successfully break the input privacy of our scheme, which means that \(\mathcal{A}\) finds out the subset S that satisfies \(g^{x_{i}}=g^{\sum a}, a\in S\). It is obvious that this is also a solution to the SSP with respect to A and sum x i .

  • For security analysis, we have to take the following attack into account. After the outsourcing computation, U obtains the exponentiations \(g^{x_{1}},g^{x_{2}}, \ldots,g^{x_{t}}\). Later, U may publish all of these exponentiations. Therefore, on inputs \((G_{p},p,a_{1},a_{2},\ldots,a_{n},g^{x_{1}},g^{x_{2}},\ldots,g^{x_{t}})\), the adversary \(\mathcal{A}\) can compute \(\frac{g^{x_{j}}}{g^{a_{i}}}\), for 1≤i≤n and 1≤j≤t. In our scheme, there exist a base value \(S_{base}=g^{\sum_{i=1}^{m-1}b_{i}}\) (or M base ) and \(g^{x_{k}}=S_{base}g^{a_{j}}\) for k∈[1,t], a j ∈A and a j ∉B. Therefore, among t sets \(\{\frac{g^{x_{i}}}{g^{a_{1}}}, \frac {g^{x_{i}}}{g^{a_{2}}},\ldots, \frac{g^{x_{i}}}{g^{a_{n}}}\}\), 1≤i≤t, there must exist the same value \(v=S_{base}=g^{\sum_{i=1}^{m-1}b_{i}}\). Suppose that \(\mathcal{A}\) has detected \(v=\frac{g^{x_{k}}}{g^{a_{l}}}\), then \(\mathcal{A}\) can conclude that a l ∉B. Similarly, \(\mathcal{A}\) can detect the rest t−1 numbers a j ∉B. Therefore, the problem that the adversary \(\mathcal{A}\) has to settle now is transformed to another SSP, that is, given a set of n−t elements \(A'=\{a_{1}',a_{2}',\ldots,a_{n-t}'\}\), determine which subset B of A′, satisfies \(S_{base}=g^{\sum a_{i}}\), a i ∈B, which is also a modular SSP problem. For security, we set n−t>200 in our scheme, and all the known attacks break down in this case.

In the end, we have proved that for any PPT adversary \(\mathcal{A}\), the probability

$$\operatorname{Pr}\bigl\{\mathcal{A}\bigl(g,G_p,g^{x_1},g^{x_2},\ldots ,g^{x_t},a_1,a_2,\ldots,a_n\bigr)=x_i\bigr\} $$

is negligible in k. Similarly, we can prove the security requirement for Protocols 2 and 3. And we can conclude that for any PPT adversary \(\mathcal{A}\), the probability

$$\operatorname{Pr}\bigl\{\mathcal{A}\bigl(G_p,x,g_1^x,g_2^x,\ldots ,g_t^x,g_1',g_2',\ldots,g_n'\bigr)=g_i\bigr\} $$

is negligible in k. □

So far, the best algorithm for discrete logarithm problem (DLP) y=g x is \(O(\sqrt{q})\), where q is the order of g. To achieve an approximately equal computation complexity of DLP we have to carefully set the parameters n, m, and t. The formula that n, m and t have to satisfy is based on the above attack game. In our scheme, we set 2(m−1)>200. In this case, the successful probability of the adversary is less than \(\frac{1}{2^{80}}\).

Theorem 2

The protocols satisfy the security requirement of verifiability.

Proof

The security requirement of soundness means that whenever the untrusted cloud servers return wrong values, the user can detect its dishonesty with high probability.

In Protocols 1 and 2, two non-collusion untrusted cloud servers are incorporated into the system, which can be realized in the real world easily. The technique used in our scheme greatly reduces the redundancies that have to be inserted into the input (x 1,x 2,…,x n ) and thus saves the bandwidth for interactive communication. The error detection is simplified as a equality verification of the return values rather than complicated computations. As long as the cloud servers return the same values, the user concludes that they are honest and vice versa.

In both of our schemes, we assume that the cloud servers do not collude with each other, which is a practical assumption in the real world. In the security definition of verifiability, we defined a query and response phase. However, for each problem generation of our scheme, a new random set s 1,…,s m−1 is generated. Thus, nothing useful information is leaked to \(\mathcal{A}\) for the challenge phase.

For each cloud server, the probability that each returned value is computed correctly or wrongly is 1/2. In both of our schemes, the probability that the user can detect the malicious cloud server’s dishonesty is \(P=\frac{3}{4}\). The probability is obtained from the analysis of three independent cases. Specifically, the inconsistency occurs when both of the cloud servers are dishonest or either of them is dishonest.

For Protocol 3, a malicious adversary can pass the verification with wrong values only if he is able to find the solutions for the two distinct SSPs. Whereas, given a randomly permuted sequence {a 1,…,a n }, the probability that a malicious adversary \(\mathcal{A}\) can find the solutions of the SSPs for any exponent x i is less than \(\frac{1}{\binom{n}{m-1}}\frac{1}{\binom{n-m+1}{m-1}} \). In our scheme, the parameters are set to satisfy n>200, m≈n/2. Thus, the success probability of the adversary is negligible. □

Theorem 3

The protocols satisfy the security requirement of correctness.

Proof

If all the values returned by the cloud servers are correct, then at the Compute stage, U gets the correct value \(g^{x_{1}},g^{x_{2}},\ldots,g^{x_{t}}\) in Scheme 1 and \(g_{1}^{x},g_{2}^{x},\ldots,g_{3}^{x}\) in Scheme 2. The procedure can be verified as:

 □

4.2 Complexity analysis

We have to emphasize that our schemes are more efficient compared with any previous server-aided fast exponentiation scheme in both the storage complexity and computation complexity. First of all, our schemes do not require any complicated precomputations, which is a great progress compared with the previous fast exponentiation schemes [12, 21]. Below, we will formalize the efficiency analysis in computational, communication and communication complexity.

Computation complexity

We split our schemes into offline and phase. In the offline phase, the user generates the set A. For Protocol 1, the generation of the set A requires t modular additions, which are so efficient so that we can omit them. For Protocol 2, the generation of the set A requires 1 inversion and t modular multiplications. In the online phase, the overall computation costs result from the Verify stage of the protocol. Moreover, a batch of t (1≤t≤n−m) exponentiations can be computed in just one implementation of our scheme. In our schemes, there are base values, S base and M base , that used for batch exponentiation computations. m−2 modular multiplications are needed to compute the base value. Then the base value can be used repeatedly to compute as many as t exponentiations. In Protocols 1 and 2, for one more exponentiation, just one more modular multiplication is need. Therefore, for t exponentiations, all the computations that U has to do are m+t−2 modular multiplications, which is very efficient. For Protocol 3, due to the verification algorithm, the computation cost of the user is double that of Protocols 1 and 2, but still very efficient.

We have to mention that for small batches, for example just one modular exponentiation is outsourced, our schemes are still efficient for long exponent, such as the exponent d of RSA signature is about 1024 bits. As we know, for τ-bit long exponent, 1.5τ multiplications are needed to complete the computation if the user does it by himself. Whereas, only approximately 100 multiplications are needed if the user utilizes our outsourcing scheme.

Communication complexity

In our schemes, the user has to send the set A to the servers. For Protocol 1, A consists of n elements from Z p . As there are two servers, thus the overall communication complexity is 2n elements from Z p . For Protocol 2, the communication complexity is 2n elements from G p . And the communication complexity of Protocol 3 is n elements from Z p . For the security of our schemes, n is usually set to be greater than 200.

Storage complexity

In Protocols 1 and 2, the user just needs to store the temporary value S base (M base ), and S k (M k ), k=1,…,t. And for Protocol 3, the storage complexity is double that of the previous schemes. And for all the schemes, the user has to store the permutation π to correctly compute the final modular exponentiations.

Table 1 presents the efficiency comparison between our scheme and [12, 21]. We denote by MM a modular multiplication, by MInv a modular inverse. Note that Protocol 2 is eliminated from the table, because Protocol 2 is designed form variable base exponentiations. Therefore, our schemes are practical and very efficient, and can be widely used in the resource limited application scenarios.

Table 1 Efficiency comparison
Full size table

5 Conclusion

In this paper, we presented secure outsourcing schemes enabling users to securely outsource the computations of exponentiations to servers. The first two schemes require two non-collusion servers, while the third scheme only needs one server. In our schemes, a batch of exponentiations (e.g. t exponentiations) can be efficiently computed by the user with only O(n+t) multiplications, where n is the number of bits of the exponent. Furthermore, there is not any complicated pre-computations on the user side. We also showed that the proposed schemes are provably secure under the Subset Sum Problem.