Welcome to the resource topic for 2016/585
Title:
Breaking the Circuit Size Barrier for Secure Computation Under DDH
Authors: 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.
ePrint: https://eprint.iacr.org/2016/585
Talk: https://www.youtube.com/watch?v=cOb97Kqq2io
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .