Secure outsourcing of scalar multiplication on elliptic curves
Kai Wen Zhou, Jian Ren · 2016
Cloud computing enables resource-constrained end-users to outsource their computational tasks to the cloud in a flexible manner. One major concern of computation outsourcing is the security of the outsourced data as well as the results. In this paper, we propose a secure outsourcing scheme (SecMul) for one basic and expensive computation in cryptography, that is scalar multiplication of points on elliptic curves. The basic idea of the proposed SecMul is to transfer computations in a finite field to computations in a ring. The scheme is designed in such a way that without the secret key, it is computationally infeasible for the cloud to recover the input and the output. The proposed SecMul is highly efficient in that it enables the end-users to outsource a scalar multiplication at the cost of only a few multiplications. Especially, the performance gain of outsourcing is O(log(s)), where s is the multiplier. Our comprehensive security and complexity analysis demonstrate that the proposed SecMul scheme is both secure and efficient.