How to securely outsource the inversion modulo a large composite number. Su, Q., Yu, J., Tian, C., Zhang, H., & Hao, R. Journal of Systems and Software, 2017.
abstract   bibtex   
© 2017 Elsevier Inc. 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.
@article{
 title = {How to securely outsource the inversion modulo a large composite number},
 type = {article},
 year = {2017},
 identifiers = {[object Object]},
 keywords = {Chinese remainder theorem,Cloud computing,Modular inversion,Outsource-secure algorithms},
 volume = {129},
 id = {f6d958df-222e-3aac-8f01-90615f60839b},
 created = {2019-04-25T16:41:29.042Z},
 file_attached = {false},
 profile_id = {43e444e4-67a9-3e6a-86a0-6dbb3d76a4e8},
 last_modified = {2019-04-25T16:41:29.042Z},
 read = {false},
 starred = {false},
 authored = {true},
 confirmed = {false},
 hidden = {false},
 private_publication = {false},
 abstract = {© 2017 Elsevier Inc. 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.},
 bibtype = {article},
 author = {Su, Q. and Yu, J. and Tian, C. and Zhang, H. and Hao, R.},
 journal = {Journal of Systems and Software}
}

Downloads: 0