PROJECT TITLE :

Novel Secure Outsourcing of Modular Inversion for Arbitrary and Variable Modulus

ABSTRACT:

In the fields of cryptography and algorithmic number theory, modular inversion is regarded as one of the operations that takes the most time and is performed the most frequently. Because modular inversion in practice requires a significant number of operations to be performed on very large numbers, it is difficult to directly accomplish on clients that have a limited amount of available resources (such as mobile devices and IC cards). In this paper, we propose a novel technique for transforming unimodular matrices in order to realize secure outsourcing of modular inversion. This will allow us to address the issue outlined above. Because of this technique, our algorithm is able to achieve a number of remarkable properties. First, to the best of our knowledge, it is the first secure outsourcing computation algorithm that supports arbitrary and variable modulus. This removes the restriction that the protected modulus needs to be a fixed composite number, which was present in previous work. Second, because our algorithm is based on the model of a single untrusted program, we do not have to make the assumption that multiple servers are not working together to cheat. Third, it only requires one round of interaction between the client and the cloud server for each given instance of modular inversion, and it enables the client to verify the correctness of the results returned from the cloud server with the (optimal) probability of 1. In addition, we suggest an extended version of our secure outsourcing algorithm that is able to solve modular inversion when there are multiple variables involved. Both theoretical analysis and experimental findings demonstrate that our proposed algorithms are capable of achieving remarkable computational savings for the local client. In conclusion, the outsourced implementations of the key generation of RSA algorithm and the Chinese Reminder Theorem are presented here as two significant applications of our algorithms that are both helpful and important.