LogStack: Stacked Garbling with O(b log b) Computation
LogStack: Stacked Garbling with O(b log b) Computation
复制标题
DOI：
10.1007/978-3-030-77883-5_1
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
David Heath;V. Kolesnikov
中科院分区：
文献类型：
--
作者：
David Heath;V. Kolesnikov
任意程序的安全两方计算（2 PC）可以有效地使用乱码电路（GC）来实现。直到最近，人们普遍认为，与整个程序成比例的GC，包括由于条件分支而完全丢弃的程序部分，必须通过网络传输。最近的工作表明，这种信念是错误的，通信只与最长的程序执行路径成比例就足够了（Heath和Kolesnikov，2009年）。虽然这项最新的工作减少了所需的通信，但它增加了计算量。对于具有b分支的条件，参与者使用计算（传统GC仅使用O（B））。我们的方案将堆叠混淆计算从减少到，而不增加通信。的计算量增加的原因是不经意地收集在评估非活动分支时出现的垃圾标签。垃圾是由一个产生成本很高的多路复用器收集的。在高层次上，我们重新设计了堆栈和垃圾收集，以避免二次缩放。我们的构造也更有空间效率：算法需要O（B）空间，而我们只使用空间。这种空间效率甚至允许适度的设置来处理大量的分支。我们跟踪这种需求的来源，形式化一个简单而自然的基础乱码方案的假设，并删除依赖RO：是安全的标准模型。然而，可以使用基于非标准假设的典型GC技巧来实例化，例如自由XOR和半门，因此可以高效地实现。我们实现了（在RO模型中，基于半门混淆）并报告性能。就挂钟时间而言，对于少于16个分支，我们的性能与的相当;对于较大的分支因子，我们的方法明显优于。例如，给定1024个分支，我们的方法更快。
Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). Until recently, it was widely believed that a GC proportional to the entire program, including parts of the program that are entirely discarded due to conditional branching, must be transmitted over a network. Recent work shows that this belief isfalse, and that communication proportional only to the longest program execution path suffices (Heath and Kolesnikov, CRYPTO 20, ). Although this recent work reduces needed communication, itincreasescomputation. For a conditional withbbranches, the players usecomputation (traditional GC uses onlyO(b)).Our schemereduces stacked garbling computation fromtowithnoincrease in communication over . The cause of ’s increased computation is the oblivious collection ofgarbage labelsthat emerge during the evaluation of inactive branches. Garbage is collected by amultiplexerthat is costly to generate. At a high level, we redesign stacking and garbage collection to avoid quadratic scaling.Our construction is also morespace efficient: algorithms requireO(b) space, while ours use onlyspace. This space efficiency allows even modest setups to handle large numbers of branches.assumes a random oracle (RO). We track the source of this need, formalize a simple and natural added assumption on the base garbling scheme, and remove reliance on RO:is secure in the standard model. Nevertheless,can be instantiated with typical GC tricks based on non-standard assumptions, such as free XOR and half-gates, and hence can be implemented with high efficiency.We implemented(in the RO model, based on half-gates garbling) and report performance. In terms of wall-clock time and for fewer than 16 branches, our performance is comparable to ’s; for larger branching factors, our approach clearly outperforms . For example, given 1024 branches, our approach isfaster.