Breaking the Circuit Size Barrier for Secure Computation Under DDH
Breaking the Circuit Size Barrier for Secure Computation Under DDH
复制标题
DOI：
10.1007/978-3-662-53018-4_19
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
Elette Boyle;N. Gilboa;Yuval Ishai
中科院分区：
文献类型：
--
作者：
Elette Boyle;N. Gilboa;Yuval Ishai
在决策性迪菲-赫尔曼（DDH）假设下，我们提出了一个2/2秘密共享方案，该方案支持对共享上的分支程序进行紧凑评估。更具体地说，有一个评估算法与一个单一的输出位，这样，如果一个输入共享到，那么对于任何确定性分支程序P的大小S，我们有，除了最多失败概率。共享算法的运行时间在安全参数下是多项式，而共享算法的运行时间在，和。这适用于sizeS的布尔公式或深度的布尔回路的特殊情况。上述结果暗示了以下基于DDH的应用：一个安全的两方计算协议，用于计算大小为S的任何分支程序或公式，其中通信复杂度与输入大小成线性关系，只有运行时间随S增长;一个安全的两方计算协议，用于计算大小为S且具有通信复杂度的分层布尔电路;一个两方函数秘密共享方案，如波义耳等人所定义的.（Eurocrypt 2015），对于一般分支程序（具有逆多项式错误概率）。一个支持由分支程序表示的一般搜索的1轮2服务器私有信息检索方案。在我们的工作之前，只能使用全同态加密来实现类似的结果。我们希望，我们的方法将导致更实际的替代方案，已知的全同态加密方案的背景下，低通信安全计算。
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 algorithmwith a single bit of output, such that if an inputis shared into, then for any deterministic branching programPof sizeSwe have thatexcept with at mostfailure probability. The running time of the sharing algorithm is polynomial innand the security parameter, and that ofis polynomial in, and. This applies as a special case to boolean formulas of sizeSor boolean circuits of depth. 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 or formula of sizeS, where the communication complexity is linear in the input size and only the running time grows withS.A secure 2-party computation protocol for evaluating layered boolean circuits of sizeSwith communication complexity.A 2-partyfunction secret sharingscheme, as defined by Boyle et al. (Eurocrypt 2015), for general branching programs (with inverse polynomial error probability).A 1-round 2-serverprivate information retrievalscheme supporting general searches expressed by branching programs.Prior to our work, similar results could only be achieved using fully homomorphic encryption. We hope that our approach will lead to more practical alternatives to known fully homomorphic encryption schemes in the context of low-communication secure computation.