...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Communication and Randomness Lower Bounds for Secure Computation
【24h】

Communication and Randomness Lower Bounds for Secure Computation

机译：通信和随机性下界，用于安全计算

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication - ost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.
机译：在安全的多方计算（MPC）中，互不信任的用户将协作以计算其私有数据的功能，而不会向其他用户透露有关其数据的任何其他信息。虽然众所周知，理论上安全的MPC信息在n个有权访问私有随机性的用户中是可能的，并且通过安全，无噪声和双向链接成对连接，以防止少于n / 2个用户的勾结（在诚实但好奇的模型中） ；阈值在恶意模型中为n / 3），对安全计算的通信和随机性复杂性（即安全计算所需的通信量和随机性）了解得很少。在本文中，我们采用信息理论技术来获得安全MPC的通信和随机性复杂度的下限。我们将自己限制在一个涉及三个用户的具体交互式设置下，在该设置下，可以安全地计算所有功能，以防止诚实但好奇的模型中单个用户的损坏。我们为完美的安全情况（即零错误且无信息泄漏）和渐近安全性（当块长度达到∞时错误和信息泄漏的可能性消失）得出下界。我们的技术包括使用残差信息的数据处理不等式（即，互信息和Ga'cs-Körner通用信息之间的差距），三用户协议的新信息不等式以及通过分布下限计算下限的想法在某些最坏的情况下，可以证明适用于一般情况。对于各种感兴趣的功能，我们的下限显示得很严格。特别地，我们示出了具有通信理想协议的具体功能，即，其在网络中的所有链路上同时实现最小通信。同样，在Feige等人的安全计算模型中，我们获得了一个函数的第一个明确示例，该函数的通信-ost比输入长度长。 （第26届ACM计算理论年度研讨会，1994年），他证明了这种功能的存在。我们还表明，我们的通信界限暗示着MPC协议对许多有趣功能所要求的随机性的严格下限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号