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.

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

BibTeX

@misc{cryptoeprint:2016/585,
      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},
      url = {https://eprint.iacr.org/2016/585}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.