Communication and Randomness Lower Bounds for Secure Computation
Communication and Randomness Lower Bounds for Secure Computation
复制标题
安全计算的通信和随机性下界
DOI：
10.1109/tit.2016.2568207
复制
发表时间：
2015
影响因子：
2.5
通讯作者：
M. Prabhakaran
中科院分区：
文献类型：
--
作者：
Deepesh Data;V. Prabhakaran;M. Prabhakaran
在安全多方计算（MPC）中，相互不信任的用户协作计算其私有数据的函数，而不会向其他用户透露有关其数据的任何额外信息。虽然已知在能够获取私有随机性且通过安全、无噪声和双向链路成对连接的n个用户之间，针对少于n/2个用户的合谋（在诚实但好奇模型中；在恶意模型中阈值为n/3），信息理论上安全的MPC是可能的，但对于安全计算的通信和随机性复杂度，即安全计算所需的通信量和随机性，人们所知相对较少。在本文中，我们运用信息论技术来获得安全MPC的通信和随机性复杂度的下界。我们将自己限制在一个涉及三个用户的具体交互环境中，在该环境下，在诚实但好奇模型中针对单个用户的腐败，所有函数都可安全计算。我们推导出了完美安全情况（即零误差且无信息泄漏）和渐近安全（当块长度趋于无穷时误差概率和信息泄漏消失）的下界。我们的技术包括使用剩余信息的数据处理不等式（即互信息和加奇 - 科尔纳公共信息之间的差距）、一个针对三个用户协议的新信息不等式，以及分布切换的思想，通过该思想可以证明在某些最坏情况下计算出的下界适用于一般情况。我们的下界对于各种感兴趣的函数被证明是紧的。特别是，我们展示了具有通信理想协议的具体函数，即这些函数在网络中的所有链路上同时实现最小通信。此外，我们获得了一个函数的第一个明确示例，该函数在费格等人（第26届ACM计算理论年会，1994年）的安全计算模型中产生比输入长度更高的通信成本，他们已经证明了此类函数的存在。我们还表明，我们的通信界意味着对于许多有趣的函数，MPC协议所需随机性数量的紧下界。
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 cost 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.