Theory of Computing Seminar

Secure computation is a fundamental cryptographic notion, enabling mutually distrusting parties to jointly compute on private inputs while hiding the inputs themselves. Known approaches for minimizing the communication complexity of general 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 succinct 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 succinct protocols for secure two-party computation and round-efficient protocols for secure multiparty computation.

Joint work with Niv Gilboa and Yuval Ishai.