Paper 2016/585

Breaking the Circuit Size Barrier for Secure Computation Under DDH

Elette Boyle, Niv Gilboa, and Yuval Ishai


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.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2016
Secure computationfunction secret sharingprivate information retrievalfully homomorphic encryption
Contact author(s)
eboyle @ alum mit edu
gilboan @ bgu ac il
yuvali @ cs technion ac il
2016-09-02: last of 3 revisions
2016-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Niv Gilboa and Yuval Ishai},
      title = {Breaking the Circuit Size Barrier for Secure Computation Under {DDH}},
      howpublished = {Cryptology ePrint Archive, Paper 2016/585},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.