A Caltech Library Service

Resilient Network Coding in the Presence of Byzantine Adversaries

Jaggi, Sidharth and Langberg, Michael and Katti, Sachin and Ho, Tracey and Katabi, Dina and Médard, Muriel and Effros, Michelle (2008) Resilient Network Coding in the Presence of Byzantine Adversaries. IEEE Transactions on Information Theory, 54 (6). pp. 2596-2603. ISSN 0018-9448.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding. This paper introduces distributed polynomial-time rate-optimal network codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam zO links, our first algorithm achieves a rate of C - 2zO, where C is the network capacity. In contrast, when the adversary has limited eavesdropping capabilities, we provide algorithms that achieve the higher rate of C - zO. Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They operate in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial time. Furthermore, only the source and destination need to be modified; nonmalicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks.

Item Type:Article
Related URLs:
URLURL TypeDescription
Langberg, Michael0000-0002-7470-0718
Additional Information:© Copyright 2008 IEEE. Reprinted with permission. Manuscript received November 23, 2006; revised February 21, 2008. [Date Published in Issue: 2008-05-23] This material is based upon work supported by the Air Force Office of Scientific Research under Grant FA9550-06-1-0155, the National Science Foundation under Grants CCR-0325496 and CCF-0325324, the Chinese University of Hong Kong under Direct Grant 2050394, and Caltech’s Lee Center for Advanced Networking. The material in this paper was presented at the IEEE INFOCOM, Anchorage, AK, May 2007. Communicated by U. Maurer, Guest Editor for Special Issue on Information Theoretic Security.
Funding AgencyGrant Number
Air Force Office of Scientific ResearchFA9550-06-1-0155
National Science FoundationCCR-0325496
National Science FoundationCCF-0325324
Chinese University of Hong Kong2050394
Lee Center for Advanced Networking, CaltechUNSPECIFIED
Subject Keywords:Byzantine adversaries, distributed network error-correcting codes, eavesdroppers, information-theoretically optimal, list decoding, polynomial-time algorithms
Issue or Number:6
Record Number:CaltechAUTHORS:JAGieeetit08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11447
Deposited By: Archive Administrator
Deposited On:15 Aug 2008 20:31
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page