On Complete Primitives for Fairness
On Complete Primitives for Fairness
复制标题
论公平的完整原语
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Sahai
中科院分区：
文献类型：
--
作者：
Dov S. Gordon;Yuval Ishai;T. Moran;R. Ostrovsky;A. Sahai
对于具有中止的安全两方和多方计算，基元完全的分类在文献中已经被广泛研究。然而，对于公平安全的计算，在(粗略地说)所有各方要么学习输出，要么不学习输出的情况下，完全原语的问题在很大程度上仍然没有得到研究。在这项工作中，我们启动了对允许公平计算的原语的完备性的严格研究。我们给出了以下结果：
为了公平起见，没有“短”的原语是完全的。与其他安全两方计算的安全概念相比，我们证明了对于公平的安全计算，没有大小为O(Logk)的原语是完备的，其中k是安全参数。即使我们可以在对原语的调用中强制并行性，情况也是如此(即，在向所有原语发送输入之前，对手不会从并行调用中的任何原语获得输出)。无论任何计算假设，这一否定结果都成立。
公平等级制度。我们通过展示“公平等级”的存在来进一步阐明公平的图景。我们证明了对于每个“短”的L=O(Logk)，没有协议对任何L比特基元进行(串行)访问，即使是(L+1)比特的同步广播也不能被用来构造。
结果是积极的。为了补充否定的结果，我们展示了一个k比特原语，它对于两方公平安全计算是完全的。我们展示了如何将这一结果推广到多方设置。
公平组合器。我们还介绍了从可能有缺陷的原语构造公平安全计算的协议的问题。我们证明，当大多数实例都是诚实的时，这是可能的。另一方面，我们证明了这一结果是严格的：如果一半(或更多)的实例可能是恶意的，那么为了公平起见，没有功能是完整的。
For secure two-party and multi-party computation with abort, classification of which primitives are complete has been extensively studied in the literature. However, for fair secure computation, where (roughly speaking) either all parties learn the output or none do, the question of complete primitives has remained largely unstudied. In this work, we initiate a rigorous study of completeness for primitives that allow fair computation. We show the following results:
No “short” primitive is complete for fairness. In surprising contrast to other notions of security for secure two-party computation, we show that for fair secure computation, no primitive of size O(logk) is complete, where k is a security parameter. This is the case even if we can enforce parallelism in calls to the primitives (i.e., the adversary does not get output from any primitive in a parallel call until it sends input to all of them). This negative result holds regardless of any computational assumptions.
A fairness hierarchy. We clarify the fairness landscape further by exhibiting the existence of a “fairness hierarchy”. We show that for every “short” l=O(logk), no protocol making (serial) access to any l-bit primitive can be used to construct even a (l+1)-bit simultaneous broadcast.
Positive results. To complement the negative results, we exhibit a k-bit primitive that is complete for two-party fair secure computation. We show how to generalize this result to the multi-party setting.
Fairness combiners. We also introduce the question of constructing a protocol for fair secure computation from primitives that may be faulty. We show that this is possible when a majority of the instances are honest. On the flip side, we show that this result is tight: no functionality is complete for fairness if half (or more) of the instances can be malicious.