Yuval Ishai: Succinct Secure Computation from DDH

Tuesday, November 8, 2016 - 4:00pm to 5:00pm
Light Refreshments at 3:50pm
Patil/Kiva G449
Yuval Ishai, Technion and UCLA



Fully homomorphic encryption (FHE) is a powerful cryptographic tool that can be used to minimize the communication complexity of secure computation protocols. However, known FHE schemes rely on a relatively narrow set of assumptions and algebraic structures that are all related to lattices.


We present a new technique for succinct secure computation that replaces FHE by ''homomorphic secret sharing'' and 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.


Our technique yields a number of new DDH-based applications, including:

- A secure 2-party protocol for evaluating branching programs or NC1 circuits, where the communication complexity is linear in the input and output size and only the time complexity grows with the branching program or circuit size.

- A secure 2-party protocol for evaluating any leveled boolean circuit of size S with communication complexity O(S/logS).

- A secure k-party protocol for evaluating general circuits using only two rounds of interaction given a public-key infrastructure.


Joint work with Elette Boyle and Niv Gilboa