CRT-Based Outsourcing Algorithms for Modular Exponentiations

The problem of securely outsourcing cryptographic computations to the untrusted servers was formally addressed first by Hohenberger and Lysyanskaya in TCC 2005. They presented an algorithm which outsources computation of modular exponentiations securely to two non-interacting third-party servers but the checkability of third-party computations has probability 1 / 2. Chen et al. improved this algorithm for two non-colluding servers by increasing the checkability probability to 2/3. For real-world cryptographic applications it is desirable that the checkability probability is \(1-\epsilon \), where \(\epsilon \) becomes negligible for appropriate parameter choices. Towards a more practical use, we present an algorithm(s) for secure outsourcing of (simultaneous) modular exponentiation(s) which can be seen as another application of the Chinese remainder theorem (CRT). Interestingly the checkability probability of our algorithm is 1 in the presence of two non colluding servers. Our algorithm is superior in both efficiency and checkability compared to that of the previously known schemes of the same kind. Finally we discuss the potential practical applications for our outsourcing schemes, for example computing the final exponentiation in pairings.

1. 1.

   We use the terms worker, program and oracle interchangeably to refer to the untrusted server.

Authors and Affiliations

1. Society for Electronic Transactions and Security (SETS), Chennai, India

   Lakshmi Kuppusamy & Jothi Rangasamy

Corresponding author

Correspondence to Lakshmi Kuppusamy .

Editors and Affiliations

1. University of Haifa , Haifa, Israel

   Orr Dunkelman

2. Indraprashtha Institute of Information Technology (IIIT-D), New Delhi, India

   Somitra Kumar Sanadhya

Appendix

A Security Defintions

Definition 1 (Algorithm with IO-outsource)

The outsource algorithm \(\mathsf {Alg}\) obeys the input/output specification if it accepts five inputs and produces three outputs. The honest entity generates the first three inputs and the last two adversarially chosen inputs are generated by the environment \(\mathcal {E}.\) The first three inputs can be further classified based on the information about them available to the adversary \(\mathcal {A}= (\mathcal {E}, \mathcal {U}).\) The first input is the honest, secret input which is unknown to both \(\mathcal {E}\) and \(\mathcal {U}.\) The second input is the honest, protected input which may be known by \(\mathcal {E},\) but is protected from \(\mathcal {U}.\) The third input is the honest, unprotected input which may be known by both \(\mathcal {E}\) and \(\mathcal {U}.\) The fourth input is the adversarial, protected input which may be known by \(\mathcal {E},\) but is protected from \(\mathcal {U}.\) The fifth input is the the adversarial, protected input which may be known by \(\mathcal {E},\) but is protected from \(\mathcal {U}.\) Similarly, the first, second and third outputs are called secret, protected and unprotected outputs respectively.

Definition 2 (Outsource-security)

A pair of algorithms \((\mathcal {C}, \mathcal {U})\) is said to be an outsource-secure implementation of an algorithm \(\mathsf {Alg}\) with IO-outsource if:

• Correctness \(\mathcal {C}^{\mathcal {U}}\) is a correct implementation of \(\mathsf {Alg}.\)

