Renen Perlman: Lattice-Based Fully Dynamic Multi-Key FHE with Short Ciphertexts

Abstract: A fully homomorphic encryption scheme (FHE) allows one to convert an encryption of a message into an encryption of some arbitrary function of that message, without compromising the secrecy of the encrypted message. A fully dynamic encryption scheme (FDE) supports evaluation of arbitrary functions on inputs encrypted under different keys. Moreover, new users, having new keys, can be introduced into the computation at any time, not requiring any coordination between the parties ahead of time.  

In this talk, I will present a construction of an FDE scheme, which allows to perform arbitrarily many computational steps on inputs encrypted by an a-priori unbounded (polynomial) number of parties. 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 (L opez-Alt, Tromer and Vaikuntanthan, STOC '12), or only supported single-hop evaluation where all parties 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.