Threshold Homomorphic Secret Sharing: Definitions and Constructions

Homomorphic Secret Sharing (HSS) allows clients to split their inputs among several servers, and supports the servers to homomorphically evaluate public functions over their local shares, such that the function value of the inputs can be efficiently reconstructed from the output shares of the servers. For all existing schemes, all servers are required to participate in the reconstruction process, and the reconstruction will fail even if one server is missing. In this work, we study HSS that supports threshold reconstruction, where the reconstruction still works even if a few servers fail. We first formalize the syntax and security notions of threshold HSS in the public-key setup model, which is a popular model in the literature. Then we present a new generic construction of HSS, which is the first construction that enjoys both threshold reconstruction and public reconstruction. To this end, we introduce a refined version of functional encryption, named HSS-friendly functional encryption. Furthermore, we instantiate our construction with quadratic functional encryption schemes modified from existing works. Compared with the state-of-the-art, our concrete scheme achieves the threshold reconstruction at the expense of slightly increasing the communication complexity.