Paper 2018/1054

Efficient Multi-key FHE with short extended ciphertexts and less public parameters

Tanping Zhou, Ningbo Li, Xiaoyuan Yang, Yiliang Han, and Wenchao Liu


Multi-Key Full Homomorphic Encryption (MKFHE) can perform arbitrary operations on encrypted data under different public keys (users), and the final ciphertext can be jointly decrypted by all involved users. Therefore, MKFHE has natural advantages and application value in security multi-party computation (MPC). The MKFHE scheme based on Brakerski-Gentry-Vaikuntanathan (BGV) inherits the advantages of BGV FHE scheme in aspects of encrypting a ring element, the ciphertext/plaintext ratio, and supporting the Chinese Remainder Theorem (CRT)-based ciphertexts packing technique. However some weaknesses also exist such as large ciphertexts and keys, and complicated process of generating evaluation keys. In this paper, we present an efficient BGV-type MKFHE scheme. Firstly, we construct a nested ciphertext extension for BGV and separable ciphertext extension for Gentry-Sahai-Waters (GSW), which can reduce the size of the extended ciphertexts about a half. Secondly, we apply the hybrid homomorphic multiplication between RBGV ciphertext and RGSW ciphertext to the generation process of evaluation keys, which can significantly reduce the amount of input/output ciphertexts and improve the efficiency. Finally, we construct a directed decryption protocol which allows the evaluated ciphertext to be decrypted by any target user, thereby enhancing the ability of data owner to control their own plaintext, and abolish the limitation in current MKFHE schemes that the evaluated ciphertext can only be decrypted by users involved in homomorphic evaluation.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. IEEE ACCESS
Multi-key FHEBGV schemeciphertext extensionpublic parameterevaluation keyhybrid homomorphic multiplication.
Contact author(s)
850301775 @ qq com
2019-06-25: revised
2018-11-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tanping Zhou and Ningbo Li and Xiaoyuan Yang and Yiliang Han and Wenchao Liu},
      title = {Efficient Multi-key {FHE} with short extended ciphertexts and less public parameters},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1054},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.