Wiretapping Problem (External Eavesdropping)

Secure network coding

Abstract: Recent work on network coding renders a new view on multicasting in a network. In the paradigm of network coding, the nodes in a network are allowed to encode the information received from the input links. The usual function of switching at a node is a special case of network coding. The advantage of network coding is that the full capacity of the network can be utilized. In this paper, we propose a new model which incorporates network coding and information security. Specifically, a collection of subsets of links is given, and a wiretapper is allowed to access any one (but not more than one) of these subsets without being able to obtain any information about the message transmitted. Our model includes secret sharing as a special case. We present a construction of secure linear network codes provided a certain graph-theoretic sufficient condition is satisfied.


author = {Cai, N. and Yeung, RW},
title = Secure network coding,
journal = {Proceedings of the 2002 IEEE International Symposium
on Information Theory.},
year = {2002}

On the Capacity of Secure Network Coding

author = {Feldman, J. and Malkin, T. and Stein, C. and Servedio, RA},
title = On the capacity of secure network coding,
journal = {Proc. 42nd Annual Allerton Conference on Communication, Control,
and Computing},
year = {2004}

Secure Network Coding via Filtered Secret Sharing


Weakly Secure Network Coding

author = {Bhattad, K. and Narayanan, K.R.},
title = Weakly secure network coding,
journal = {Proc. First Workshop on Network Coding, Theory, and Applications
year = {2005}

Secure Network Coding with a Cost Criterion

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 multicasted 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.


author = {Tan, J. and Medard, M.},
title = { Secure Network Coding with a Cost Criterion },
journal = {Proc. 4th International Symposium on Modeling and Optimization in
Mobile, Ad Hoc and Wireless Networks (WiOpt'06), Apr},
year = {2006}

Internal eavesdropping

L. Lima, M. Medard and J. Barros. Random Linear Network Coding: A Free Cypher?. Accepted for the IEEE International Syposium on Information Theory, Nice, France, June, 2007.

Abstract: We consider the level of information security provided by random linear network coding in network scenarios in which all nodes comply with the communication protocols yet are assumed to be potential eavesdroppers (i.e. "nice but curious"). For this setup, which differs from wiretapping scenarios considered previously, we develop a natural algebraic security criterion, and prove several of its key properties. A preliminary analysis of the impact of network topology on the overall network coding security, in particular for complete directed acyclic graphs, is also included.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.