Cryptology ePrint Archive: Report 2018/1054

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

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

Abstract: 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.

Category / Keywords: public-key cryptography / Multi-key FHE, BGV scheme, ciphertext extension, public parameter, evaluation key, hybrid homomorphic multiplication.

Original Publication (with minor differences): IEEE ACCESS

Date: received 31 Oct 2018, last revised 25 Jun 2019

Contact author: 850301775 at qq com

Available format(s): PDF | BibTeX Citation

Version: 20190625:124523 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]