Paper 2017/710
Distributed Computing with Channel Noise
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, and Jared Saia
Abstract
A group of $n$ users want to run a distributed protocol $\pi$ over a network where communication occurs via private pointtopoint channels. Unfortunately, an adversary, who knows $\pi$, is able to maliciously flip bits on the channels. Can we efficiently simulate $\pi$ in the presence of such an adversary? We show that this is possible, even when $L$, the number of bits sent in $\pi$, and $T$, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of $\pi$ that 1) fails with probability at most $\delta$, for any $\delta > 0$; and 2) sends $\tilde{O}(L+T)$ bits, where the $\tilde{O}$ notation hides a $\log(nL/\delta)$ term multiplying $L$. Additionally, we show how to improve this result when the average message size $\alpha$ is not constant. In particular, we give an algorithm that sends $O(L(1 + (1/\alpha) \log(nL/\delta) + T )$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $\alpha$. We note that if $\alpha$ is $\Omega (log(nL/\delta))$, then this improved algorithm sends only $O(L + T)$ bits, and is therefore within a constant factor of optimal.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 interactive communicationinformation theoretic security
 Contact author(s)
 abhiag @ unm edu
 History
 20170725: received
 Short URL
 https://ia.cr/2017/710
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/710, author = {Abhinav Aggarwal and Varsha Dani and Thomas P. Hayes and Jared Saia}, title = {Distributed Computing with Channel Noise}, howpublished = {Cryptology ePrint Archive, Paper 2017/710}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/710}}, url = {https://eprint.iacr.org/2017/710} }