Single-Unicast Secure Network Coding and Network Error Correction are as Hard as Multiple-Unicast Network Coding

Wentao Huang, Tracey Ho, Michael Langberg, Jorg Kliewer

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

This paper reduces multiple-unicast network coding to single-unicast secure network coding and single-unicast network error correction. Specifically, we present reductions that map an arbitrary multiple-unicast network coding instance to a unicast secure network coding instance in which at most one link is eavesdropped, or a unicast network error correction instance in which at most one link is erroneous, such that a rate tuple is achievable in the multiple-unicast network coding instance if and only if a corresponding rate is achievable in the unicast secure network coding instance, or in the unicast network error correction instance. Conversely, we show that an arbitrary unicast secure network coding instance in which at most one link is eavesdropped can be reduced back to a multiple-unicast network coding instance. In addition, we show that the capacity of a unicast network error correction instance in general is not (exactly) achievable.

Original languageEnglish (US)
Pages (from-to)4496-4512
Number of pages17
JournalIEEE Transactions on Information Theory
Volume64
Issue number6
DOIs
StatePublished - Jun 2018

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Network coding
  • capacity
  • equivalence
  • error correction
  • security

Fingerprint

Dive into the research topics of 'Single-Unicast Secure Network Coding and Network Error Correction are as Hard as Multiple-Unicast Network Coding'. Together they form a unique fingerprint.

Cite this