• Security For all probabilistic polynomial-time adversaries \(\mathcal {A}= (\mathcal {E}, \mathcal {U}'),\) there exist probabilistic expected polynomial-time simulators \((\mathcal {S}_1,\mathcal {S}_2)\) such that the following pairs of random variables are computationally indistinguishable.

  Pair One (\(\mathcal {E}\) learns nothing): \( EVIEW _{real} \sim EVIEW _{ideal} .\)

  The real process: This process proceeds in rounds. Assume that the honestly generated inputs are chosen by a process I. The view that the adversarial environment obtains by participating in the following process:

  

  $$ EVIEW _{real} = EVIEW _{real}^i if stop^i = TRUE .$$

  In round i,  The adversarial environment does not have access to the honest inputs \((x_{hs}^i, x_{hp}^i, x_{hu}^i)\) that are picked using an honest, stateful process I. The environment based on its view from last round, chooses the value of its \(estate_i\) variable that is used to recall what it did next time it is invoked. Then, among the previously generated honest inputs, the environment chooses a input vector \((x_{hs}^{j^i}, x_{hp}^{j^i}, x_{hu}^{j^i})\) to give it to \(\mathcal {C}^{\mathcal {U}'}.\) Observe that the environment can specify the index \(j^i\) of the inputs but not the values. The environment also chooses the adversarial protected and unprotected input \(x_{ap}^i\) and \(x_{au}^i\) respectively. It also chooses the boolean variable \(stop^i\) that determines whether round i is the last round in this process.

  Then, \(\mathcal {C}^{\mathcal {U}'}\) is run on inputs \((tstate^{i-1}, x_{hs}^{j^i}, x_{hp}^{j^i}, x_{hu}^{j^i}, x_{ap}^{i},x_{au}^{i} )\) where \(tstate^{i-1}\) is \(\mathcal {C}\)’s previously saved state. The algorithm produces a new state \(tstate^{i}\) for \(\mathcal {C}\) along with the secret \(y_s^i\), protected \(y_p^i\) and unprotected \(y_u^i\) outputs. The oracle \(\mathcal {U}'\) is given \(ustate^{i-1}\) as input and the current state in saved in \(ustate^{i}.\) The view of the real process in round i consists of \(estate^i,\) and the values \(y_p^i\) and \(y_u^i.\) The overall view of the environment in the real process is just its view in the last round.c

  The ideal process:

  

  $$ EVIEW _{ideal} = EVIEW _{ideal}^i if stop^i = TRUE .$$

  This process also proceeds in rounds. The secret input \(x_{hs}^i\) is hidden from the stateful simulator \(\mathcal {S}_1.\) But, the non-secret inputs produced by the algorithm that is run on all inputs of round i is given to \(\mathcal {S}_1.\) Now, \(\mathcal {S}_1\) decides whether to output the values \((y_p^i, y_u^i)\) generated by the algorithm \(\mathsf {Alg}\) or replace them with some other values \((Y_p^i, Y_u^i).\) This replacement is captured using the indicator variable \(replace^i \in \{0,1\}.\) The simulator is allowed to query the oracle \(\mathcal {U}'\) which saves its state as in the real experiment.

  Pair Two (\(\mathcal {U}'\) Learns Nothing): \( UVIEW _{real} \sim UVIEW _{ideal} .\)

  The view that the untrusted entity \(\mathcal {U}'\) obtains by participating in the real process is described in pair one. \( UVIEW _{real} = ustate^i if stop^i = TRUE .\) The ideal process:

  

  $$ UVIEW _{ideal} = UVIEW _{ideal}^i if stop^i = TRUE .$$

  In the ideal process, the stateful simulator \(\mathcal {S}_2\) is given with only the unprotected inputs \((x_{hu}^i, x_{au}^i),\) queries \(\mathcal {U}'.\) As before, \(\mathcal {U}'\) may maintain state.

Definition 3

( \(\alpha -\) efficient, secure outsourcing). A pair of algorithms \((\mathcal {C}, \mathcal {U})\) is said to be an \(\alpha -\)efficient implementation of an algorithm \(\mathsf {Alg}\) if \((\mathcal {C}, \mathcal {U})\) is an outsource secure implementation of algorithm \(\mathsf {Alg}\) and for all inputs x,  the running time of \(\mathcal {C}\) is \(\le \) an \(\alpha -\) multiplicative factor of the running time of \(\mathsf {Alg}(x)\)

Definition 4

( \(\beta -\) checkable, secure outsourcing). A pair of algorithms \((\mathcal {C}, \mathcal {U})\) is a \(\beta -\)checkable implementation of an algorithm \(\mathsf {Alg}\) if \((\mathcal {C}, \mathcal {U})\) is an outsource secure implementation of algorithm \(\mathsf {Alg}\) and for all inputs x,  if \(\mathcal {U}'\) deviates from its advertised functionality during the execution of \(\mathcal {C}^{\mathcal {U}'}(x),\) \(\mathcal {C}\) will detect the error with probability \(\ge \beta \)

Definition 5

( \((\alpha , \beta )-\) outsource-security). A pair of algorithms \((\mathcal {C}, \mathcal {U})\) is said to be an \((\alpha , \beta )-\)outsource-secure implementation of an algorithm \(\mathsf {Alg}\) if they are both \(\alpha -\)efficient and \(\beta -\)checkable.

Reprints and permissions

© 2016 Springer International Publishing AG

Policies and ethics