Novel Secure Outsourcing of Modular Inversion for Arbitrary and Variable Modulus

In cryptography and algorithmic number theory, modular inversion is viewed as one of the most common and time-consuming operations. It is hard to be directly accomplished on resource-constrained clients (e.g. mobile devices and IC cards) since modular inversion involves a great amount of operations on large numbers in practice. To address the above problem, this paper proposes a novel unimodular matrix transformation technique to realize secure outsourcing of modular inversion. This technique makes our algorithm achieve several amazing properties. First, to the best of our knowledge, it is the first secure outsourcing computation algorithm that supports arbitrary and variable modulus, which eliminates the restriction in previous work that the protected modulus has to be a fixed composite number. Second, our algorithm is based on the single untrusted program model, which avoids the non-collusion assumption between multiple servers. Third, it only needs one round interaction between the client and the cloud server, and can detect the malicious behavior of the cloud server with the (optimal) probability $1$ . Furthermore, we propose an extended secure outsoucing algorithm that can solve modular inversion in multi-variable case. Theoretical analysis and experimental results show that our proposed algorithms achieve remarkable local-client's computational savings. At last, as two important and helpful applications of our algorithms, the outsourced implementations of the key generation of RSA algorithm and the Chinese Reminder Theorem are given.