A Caltech Library Service

Network Codes Resilient to Jamming and Eavesdropping

Yao, Hongyi and Silva, Danilo and Jaggi, Sidharth and Langberg, Michael (2014) Network Codes Resilient to Jamming and Eavesdropping. IEEE/ACM Transactions on Networking, 22 (6). pp. 1978-1987. ISSN 1063-6692.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the problem of communicating information over a network secretly and reliably in the presence of a hidden adversary who can eavesdrop and inject malicious errors. We provide polynomial-time distributed network codes that are information-theoretically rate-optimal for this scenario, improving on the rates achievable in prior work by Ngai et al. Our main contribution shows that as long as the sum of the number of links the adversary can jam (denoted by Z_O) and the number of links he can eavesdrop on (denoted by Z_I) is less than the network capacity (denoted by C) (i.e., Z(O) + Z_I < C), our codes can communicate (with vanishingly small error probability) a single bit correctly and without leaking any information to the adversary. We then use this scheme as a module to design codes that allow communication at the source rate of C - Z_O when there are no security requirements, and codes that allow communication at the source rate of C - Z_O - Z_I while keeping the communicated message provably secret from the adversary. Interior nodes are oblivious to the presence of adversaries and perform random linear network coding; only the source and destination need to be tweaked. We also prove that the rate-region obtained is information-theoretically optimal. In proving our results, we correct an error in prior work by a subset of the authors in this paper.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Langberg, Michael0000-0002-7470-0718
Additional Information:© 2014 IEEE. Manuscript received February 27, 2012; revised November 12, 2012 and August 26, 2013; accepted October 28, 2013. The work of D. Silva was supported in part by the Brazilian National Council for Scientific and Technological Development (CNPq) under Grant 482131/2010-1. The work of S. Jaggi was supported in part by the University Grants Committee of the Hong Kong Special Administrative Region, China, under Project No. AoE/E-02/08, the Microsoft-CUHK Joint Laboratory for Human-centric Computing and Interface Technologies under a grant, and an SHIAE grant. The work of M. Langberg was supported in part by ISF Grant 480/08 while the author was at The Open University of Israel.
Funding AgencyGrant Number
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)482131/2010-1
Hong Kong Special Administrative Region University Grants CommitteeAoE/E-02/08
Microsoft-CUHK Joint Laboratory for Human-centric Computing and Interface TechnologiesUNSPECIFIED
Israel Science Foundation (ISF)480/08
Subject Keywords:Achievable rates; adversary; error control; network coding; secrecy
Issue or Number:6
Record Number:CaltechAUTHORS:20150123-100303449
Persistent URL:
Official Citation:Hongyi Yao; Silva, D.; Jaggi, S.; Langberg, M., "Network Codes Resilient to Jamming and Eavesdropping," Networking, IEEE/ACM Transactions on , vol.22, no.6, pp.1978,1987, Dec. 2014 doi: 10.1109/TNET.2013.2294254
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54016
Deposited By: Ruth Sustaita
Deposited On:23 Jan 2015 19:18
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page