Acceleration of Homomorphic Arithmetic Processing Based on the ElGamal Cryptosystem
- 1 Department of Information Sciences, Graduate School of Tokyo University of Science, Tokyo, Japan
- 2 Department of Information Sciences, Tokyo University of Science, Tokyo, Japan
- 3 Department of Information Sciences, Tokyo University of Science, Tokyo, Japan
Abstract
In recent years, opportunities for using cloud services as computing resources have increased and there is a concern that private information may be leaked when processes data. The data processing while maintaining confidentiality is called secret computation. Cryptosystems can add and multiply plaintext through the manipulation of ciphertexts of homomorphic cryptosystems, but most of them have restrictions on the number of multiplications that can be performed. Among the different types of cryptosystems, fully homomorphic encryption can perform arbitrary homomorphic addition and multiplication, but it takes a long time to eliminate the limitation on the number of homomorphic operations and to carry out homomorphic multiplication. Therefore, in this paper, we propose an arithmetic processing method that can perform an arbitrary number of homomorphic addition and multiplication operations based on ElGamal cryptosystem. The results of experiments comparing with the proposed method with HElib in which the BGV scheme of fully homomorphic encryption is implemented showed that, although the processing time for homomorphic addition per ciphertext increased by about 35%, the processing time for homomorphic multiplication was reduced to about 1.8%, and the processing time to calculate the statistic (variance) had approximately a 15% reduction.
- Paillier, P. (1999) Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Proceedings of the EUROCRYPTO’99, Lecture Notes in Computer Science, 1592, 223-238. https://doi.org/10.1007/3-540-48910-X_16
- Rivest, R.L., Shamir, A. and Adleman, L. (1978) A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21, 120-126. https://doi.org/10.1145/359340.359342
- Elgamal, T. (1985) A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31, 469-472. https://doi.org/10.1109/TIT.1985.1057074
- Gentry, C. (2009) A Fully Homomorphic Encryption Scheme. Doctoral Dissertation, Stanford University, Stanford.
- Smart, N.P. and Vercauteren, F. (2010) Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. PKC, 420-443. https://doi.org/10.1007/978-3-642-13013-7_25
- Brakerski, Z., Gentry, C. and Vaikuntanathan, V. (2011) Fully Homomorphic Encryption without Bootstrapping. IACR Cryptology ePrint Archive, Report 2011/277.