Breaking the Circuit-Size Barrier for Secure Computation Under DDH

Under the Decisional Diffie-Hellman (DDH) assumption, we present a 2-out-of-2 secret sharing scheme that supports a compact homomorphic evaluation of branching programs on the shares.  

 

This yields a number of DDH-based applications, including:

   - A secure 2-party computation protocol for evaluating any branching program or NC1 circuit, where the communication complexity is linear in the input and output size (and only the running time grows with the size of the branching program or circuit).

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

   - A 2-party function secret sharing scheme for general branching programs, with inverse polynomial error probability.

   - A 2-server private information retrieval scheme supporting general searches expressed by branching programs.

 

Prior to our work, similar results could only be achieved using fully homomorphic encryption.

 

Joint work with Niv Gilboa and Yuval Ishai.