Paper 2013/160
Interactive Coding, Revisited
KaiMin Chung, Rafael Pass, and Sidharth Telang
Abstract
How can we encode a communication protocol between two parties to become resilient to adversarial errors on the communication channel? This question dates back to the seminal works of Shannon and Hamming from the 1940's, initiating the study of errorcorrecting codes (ECC). But, even if we encode each message in the communication protocol with a ``good'' ECC, the error rate of the encoded protocol becomes poor (namely $O(1/m)$ where $m$ is the number of communication rounds). Towards addressing this issue, Schulman (FOCS'92, STOC'93) introduced the notion of \emph{interactive coding}. We argue that whereas the method of separately encoding each message with an ECC ensures that the encoded protocol carries the same amount of information as the original protocol, this may no longer be the case if using interactive coding. In particular, the encoded protocol may completely leak a player's private input, even if it would remain secret in the original protocol. Towards addressing this problem, we introduce the notion of \emph{knowledgepreserving interactive coding}, where the interactive coding protocol is required to preserve the ``knowledge'' transmitted in the original protocol. Our main results are as follows. \begin{itemize} \item The method of separately applying ECCs to each message is essentially optimal: No knowledgepreserving interactive coding scheme can have an error rate of $1/m$, where $m$ is the number of rounds in the original protocol. \item If restricting to computationallybounded (polynomialtime) adversaries, then assuming the existence of oneway functions (resp. subexponentiallyhard oneway functions), for every $\epsilon>0$, there exists a knowledgepreserving interactive coding schemes with constant error rate and information rate $n^{\epsilon}$ (resp. $1/\polylog(n)$) where $n$ is the security parameter; additionally to achieve an error of even $1/m$ requires the existence of oneway functions. \item Finally, even if we restrict to computationallybounded adversaries, knowledgepreserving interactive coding schemes with constant error rate can have an information rate of at most $o(1/\log n)$. This results applies even to \emph{nonconstructive} interactive coding schemes. \end{itemize}
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 interactive codingknowledge preservingsimulation paradigmerror correcting codes
 Contact author(s)
 chung @ cs cornell edu
 History
 20130326: received
 Short URL
 https://ia.cr/2013/160
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/160, author = {KaiMin Chung and Rafael Pass and Sidharth Telang}, title = {Interactive Coding, Revisited}, howpublished = {Cryptology ePrint Archive, Paper 2013/160}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/160}}, url = {https://eprint.iacr.org/2013/160} }