Secure Computation Outsourcing Protocol For Modular Inverses And Elliptic Curve Scalar Multiplication

Cloud computing is a new computing paradigm which provides powerful computing and storage resources for cloud clients. As an important application, the cloud clients can securely outsource their costly computations to the cloud. So the cloud client’s burden can be reduced. The costly modular inverse and scalar multiplication operations lie in the core of the widely- used elliptic curve cryptosystems. Thus, the computational efficiency of the modular inve rse and the scalar multiplication directly determines the running efficiency of elliptic curve cryptosystems. Considering the securely outsourcing computing problems for costly modular inverse and scalar multiplication in cloud computing, this dissertation contains the main contributions as follows.1. Secure outsourcing protocol for modular inverses: In this outsourcing protocol, the client only needs to do three modular multiplication to perform a modular inverse operation by resorting to a cloud server. It is illustrated that the cheating behaviors of the servers can be detected by a probability exactly 100%. The protocol is designed based on the one-time pad principle, and thus can obtain the highest level of security, namely, perfect privacy, with respect to the user ’s data privacy. Finally, the experimental and simulation results with C++ language demonstrate that the efficiency of the protocol is about three times that of the Binary Extended Euclidean Algorithm.2. Secure outsourcing protocol for the scalar multiplications on elliptic curves: In the non-colluding double-server model, we propose an outsourcing protocol for the scalar multiplication operations on elliptic curves. In this outsourcing protocol, it only requires two point additions on elliptic curves for the client to do a scalar multiplication operation. It is shown that the cheating behaviors of the servers can be detected by a probability 75%. Furthermore, the protocol can obtain the highest perfect data privacy goal due to the one-time pad principle. The proposal gains the following two advantages over previous protocols: Firstly, the proposed protocol obtains the highest level of security. Secondly, the proposed protocol is much more efficient than the Binary Scalar Multiplication Algorithm. Simulations and experiments with C++ reveal that under several practical parameter choices, the protocol can improve the client’s computational efficiency about 207 and 475 times.