Journal Home > Volume 27 , Issue 3

Multikey homomorphic encryption (MKHE) supports arbitrary homomorphic evaluation on the ciphertext of different users and thus can be applied to scenarios involving multiusers (e.g., cloud computing and artificial intelligence) to protect user privacy. CDKS19 is the current most efficient MKHE scheme, and its relinearization process consumes most of the time of homomorphic evaluation. In this study, an optimized relinearization algorithm of CDKS19 is proposed. This algorithm reorganizes the evaluation key during the key generation process, decreases the complexity of relinearization, and reduces the error growth rate during homomorphic evaluation. First, we reduce the scale of the evaluation key by increasing its modulus instead of using a gadget vector to decompose the user’s public key and extend the ciphertext of homomorphic multiplication. Second, we use rescaling technology to optimize the relinearization algorithm; thus, the error bound of the ciphertext is reduced, and the homomorphic operation efficiency is improved. Lastly, the average-case error estimation on the variances of polynomial coefficients and the upper bound of the canonical embedding map are provided. Results show that our scheme reduces the scale of the evaluation key, the error variance, and the computational cost of the relinearization process. Our scheme can effectively perform the homomorphic multiplication of ciphertexts.


menu
Abstract
Full text
Outline
About this article

Optimized Relinearization Algorithm of the Multikey Homomorphic Encryption Scheme

Show Author's information Xiaoyuan YangShangwen ZhengTanping Zhou( )Yao LiuXiaoliang Che
College of Cryptographic Engineering, Engineering University of PAP, Xi’an 710086, China

Abstract

Multikey homomorphic encryption (MKHE) supports arbitrary homomorphic evaluation on the ciphertext of different users and thus can be applied to scenarios involving multiusers (e.g., cloud computing and artificial intelligence) to protect user privacy. CDKS19 is the current most efficient MKHE scheme, and its relinearization process consumes most of the time of homomorphic evaluation. In this study, an optimized relinearization algorithm of CDKS19 is proposed. This algorithm reorganizes the evaluation key during the key generation process, decreases the complexity of relinearization, and reduces the error growth rate during homomorphic evaluation. First, we reduce the scale of the evaluation key by increasing its modulus instead of using a gadget vector to decompose the user’s public key and extend the ciphertext of homomorphic multiplication. Second, we use rescaling technology to optimize the relinearization algorithm; thus, the error bound of the ciphertext is reduced, and the homomorphic operation efficiency is improved. Lastly, the average-case error estimation on the variances of polynomial coefficients and the upper bound of the canonical embedding map are provided. Results show that our scheme reduces the scale of the evaluation key, the error variance, and the computational cost of the relinearization process. Our scheme can effectively perform the homomorphic multiplication of ciphertexts.

Keywords: multikey homomorphic encryption, relinearization, evaluation key, rescaling

References(23)

