Cryptology ePrint Archive: Report 2016/585

Breaking the Circuit Size Barrier for Secure Computation Under DDH

Elette Boyle and Niv Gilboa and Yuval Ishai

Abstract: Under the Decisional Diffie-Hellman (DDH) assumption, we present a 2-out-of-2 secret sharing scheme that supports a compact evaluation of branching programs on the shares. More concretely, there is an evaluation algorithm $\Eval$ with a single bit of output, such that if an input $w\in\{0,1\}^n$ is shared into $(w^0,w^1)$, then for any deterministic branching program $P$ of size $S$ we have that $\Eval(P,w^0)\oplus \Eval(P,w^1)=P(w)$ except with at most $\delta$ failure probability. The running time of the sharing algorithm is polynomial in $n$ and the security parameter $\lambda$, and that of $\Eval$ is polynomial in $S,\lambda$, and $1/\delta$. This applies as a special case to boolean formulas of size $S$ or boolean circuits of depth $\log S$. We also present a public-key variant that enables homomorphic computation on inputs contributed by multiple clients. The above result implies the following DDH-based applications:

- A secure 2-party computation protocol for evaluating any branching program of size $S$, where the communication complexity is linear in the input size and only the running time grows with $S$.

- A secure 2-party computation protocol for evaluating any layered boolean circuit of size $S$ and $m$ outputs with communication complexity $O(S/\log S)+m\cdot\poly(\lambda)$.

-A 2-party {\em function secret sharing} scheme, as defined by Boyle et al. (Eurocrypt 2015), for general branching programs (with inverse polynomial error probability).

- A 1-round 2-server {\em private information retrieval} scheme supporting general searches expressed by branching programs.

Category / Keywords: Secure computation, function secret sharing, private information retrieval, fully homomorphic encryption

Original Publication (in the same form): IACR-Crypto-2016

Date: received 3 Jun 2016, last revised 2 Sep 2016

Contact author: eboyle at alum mit edu, gilboan@bgu ac il, yuvali@cs technion ac il