Secure Network Coding: Bounds and Algorithms for Secret and Reliable Communications

This chapter addresses the task of multicast communication using network coding in the presence of passive eavesdroppers and active jammers. Network coding allows network routers to mix the information content in incoming packets before forwarding them. This mixing has been theoretically proven to be very beneficial in improving both throughput and robustness. Since network coding allows routers to mix packets' content, a single corrupted packet can end up corrupting all the information reaching a destination. Unless this problem is solved, network coding may perform much worse than pure forwarding in the presence of such malicious adversaries. It is shown that high-rate private and reliable communication via schemes, that are both computationally efficient and distributed, is possible in the settings under study. This chapter summarizes almost a decade of study in the very dynamic and intriguing field of private and reliable network communication. The algorithmic techniques presented cover several paradigms and include tools from the study of combinatorics, linear algebra, cryptography, and coding theory.