Routing for Security in Networks with Adversarial Nodes
The authors consider the problem of secure unicast transmission between two nodes in a directed graph, where an adversary eavesdrops/jams a subset of nodes. This adversarial setting is in contrast to traditional ones where the adversary controls a subset of links. In particular, they study, in the main, the class of routing-only schemes (as opposed to those allowing coding inside the network). Routing-only schemes usually have low implementation complexity, yet a characterization of the rates achievable by such schemes was open prior to this paper. They first propose an LP based solution for secure communication against eavesdropping, and show that it is information-theoretically rate optimal among all routing-only schemes.