Cryptology ePrint Archive: Report 2021/1131

Multi-key Fully Homomorphic Encryption Scheme with Compact Ciphertext

Tanping Zhou and Zhenfeng Zhang and Long Chen and Xiaoliang Che and Wenchao Liu and Xiaoyuan Yang

Abstract: Multi-Key fully homomorphic encryption (MKFHE) allows computation on data encrypted under different and independent keys. The previous researches show that the ciphertext size of MKFHE scheme usually increases linearly or squarely with the number of parties, which restricts the application of the MKFHE scheme. In this paper, we propose a general construction of MKFHE scheme with compact ciphertext. Firstly, we construct the accumulated public key of the parties set with compact by accumulating every party’s public key under the CRS model. Secondly, all parties provide the ciphertext of their secret keys key which is encrypted by the accumulated public-key as the accumulated evaluation key. Thirdly, we run the bootstrapping process (or key switching process) on each party's ciphertext and accumulated evaluation key to refresh the ciphertext. Finally, We homomorphically calculate the refreshed ciphertext and decrypt it by the joint secret key. Furthermore, according to the advantages of TFHE-type scheme’s efficient bootstrapping and CKKS scheme supporting approximate data homomorphic computation, we improve the bootstrapping in our general scheme and specifically propose two efficient MKFHE schemes with compact ciphertext. Our work has two advantages. The one is that the ciphertext size of the proposed general scheme is independent of the number of parties, and the homomorphic computation is as efficient as the single-party full homomorphic encryption scheme. When the parties' set is updated, the ciphertext of the original set can continue to be used for homomorphic computation of the new parties' set after refreshed. Another advantage is that only by authorization can a party’s data be used in the homomorphic operation of a set, i.e., all parties need to regenerate their accumulated evaluation key with the set. Compared with the fully dynamic MKFHE scheme, the authorized MKFHE scheme we proposed supports parties to effectively control which set their data.

Category / Keywords: public-key cryptography / Multi-key Fully homomorphic encryption, Lattice cipher, Bootstrapping process, Homomorphic decryption

Date: received 5 Sep 2021

Contact author: tanping2020 at iscas ac cn

Available format(s): PDF | BibTeX Citation

Version: 20210906:074949 (All versions of this report)

Short URL: ia.cr/2021/1131


[ Cryptology ePrint archive ]