License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.82
URN: urn:nbn:de:0030-drops-136215
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13621/
Efremenko, Klim ;
Kol, Gillat ;
Paramonov, Dmitry ;
Saxena, Raghuvansh R.
Computation over the Noisy Broadcast Channel with Malicious Parties
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.
BibTeX - Entry
@InProceedings{efremenko_et_al:LIPIcs.ITCS.2021.82,
author = {Klim Efremenko and Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena},
title = {{Computation over the Noisy Broadcast Channel with Malicious Parties}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {82:1--82:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13621},
URN = {urn:nbn:de:0030-drops-136215},
doi = {10.4230/LIPIcs.ITCS.2021.82},
annote = {Keywords: Broadcast Network, Malicious Parties, Communication Complexity}
}
|
Keywords: |
|
Broadcast Network, Malicious Parties, Communication Complexity |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
