Efficient Secure Computation via Homomorphic Secret Sharing
Known approaches for minimizing the communication complexity and round complexity of secure computation protocols are based on fully homomorphic encryption, which in turn relies on a relatively narrow set of assumptions and algebraic structures all related to lattices.
We present a new technique for efficient secure computation via ''homomorphic secret sharing,'' which can be based on discrete-log-type assumptions. More concretely, under the Decisional Diffie-Hellman (DDH) assumption, we construct a 2-out-of-2 secret sharing scheme that supports a compact evaluation of branching programs on the shares. We use this to obtain several new DDH-based results, including low-communication protocols for secure two-party computation and round-efficient protocols for secure multiparty computation. We discuss different optimizations of the basic technique and survey related open problems.
Joint work with Elette Boyle and Niv Gilboa