Secure one-way interactive communication.
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia · arXiv (Cornell University) · 2016
Alice and Bob are connected via a two-way binary channel. This paper describes an algorithm to enable Alice to send a message to Bob when 1) an oblivious adversary flips an unknown number of bits, $T$, on the channel; and 2) the message length $L$, and a desired error probability, $\epsilon$ are public knowledge. With probability at least $1-\epsilon$, our algorithm ensures that Bob receives the correct message, and that Alice and Bob terminate after sending a total of $L + O \left( T + \min \left(T+1,\frac{L}{\log L} \right) \log \left( \frac{L}{\epsilon} \right) \right)$ bits. When $\epsilon = \Omega\left( \frac{1}{poly(L)} \right)$ and $T$ is large, the number of bits sent is $L + O\left( T \right)$, which is asymptotically optimal, assuming a conjecture by Haeupler.