Paper 2016/585

Breaking the Circuit Size Barrier for Secure Computation Under DDH

Elette Boyle, 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.

Note: Preliminary full version of the Crypto 2016 paper.