Team for Research in
Ubiquitous Secure Technology

Citation
Sidharth Telang. "Knowledge-Preserving Interactive Coding". Talk or presentation, 10, October, 2013.

Abstract
How can we encode a communication protocol between two parties to become resilient to adversarial errors on the communication channel? If we encode each message in the communication protocol with a “good” error-correcting code (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 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 knowledge-preserving interactive coding, where the interactive coding protocol is required to preserve the “knowledge” transmitted in the original protocol.

Electronic downloads

• Telang_interactivecode-retreat_2013_10_TRUST.pdf · application/pdf · 813 kbytes

• HTML

  Sidharth Telang. <a
  href="http://www.truststc.org/pubs/930.html"
  ><i>Knowledge-Preserving Interactive
  Coding</i></a>, Talk or presentation,  10,
  October, 2013.

• Plain text

  Sidharth Telang. "Knowledge-Preserving Interactive
  Coding". Talk or presentation,  10, October, 2013.

• BibTeX

  @presentation{Telang13_KnowledgePreservingInteractiveCoding,
      author = {Sidharth Telang},
      title = {Knowledge-Preserving Interactive Coding},
      day = {10},
      month = {October},
      year = {2013},
      abstract = {How can we encode a communication protocol between
                two parties to become resilient to adversarial
                errors on the communication channel? If we encode
                each message in the communication protocol with a
                �good� error-correcting code (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
                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
                knowledge-preserving interactive coding, where the
                interactive coding protocol is required to
                preserve the �knowledge� transmitted in the
                original protocol.},
      URL = {http://www.truststc.org/pubs/930.html}
  }
  

Posted by Carolyn Winter on 18 Nov 2013.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.