Paper 2017/672

Coding for interactive communication beyond threshold adversaries

Anat Paskin-Cherniavsky and Slava Radune

Abstract

We revisit the setting of coding for interactive communication, CIC, (initiated by Schulman 96') for non-threshold tampering functions. In a nutshell, in the (special case of) the communication complexity setting, Alice and Bob holding inputs $x,y$ wish to compute a function $g(x,y)$ on their inputs over the identity channel using an interactive protocol. The goal here is to minimize the total communication complexity (CC). A "code" for interactive communication is a compiler transforming any $\pi_0$ working in the communication complexity setting into a protocol $\pi$ evaluating the same function over any channel $f$ picked from a family $\mathcal{F}$. Here $f$ is a function modifying the entire communication transcript. The goal here is to minimize the code's \emph{rate}, which is the CC overhead $CC(\pi)/CC(\pi_0)$ incurred by the compiler. All previous work in coding for interactive communication considered error correction (that is, $g(x,y)$ must be recovered correctly with high probability), which puts a limit of corrupting up to a $1/4$ of the symbols (Braverman and Rao 11'). In this work, we initiate the study of CIC for non-threshold families. We first come up with a robustness notion both meaningful and achievable by CIC for interesting non-threshold families. As a test case, we consider $\mathcal{F}_{\text{bit}}$, where each bit of the codeword is modified independently of the other bits (and all bits can be modified). Our robustness notion is an enhanced form of error-detection, where the output of the protocol is distributed over $\{\bot,f(x,y)\}$, and the distribution does not depend on $x,y$. This definition can be viewed as enhancing error detection by non malleability (as in the setting of non-malleable codes introduced by Dzembowski et. al. 10'). We devise CIC for several interesting tampering families (including $\mathcal{F}_{\text{bit}}$). As a building block, we introduce the notion of MNMC (non malleable codes for multiple messages), which may be of independent interest.