Computation Over the Noisy Broadcast Channel with Malicious Parties
Computation Over the Noisy Broadcast Channel with Malicious Parties
复制标题
带有恶意方的噪声广播信道的计算
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Raghuvansh R. Saxena
中科院分区：
文献类型：
--
作者：
K. Efremenko;Gillat Kol;Dmitry Paramonov;Raghuvansh R. Saxena
我们研究了n方噪声广播信道与一个常数的恶意方的分数。具体来说，我们假设每个非恶意方都持有一个输入位，并与其他方进行通信，以学习所有非恶意方的输入位。在每一轮通信中，其中一方向所有其他方广播一个比特，并且每一方接收的比特都以固定的恒定概率（独立于每个接收者）进行加密。需要几发子弹？假设没有恶意方，Gallager为上述问题给出了O（n log log n）轮协议，后来被证明是最优的。然而，该协议在存在恶意方的情况下固有地失效。我们提出了一种新颖的n ·~ O（cid：0）√ log n（cid：1）轮协议，即使几乎一半的参与方都是恶意的，也可以解决这个问题。我们的协议使用了一种新型的纠错码，我们称之为局部敏感码，这可能是独立的利益。粗略地说，这些代码将“接近”消息映射到“接近”码字，而不接近的消息映射到相距非常远的码字。我们认为我们的结果是朝着保持属性的交互式编码理论迈出的第一步，即，交互式代码，保留被编码的协议的有用属性。在我们的例子中，无噪声广播信道上的朴素协议，其中所有各方广播其输入位并输出接收到的所有位，即使在存在恶意方的情况下也有效。与Gallager的不同，我们对该协议的模拟保留了原始协议的此属性。
We study the n -party noisy broadcast channel with a constant fraction of malicious parties . Specific-ally, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts a bit to all other parties, and the bit received by each party is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? Assuming there are no malicious parties, Gallager gave an O ( n log log n )-round protocol for the above problem, which was later shown to be optimal. This protocol, however, inherently breaks down in the presence of malicious parties. We present a novel n · ˜ O (cid:0) √ log n (cid:1) -round protocol, that solves this problem even when almost half of the parties are malicious. Our protocol uses a new type of error correcting code, which we call a locality sensitive code and which may be of independent interest. Roughly speaking, these codes map “close” messages to “close” codewords, while messages that are not close are mapped to codewords that are very far apart. We view our result as a first step towards a theory of property preserving interactive coding , i.e., interactive codes that preserve useful properties of the protocol being encoded. In our case, the naive protocol over the noiseless broadcast channel, where all the parties broadcast their input bit and output all the bits received, works even in the presence of malicious parties. Our simulation of this protocol, unlike Gallager’s, preserves this property of the original protocol.
通过高度连接的嘈杂网络进行可靠通信
影响因子：
1.3
作者：
Alon, Noga;Braverman, Mark;Efremenko, Klim;Gelles, Ran;Haeupler, Bernhard
通讯作者：
Haeupler, Bernhard