Skip to main content

Computation over the Noisy Broadcast Channel with Malicious Parties

Author(s): Efremenko, Klim; Kol, Gillat; Paramonov, Dmitry; Saxena, Raghuvansh R

To refer to this page use:
Abstract: We study the n-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, 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 𝒪(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 ⋅ 𝒪̃(√{log n})-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.
Publication Date: 2021
Citation: Efremenko, Klim, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. "Computation over the noisy broadcast channel with malicious parties." In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 185 (2021): pp. 82:1-82:19. doi:10.4230/LIPIcs.ITCS.2021.82
DOI: 10.4230/LIPIcs.ITCS.2021.82
ISSN: 1868-8969
Pages: 82:1 - 82:19
Type of Material: Conference Article
Journal/Proceeding Title: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.