  We consider the problem of communication over a network containing a hidden
and malicious adversary that can control a subset of network resources, and
aims to disrupt communications. We focus on omniscient node-based adversaries,
i.e., the adversaries can control a subset of nodes, and know the message,
network code and packets on all links. Characterizing information-theoretically
optimal communication rates as a function of network parameters and bounds on
the adversarially controlled network is in general open, even for unicast
(single source, single destination) problems. In this work we characterize the
information-theoretically optimal randomized capacity of such problems, i.e.,
under the assumption that the source node shares (an asymptotically negligible
amount of) independent common randomness with each network node a priori (for
instance, as part of network design). We propose a novel
computationally-efficient communication scheme whose rate matches a natural
information-theoretically "erasure outer bound" on the optimal rate. Our
schemes require no prior knowledge of network topology, and can be implemented
in a distributed manner as an overlay on top of classical distributed linear
network coding.
