**Breaking the Circuit Size Barrier for Secure Computation Under DDH**

*Elette Boyle; Niv Gilboa; 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

**Available format(s): **PDF | BibTeX Citation

**Note: **Preliminary full version of the Crypto 2016 paper.

**Version: **20160902:085231 (All versions of this report)

**Short URL: **ia.cr/2016/585

[ Cryptology ePrint archive ]