Welcome to the resource topic for 2017/672
Title:
Coding for interactive communication beyond threshold adversaries
Authors: Anat Paskin-Cherniavsky, 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.
ePrint: https://eprint.iacr.org/2017/672
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .