2nd International ICST Workshop on Network Coding, Theory, and Applications

Research Article

Secure Network Coding with a Cost Criterion

  • @INPROCEEDINGS{10.1109/WIOPT.2006.1666440,
        author={Jianlong  Tan and Muriel  Medard},
        title={Secure Network Coding with a Cost Criterion},
        proceedings={2nd International ICST Workshop on Network Coding, Theory, and Applications},
        publisher={IEEE},
        proceedings_a={NETCOD},
        year={2006},
        month={8},
        keywords={},
        doi={10.1109/WIOPT.2006.1666440}
    }
    
  • Jianlong Tan
    Muriel Medard
    Year: 2006
    Secure Network Coding with a Cost Criterion
    NETCOD
    IEEE
    DOI: 10.1109/WIOPT.2006.1666440
Jianlong Tan1,*, Muriel Medard1,*
  • 1: Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
*Contact email: jianlong@mit.edu, medard@mit.edu

Abstract

Network cost and network security are two of many network parameters that are important to network users. While these two parameters have been separately considered in coded networks (networks that employ network coding), a joint investigation of them both has not been done yet to our knowledge, thus providing the motivation for this work. In this paper, we consider the situation where a set of messages is to be multi-casted across the network, and a known subset of these messages is of interest to a wiretapping adversary. The problem that we attempt to solve is to find a network coding scheme that has both a low network cost and a low probability of the wiretapper being able to retrieve all the messages of interest. We make use of random linear codes in anticipation for decentralized implementation of the scheme, and focus on the problem of finding the multicast subgraph. As an exact algorithmic solution is difficult, we propose two heuristic solutions, and compare their performances to traditional routing through a simulation study. Our results suggest that network coding can be more effective than routing for this low cost and secure data multicast problem, especially when the links are not easily tapped.