Communication complexity of secure computation (extended abstract)
Communication complexity of secure computation (extended abstract)
复制标题
DOI：
10.1145/129712.129780
复制
发表时间：
1992-07
期刊：
影响因子：
--
通讯作者：
M. Franklin;M. Yung
中科院分区：
文献类型：
--
作者：
M. Franklin;M. Yung
对单个命题的无记名投票是安全分布式计算的一个例子。目标是让m个参与者联合计算某个n元函数的输出（在本例中为投票之和），同时保护他们的个人输入免受某种形式的不当行为的影响。本文研究了无条件安全多方计算的通信复杂性及其与各种容错模型的关系。我们目前的上限和下限的通信，以及资源之间的权衡。首先，我们考虑完全安全协议的通信复杂度的“直和问题”：如果所有输入都同时计算，那么在k个输入集合上安全地计算单个函数f：Fn → F的通信复杂度是否会比每个输入单独计算的通信复杂度小？我们表明，答案取决于故障模型。在隐私模型中可以获得O（n/log n）的因子（处理器很好奇但正确）;具体地说，当f是n元加法（mod 2）时，我们同时计算f O（n）次的下限为（n2 log n）。在稍强的故障模型（故障停止模式）中不可能有增益;具体地说，当f是GF（q）上的n元加法时，我们证明了在k组输入同时计算f的精确界（kn 2 log q）（对于任何k ≥ 1）。然而，如果人们愿意在容错方面付出额外的代价（从t到t-k+1），那么各种已知的非密码协议（包括上述的“可证明不可并行化”协议！）可以系统地编译以在k组输入处计算一个函数，而不增加通信复杂性。我们的编译技术是基于一个新的压缩思想的多项式为基础的多秘密共享。最后，我们展示了如何编译私有协议到错误检测协议在一个大的节省的一个因素O（n3）（最多的日志因子）在最知名的纠错协议。这是容错协议的一个新概念，当恶意行为不频繁时特别有用，因为在这种情况下错误检测意味着错误纠正。
A secret-ballot vote for a single proposition is an example of a secure distributed computation. The goal is for m participants to jointly compute the output of some n-ary function (in this case, the sum of the votes), while protecting their individual inputs against some form of misbehavior. In this paper, we initiate the investigation of the communication complexity of unconditionally secure multi-party computation, and its relation with various fault-tolerance models. We present upper and lower bounds on communication, as well as tradeoffs among resources. First, we consider the “direct sum problem” for communications complexity of perfectly secure protocols: Can the communication complexity of securely computing a single function f : Fn → F at k sets of inputs be smaller if all are computed simultaneously than if each is computed individually? We show that the answer depends on the failure model. A factor of O(n/log n) can be gained in the privacy model (where processors are curious but correct); specifically, when f is n-ary addition (mod 2), we show a lower bound of &OHgr;(n2 log n) for computing f O(n) times simultaneously. No gain is possible in a slightly stronger fault model (fail-stop mode); specifically, when f is n-ary addition over GF(q), we show an exact bound of &THgr;(kn2 log q) for computing f at k sets of inputs simultaneously (for any k ≥ 1). However, if one is willing to pay an additive cost in fault tolerance (from t to t-k+1), then a variety of known non-cryptographic protocols (including “provably unparallelizable” protocols from above!) can be systematically compiled to compute one function at k sets of inputs with no increase in communication complexity. Our compilation technique is based on a new compression idea of polynomial-based multi-secret sharing. Lastly, we show how to compile private protocols into error-detecting protocols at a big savings of a factor of O(n3) (up to a log factor) over the best known error-correcting protocols. This is a new notion of fault-tolerant protocols, and is especially useful when malicious behavior is infrequent, since error-detection implies error-correction in this case.