Efficient Secure Computation via Homomorphic Secret Sharing

Yuval Ishai


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

Time and Place

Wednesday, March 15, 4:15pm
Gates 463