Fast Interactive Coding against Adversarial Noise

Consider two parties who wish to communicate in order to execute some interactive protocol pi. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits arbitrarily, thus interrupting the execution of (which was designed for an error-free channel). If pi only contains a single long message, then a good error correcting code would overcome the noise with only a constant overhead in communication. However, this solution is not applicable to interactive protocols consisting of many short messages. Schulman [1992, 1993] introduced the notion of interactive coding: A simulator that, given any protocol pi, is able to simulate it (i.e., produce its intended transcript) even in the presence of constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. However, the running time of Schulman's simulator, and of all simulators that followed, has been exponential (or subexponential) in the communication complexity of pi (which we denote by N). In this work, we present three efficient simulators, all of which are randomized and have a certain failure probability (over the choice of coins). The first runs in time poly(N), has failure probability roughly 2(-N), and is resilient to 1/32-fraction of adversarial error. The second runs in time 0(N log N), has failure probability roughly 2-N, and is resilient to some constant fraction of adversarial error. The third runs in time 0(N), has failure probability 1/poly(N), and is resilient to some constant fraction of adversarial error. (Computational complexity is measured in the RAM model.) The first two simulators can be made deterministic if they are a priori given a random string (which may be known to the adversary ahead of time). In particular, the simulators can be made to be nonuniform and deterministic (with equivalent performance). Categories and Subject Descriptors: E.4 [Coding and Information Theory]: Error control codes; F.2 [Analysis of Algorithms and Problem Complexity]