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, for each given instance of modular inversion, it only needs one round interaction between the client and the cloud server, and enables the client to verify the correctness of the results retuned from the cloud server with the (optimal) probability 1. Furthermore, we propose an extended secure outsourcing algorithm that can solve modular inversion in multi-variable case. Theoretical analysis and experimental results show that our proposed algorithms achieve remarkable local-clients 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.

Automated summary

This paper proposes a novel technique using unimodular matrix transformation to achieve secure outsourcing of modular inversion. The technique supports arbitrary and variable modulus, is based on a single untrusted program model, requires only one round interaction, and enables verification of result correctness. Theoretical analysis and experimental results demonstrate the computational savings achieved by the proposed algorithm on local clients.