Paper 2016/339

Lattice-Based Fully Dynamic Multi-Key FHE with Short Ciphertexts

Zvika Brakerski and Renen Perlman


We present a multi-key fully homomorphic encryption scheme that supports an unbounded number of homomorphic operations for an unbounded number of parties. Namely, it allows to perform arbitrarily many computational steps on inputs encrypted by an a-priori unbounded (polynomial) number of parties. Inputs from new parties can be introduced into the computation dynamically, so the final set of parties needs not be known ahead of time. Furthermore, the length of the ciphertexts, as well as the space complexity of an atomic homomorphic operation, grow only linearly with the current number of parties. Prior works either supported only an a-priori bounded number of parties (Lopez-Alt, Tromer and Vaikuntanthan, STOC '12), or only supported single-hop evaluation where all inputs need to be known before the computation starts (Clear and McGoldrick, Crypto '15, Mukherjee and Wichs, Eurocrypt '16). In all aforementioned works, the ciphertext length grew at least quadratically with the number of parties. Technically, our starting point is the LWE-based approach of previous works. Our result is achieved via a careful use of Gentry's bootstrapping technique, tailored to the specific scheme. Our hardness assumption is that the scheme of Mukherjee and Wichs is circular secure (and thus bootstrappable). A leveled scheme can be achieved under standard LWE.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2016
fully homomorphic encryption
Contact author(s)
renenp @ gmail com
2016-11-18: last of 2 revisions
2016-03-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Renen Perlman},
      title = {Lattice-Based Fully Dynamic Multi-Key FHE with Short Ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2016/339},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.