[1]
N. B. Li, T. P. Zhou, X. L. Che, X. Y. Yang, and Y. L. Han, Overview on multi-key fully homomorphic encryption, (in Chinese), J. Cryptol. Res., vol. 7, no. 6, pp. 713-734, 2020.
[2]
T. Ristenpart, E. Tromer, H. Shacham, and S. Savage, Hey, you, get off of my cloud: Exploring information leakage in third-party compute clouds, in Proc. 16th ACM Conf. Computer and Communications Security, Chicago, IL, USA, 2009, pp. 199-212.
DOI
[3]
M. Y. Shabir, A. Iqbal, Z. Mahmood, and A. Ghafoor, Analysis of classical encryption techniques in cloud computing, Tsinghua Science and Technology, vol. 21, no. 1, pp. 102-113, 2016.
[4]
Z. F. Cao and Q. S. Xue, The development direction and the latest progress of cryptography, (in Chinese), Comput. Educ., no. 1, pp. 19-21, 2005.
[5]
D. G. Feng, M. Zhang, Y. Zhang, and Z. Xu, Study on cloud computing security, (in Chinese), J. Softw., vol. 22, no. 1, pp. 71-83, 2011.
[6]
X. Wang, S. Ranellucci, and J. Katz, Global-scale secure multiparty computation, in Proc. 2017 ACM SIGSAC Conf. Computer and Communications Security, Dallas, TX, USA, 2017, pp. 39-56.
DOI
[7]
A. López-Alt, E. Tromer, and V. Vaikuntanathan, On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption, in Proc. 44th Annu. ACM Symp. Theory of Computing, New York, NY, USA, 2012, pp. 1219-1234.
DOI
[8]
X. L. Che, T. P. Zhou, N. B. Li, H. N. Zhou, Z. H. Chen, and X. Y. Yang, Modified multi-key fully homomorphic encryption based on NTRU cryptosystem without key-switching, Tsinghua Science and Technology, vol. 25, no. 5, pp. 564-578, 2020.
[9]
M. Clear and C. McGoldrick, Multi-identity and multi-key leveled FHE from learning with errors, in Proc. 35thAnnu. Cryptology Conf., Santa Barbara, CA, USA, 2015, pp. 630-656.
DOI
[10]
C. Gentry, A. Sahai, and B. Waters, Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based, in Proc. 33rd Annu. Cryptology Conf., Santa Barbara, CA, USA, 2013, pp. 75-92.
DOI
[11]
P. Mukherjee and D. Wichs, Two round multiparty computation via multi-key FHE, in Proc. 35th Annu. Int. Conf. Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, pp. 735-763.
DOI
[12]
C. Peikert and S. Shiehian, Multi-key FHE from LWE, revisited, in Proc. 14th Int. Conf., Beijing, China, 2016, pp. 217-238.
DOI
[13]
Z. Brakerski and R. Perlman, Lattice-based fully dynamic multi-key FHE with short ciphertexts, in Proc. 36th Annu. Int. Cryptology Conf., Santa Barbara, CA, USA, 2016, pp. 190-213.
DOI
[14]
L. Chen, Z. F. Zhang, and X. Q. Wang, Batched multi-hop multi-key FHE from Ring-LWE with compact ciphertext extension, in Proc. 15th Int. Conf., Baltimore, MD, USA, 2017, pp. 597-627.
DOI
[15]
Z. Brakerski, C. Gentry, and V. Vaikuntanathan, (Leveled) fully homomorphic encryption without bootstrapping, in Proc. 3rd Innovations in Theoretical Computer Science Conf., Cambridge, MA, USA, 2012, pp. 309-325.
DOI
[16]
H. Chen, I. Chillotti, and Y. Song, Multi-key homomorphic encryption from TFHE, in Proc. 25th Int. Conf. Theory and Application of Cryptology and Information Security, Kobe, Japan, 2019, pp. 446-472.
DOI
[17]
I. Chillotti, N. Gama, M. Georgieva, and M. Izabachne, Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds, in Proc. 22nd Int. Conf. Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016, pp. 3-33.
DOI
[18]
H. Chen, W. Dai, M. Kim, and Y. Song, Efficient multi-key homomorphic encryption with packed ciphertexts with application to oblivious neural network inference, in Proc. 2019 ACM SIGSAC Conf. Computer and Communications Security, London, UK, 2019, pp. 395-412.
DOI
[19]
J. H. Cheon, A. Kim, M. Kim, and Y. Song, Homomorphic encryption for arithmetic of approximate numbers, in Proc. 23rd Int. Conf. Theory and Application of Cryptology and Information Security, Hong Kong, China, 2017, pp. 409-437.
DOI
[20]
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM, vol. 56, no. 6, p. Article No. 34, 2009.
[21]
B. Y. Li and D. Micciancio, On the security of homomorphic encryption on approximate numbers, in Proc. 40th Annu. Int. Conf. Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 2021, pp. 648-677.
DOI
[22]
C. Gentry, S. Halevi, and N. P. Smart, Homomorphic evaluation of the AES circuit, in Proc. 32nd Annu. Cryptology Conf., Santa Barbara, CA, USA, 2012, pp. 850-867.
DOI
[23]
A. Costache and N. P. Smart, Which ring based somewhat homomorphic encryption scheme is best? in Proc. Cryptographers’ Track at the RSA Conf. 2016, San Francisco, CA, USA, 2016, pp. 325-340.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 31 March 2021
Revised: 04 July 2021
Accepted: 09 July 2021
Published: 13 November 2021
Issue date: June 2022

Copyright

© The author(s) 2022

Acknowledgements

This work was supported by the National Key R&D Program of China (No. 2017YFB0802000), Innovative Research Team in Engineering University of PAP (No. KYTD201805), National Natural Science Foundation of China (No. 62172436), Natural Science Basic Research Plan in Shaanxi Province of China (No. 2020JQ-492), and Fundamental Research Project of Engineering University of PAP (Nos. WJY201910, WJY201914, and WJY201912).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return