How to securely outsource the inversion modulo a large composite number

Modular inversion is one of the most basic computations in algorithmic number theory. When it comes to cryptosystems, this computation is very time-consuming since the modulus is generally a large number. It is unrealistic for some devices with limited computation capability (e.g. mobile devices and IC cards) to conduct such a time-consuming computation. In this paper, we investigate how to securely outsource the inversion modulo a large composite number. Based on the Chinese Remainder Theorem (CRT), we design a secure outsourcing algorithm for inversion modulo a large composite number with two known prime factors for the client. Besides the privacy of the number and its modular inversion, our algorithm also protects the privacy of the modulus. We can verify the correctness of the result with probability 1. Traditionally, the complexity of modular inversion for a l-bit modulus is O(l3). By leveraging the cloud, our algorithm reduces the complexity to O(l2) on the client side. Also, we prove the security of our algorithm based on the one-malicious version of two untrusted program model (one-malicious model). We conduct several experiments to demonstrate the validity and the practicality of our proposed algorithm. In appendix, we show that our proposed algorithm can be extended and applied in the secret key generation of RSA algorithm on the resource-constrained devices.