Efficient Secure Computation via Homomorphic Secret Sharing
Yuval Ishai
Abstract:
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