Computation over the noisy broadcast channel with malicious parties

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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 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 · Õ(√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.

Original languageEnglish (US)
Title of host publication12th Innovations in Theoretical Computer Science Conference, ITCS 2021
EditorsJames R. Lee
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771771
StatePublished - Feb 1 2021
Event12th Innovations in Theoretical Computer Science Conference, ITCS 2021 - Virtual, Online
Duration: Jan 6 2021Jan 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference12th Innovations in Theoretical Computer Science Conference, ITCS 2021
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Software


  • Broadcast network
  • Communication complexity
  • Malicious parties


Dive into the research topics of 'Computation over the noisy broadcast channel with malicious parties'. Together they form a unique fingerprint.

Cite this