Multi-Key Homomorphic Secret Sharing

Homomorphic secret sharing (HSS) is a distributed analogue of fully homomorphic encryption (FHE) where following an input-sharing phase, two or more parties can locally compute a function over their private inputs to obtain shares of the function output.

Over the last decade, HSS schemes have been constructed from an array of different assumptions. However, all existing HSS schemes, except ones based on assumptions known to imply multikey FHE, require a public-key infrastructure (PKI) or a correlated setup between parties. This limitation carries over to many applications of HSS.

In this work, we construct multi-key homomorphic secret sharing (MKHSS), where given only a common reference string (CRS), two parties can secret share their inputs to each other and then perform local computations as in HSS, eliminating the need for PKI or a correlated setup. Specifically, we present the first MKHSS schemes supporting all NC 1 computations from either the decisional Diffie-Hellman (DDH) assumption, the decisional composite residuosity (DCR) assumption, or DDH-like assumptions in class group.

Our constructions imply the following applications in the CRS model:

-Succinct two-round secure computation. Under the same assumptions as our MKHSS schemes, we construct a succinct, two-round, two-party secure computation protocol for NC 1 circuits. Previously, such a result was only known from the learning with errors assumption. -Attribute-based NIKE. Under DCR or class group assumptions, we construct noninteractive key exchange (NIKE) protocols where two parties agree on a key if and only if their secret attributes satisfy a public NC 1 predicate. This significantly generalizes the existing notion of password-based NIKE. -Public-key PCFs. Under DCR or class group assumptions, we construct public-key pseudorandom correlation functions (PCFs) for any NC 1 correlation. This yields the first publickey PCFs for Beaver triples (and more) from non-lattice assumptions. -Silent MPC. Under DCR or class group assumptions, we construct a p-party secure computation protocol in the silent preprocessing model where the preprocessing phase has communication O(p), ignoring polynomial factors. All prior protocols that do not rely on multi-key FHE techniques require Ω(p 2 ) communication.