IACR News item: 26 March 2013
Kai-Min Chung, Rafael Pass, Sidharth Telang
ePrint ReportWe 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{knowledge-preserving 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 knowledge-preserving 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 computationally-bounded (polynomial-time) adversaries, then assuming the existence of one-way functions (resp. subexponentially-hard one-way functions), for every $\\epsilon>0$, there exists a knowledge-preserving 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 one-way functions.
\\item Finally, even if we restrict to computationally-bounded adversaries, knowledge-preserving 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{non-constructive} interactive coding schemes.
\\end{itemize}
Additional news items may be found on the IACR news page.