Threshold Homomorphic Encryption From Provably Secure NTRU

Abstract Homomorphic Encryption (HE) supports computation on encrypted data without the need to decrypt, enabling secure outsourcing of computing to an untrusted cloud. Motivated by application scenarios where private information is offered by different data owners, Multi-Key Homomorphic Encryption (MKHE) and Threshold Homomorphic Encryption (ThHE) were proposed. Unlike MKHE, ThHE schemes do not require expensive ciphertext extension procedures and are therefore as efficient as their underlying single-key HE schemes. In this work, we propose a novel NTRU-type ThHE scheme which caters to the computation scenarios with pre-defined participants. In addition to inheriting the simplicity of NTRU scheme, our construction has no expensive relinearization and correspondingly no costly evaluation keys. Controlling noise to make it increase linearly and then using a wide key distribution, our scheme is immune to the subfield lattice attacks and its security follows from the hardness of the standard R-LWE problem. Finally, based on the {0,1}-linear secret sharing and noise flooding techniques, we design a single round distributed threshold decryption protocol, where the decryption is able to be completed even when only given a subset (say $t$-out-of-$k$) of partial decryptions. To the best of our knowledge, our construction is the first NTRU-type ThHE scheme.