4.7 Article

Novel Secure Outsourcing of Modular Inversion for Arbitrary and Variable Modulus

期刊

IEEE TRANSACTIONS ON SERVICES COMPUTING
卷 15, 期 1, 页码 241-253

出版社

IEEE COMPUTER SOC
DOI: 10.1109/TSC.2019.2937486

关键词

Cloud computing; modular inversion; unimodular matrix transformation; efficiency; privacy

资金

  1. National Natural Science Foundation of China [61702294, 61572267]
  2. Natural Science Foundation of Shandong Province [ZR2016FQ02]
  3. National Development Foundation of Cryptography [MMJJ20170126, MMJJ20170118]
  4. State Key Laboratory of Information Security in Institute of Information Engineering, Chinese Academy of Sciences [2016-MS-23, 2019-MS-03]
  5. Key Research and Development Project of Shandong Province
  6. Applied Basic Research Project of Qingdao City [17-1-1-10-jch]

向作者/读者索取更多资源

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

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据