Byzantine Modification Detection in Multicast Networks With Random Network Coding
Authors:
- Ben LeongBLBen Leong
- Ralf KoetterRKRalf Koetter
- Muriel MedardMMMuriel Medard
- Michelle EffrosMEMichelle Effros
- David R. KargerDKDavid R. Karger
- 23 May 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 54 (6) , 2798-2803
Abstract
An information-theoretic approach for detecting Byzantine or adversarial modifications in networks employing random linear network coding is described. Each exogenous source packet is augmented with a flexible number of hash symbols that are obtained as a polynomial function of the data symbols. This approach depends only on the adversary not knowing the random coding coefficients of all other packets received by the sink nodes when designing its adversarial packets. We show how the detection probability varies with the overhead (ratio of hash to data symbols), coding field size, and the amount of information unknown to the adversary about the random code.Keywords
This publication has 19 references indexed in Scilit:
- On coding for reliable communication over packet networksPhysical Communication, 2008
- Network Error Correction, II: Lower BoundsCommunications in Information and Systems, 2006
- Network Error Correction, I: Basic Concepts and Upper BoundsCommunications in Information and Systems, 2006
- Unconditionally private and reliable communication in an untrusted network2005
- Analysis of network error correction based on network codingIEE Proceedings - Communications, 2005
- Byzantine modification detection in multicast networks using randomized network coding2004
- An algebraic approach to network codingIEEE/ACM Transactions on Networking, 2003
- Practical byzantine fault tolerance and proactive recoveryACM Transactions on Computer Systems, 2002
- Network information flowIEEE Transactions on Information Theory, 2000
- Perfectly secure message transmissionJournal of the ACM, 1993