Byzantine Modification Detection in Multicast Networks With Random Network Coding

Authors:
  • RKRalf Koetter
    Ralf Koetter
  • MMMuriel Medard
    Muriel Medard
  • MEMichelle Effros
    Michelle Effros
  • DKDavid R. Karger
    David R. Karger

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.

This publication has 19 references indexed in Scilit: