Must the Communication Graph of MPC Protocols be an Expander?
Must the Communication Graph of MPC Protocols be an Expander?
复制标题
DOI：
10.1007/s00145-023-09460-8
复制
发表时间：
2018-08
影响因子：
3
通讯作者：
Elette Boyle;Ran Cohen;Deepesh Data;Pavel Hubácek
中科院分区：
文献类型：
--
作者：
Elette Boyle;Ran Cohen;Deepesh Data;Pavel Hubácek
不完备通信网络上的安全多方计算(MPC)在两个主要模型下被研究：(1)部分网络是先验固定的，因此可能发生破坏，依赖于其结构；(2)通信图中的边被动态地确定为协议的一部分。虽然大量的文献已经成功地描绘出在固定图模型中支持安全计算的图结构的可行性和局限性(包括强经典下界)，但这些界限不适用于后一种动态图环境，后者最近看到了令人振奋的新结果，但仍然相对未被探索。在这项工作中，我们在动态图模型中启动了类似的预测控制的基础研究。作为第一步，我们研究了图扩张的性质。所有现有的协议(隐式或显式地)生成的通信图都是扩展器，但尚不清楚这是否是固有的。我们的结果包括两种类型(对于恒定分数的腐败)：上界：我们证明了安全协议的诱导通信图不是扩展图，在广泛的设置(计算、信息理论、低局部性，甚至具有低局部性和自适应安全性)下，每种协议都假定某种形式的输入无关设置。下界：在具有自适应腐败的普通模型(未设置)中，我们证明了对于某些功能，没有协议能够针对所有对抗策略保持非扩展通信图。我们的下界只依赖于协议的正确性(而不是保密性)，并且需要令人惊讶的精细论证。更一般地，我们为分析MPC协议的演化通信图提供了一个形式化的框架，为研究安全计算与更一般的图性质之间的关系提供了一个起点。
Secure multiparty computation (MPC) on incomplete communication networks has been studied within two primary models: (1) where a partial network is fixed a priori, and thus corruptions can occur dependent on its structure, and (2) where edges in the communication graph are determined dynamically as part of the protocol. Whereas a rich literature has succeeded in mapping out the feasibility and limitations of graph structures supporting secure computation in the fixed-graph model (including strong classical lower bounds), these bounds do not apply in the latter dynamic-graph setting, which has recently seen exciting new results, but remains relatively unexplored. In this work, we initiate a similar foundational study of MPC within the dynamic-graph model. As a first step, we investigate the property of graphexpansion. All existing protocols (implicitly or explicitly) yield communication graphs which are expanders, but it is not clear whether this is inherent. Our results consist of two types (for constant fraction of corruptions):Upper bounds: We demonstrate secure protocols whose induced communication graphs arenotexpander graphs, within a wide range of settings (computational, information theoretic, with low locality, even with low localityandadaptive security), each assuming some form of input-independent setup.Lower bounds: In the plain model (no setup) with adaptive corruptions, we demonstrate that for certain functionalities,noprotocol can maintain a non-expanding communication graph against all adversarial strategies. Our lower bound relies only on protocol correctness (not privacy) and requires a surprisingly delicate argument.More generally, we provide a formal framework for analyzing the evolving communication graph of MPC protocols, giving a starting point for studying the relation between secure computation and further, more general graph properties.