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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Error correcting codescoding for interactive communicationnon malleable codes.
Contact author(s)
anps83 @ gmail com
History
2017-07-06: received
Short URL
https://ia.cr/2017/672
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/672,
      author = {Anat Paskin-Cherniavsky and Slava Radune},
      title = {Coding for interactive communication beyond threshold adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2017/672},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/672}},
      url = {https://eprint.iacr.org/2017/672}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.