Name
Abstract | ||
|---|---|---|
A group of $n$ users want to run a distributed protocol $pi$ over a network where communication occurs via private point-to-point 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 $deltau003e0$; 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 (n L/delta) + T)$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $alpha$. We note that if $alpha$ is $Omegaleft( log (n L/delta) right)$, then this improved algorithm sends only $O(L+T)$ bits, and is therefore within a constant factor of optimal. |
Year | Venue | Field |
|---|---|---|
2017 | IACR Cryptology ePrint Archive | Combinatorics,Computer science,Communication channel,Theoretical computer science,Omega,Message size |
DocType | Volume | Citations |
Journal | 2017 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abhinav Aggarwal | 1 | 1 | 4.06 |
| Varsha Dani | 2 | 432 | 40.05 |
| Thomas P. Hayes | 3 | 659 | 54.21 |
| Jared Saia | 4 | 1019 | 96.95 |