Publication Type

Journal Article

Version

publishedVersion

Publication Date

1-2022

Abstract

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 returned 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-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.

Keywords

Outsourcing, Servers, Cloud Computing, Computational Modeling, Task Analysis, Cryptography, Cloud Computing, Modular Inversion, Unimodular Matrix Transformation, Efficiency, Privacy

Discipline

Information Security

Research Areas

Cybersecurity

Areas of Excellence

Digital transformation

Publication

IEEE Transactions on Services Computing

Volume

15

Issue

1

First Page

241

Last Page

253

ISSN

1939-1374

Identifier

10.1109/tsc.2019.2937486

Publisher

Institute of Electrical and Electronics Engineers

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/tsc.2019.2937486

Download

Share

COinS