Multi-key Fully Homomorphic Encryption Scheme  with Compact Ciphertexts

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

Paper 2021/1131

Multi-key Fully Homomorphic Encryption Scheme with Compact Ciphertexts

Tanping Zhou

Long Chen

Xiaoliang Che

Wenchao Liu

Zhenfeng Zhang

Xiaoyuan Yang

Abstract

Multi-Key fully homomorphic encryption (MKFHE) allows computations on data encrypted by different parties. One disadvantage of previous MKFHE schemes is that the ciphertext size increases linearly or squarely with respect to the number of parties. It incurs a heavy communication and computation burden for the homomorphic evaluation, especially when the number of involved parties is large. In this paper, we propose the first method to construct MKFHE scheme while keeping the size of the ciphertext and corresponding evaluation key to be independent of the number of parties during the homomorphic evaluation. Specifically, we construct efficient compact MKFHE schemes with various advantages. On the one hand, we show how to construct compact MKFHE schemes which support the homomorphic encryption of ring elements and are friendly to floating point numbers. On the other hand, we give a compact MKFHE scheme that supports high efficient bootstrapping. In our paper, we show a novel method to reduce the cost of generating these evaluation keys from a quadratic time to a linear time with respect to the number of parties.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Multi-key Fully homomorphic encryption Lattice cipher Bootstrapping process Homomorphic decryption
Contact author(s): tanping2020 @ iscas ac cn
History: 2022-05-31: revised; 2021-09-06: received; See all versions
Short URL: https://ia.cr/2021/1131
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1131,
      author = {Tanping Zhou and Long Chen and Xiaoliang Che and Wenchao Liu and Zhenfeng Zhang and Xiaoyuan Yang},
      title = {Multi-key Fully Homomorphic Encryption Scheme  with Compact Ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1131},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1131}},
      url = {https://eprint.iacr.org/2021/1131}
}