On perfectly secure communication over arbitrary networks
On perfectly secure communication over arbitrary networks
复制标题
DOI：
10.1145/571825.571858
复制
发表时间：
2002-07
期刊：
影响因子：
--
通讯作者：
M. Kumar;Pranava Goundan;K. Srinathan;C. Pandu Rangan
中科院分区：
文献类型：
--
作者：
M. Kumar;Pranava Goundan;K. Srinathan;C. Pandu Rangan
我们研究了网络连接和完全安全的消息传输的腐败影响下的广义拜占庭对手的相互作用。众所周知，在阈值攻击模型中，拜占庭攻击者可以破坏n个参与者（节点）中的任何t个，当且仅当底层同步网络是（2 t + 1）-连接时，任何一对参与者之间的完全安全通信是可能的。严格推广这些结果的非阈值设置，我们表明，完全安全的通信之间的任何一对球员是可能的，当且仅当工会没有两个集的对手结构是一个顶点割集的同步网络。传输协议的计算和通信复杂度是网络规模和敌手结构的最大基的多项式。
We study the interplay of network connectivity and perfectly secure message transmission under the corrupting influence of generalized Byzantine adversaries. It is known that in the threshold adversary model, where the Byzantine adversary can corrupt upto any t among the n players (nodes), perfectly secure communication among any pair of players is possible if and only if the underlying synchronous network is (2t + 1)-connected. Strictly generalizing these results to the non-threshold setting, we show that perfectly secure communication among any pair of players is possible if and only if the union of no two sets in the adversary structure is a vertex cutset of the synchronous network. The computation and communication complexities of the transmission protocol are polynomial in the size of the network and the maximal basis of the adversary structure.