Cryptology ePrint Archive: Report 2017/923

Batched Multi-hop Multi-key FHE from ring-LWE with Compact Ciphertext Extension

Long Chen and Zhenfeng Zhang and Xueqing Wang

Abstract: Traditional fully homomorphic encryption (FHE) schemes support computation on data encrypted under a single key. In STOC 2012, López-Alt et al. introduced the notion of multi-key FHE (MKFHE), which allows homomorphic computation on ciphertexts encrypted under different keys. In this work, we focus on MKFHE constructions from standard assumptions and propose a new construction of ring-LWE-based multi-hop MKFHE scheme. Our work is based on Brakerski-Gentry-Vaikuntanathan (BGV) FHE scheme where, in contrast, all the previous works on multi-key FHE with standard assumptions were based on Gentry-Sahai-Waters (GSW) FHE scheme. Therefore, our construction can encrypt ring elements rather than a single bit and naturally inherits the advantages in aspects of the ciphertext/plaintext ratio and the complexity of homomorphic operations. Moveover, the proposed MKFHE scheme supports the Chinese Remainder Theorem (CRT)-based ciphertexts packing technique, achieves $poly\left(k,L,\log n\right)$ computation overhead for $k$ users, circuits with depth at most $L$ and an $n$ dimensional lattice, and gives the first batched MKFHE scheme based on standard assumptions to our knowledge. Furthermore, the ciphertext extension algorithms of previous schemes need to perform complex computation on each ciphertext, while our extension algorithm just needs to generate evaluation keys for the extended scheme. So the complexity of ciphertext extension is only dependent on the number of associated parities but not on the number of ciphertexts. Besides, our scheme also admits a threshold decryption protocol from which a generalized two-round MPC protocol can be similarly obtained as prior works.

Category / Keywords: multikey FHE, batching, BGV FHE

Original Publication (in the same form): IACR-TCC-2017

Date: received 21 Sep 2017

Contact author: chenlong0405 at qq com

Available format(s): PDF | BibTeX Citation

Version: 20170924:224320 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]