Anonymous networking with localized eavesdroppers: A game-theoretic approach

The problem of anonymous wireless networking is considered when an adversary monitors the packet transmission timing of an unknown fraction of the network nodes. For a given level of network performance, as measured by network throughput, the problem of maximizing anonymity is studied from a game-theoretic perspective. Using conditional entropy of routes as a measure of anonymity, this problem is posed as a two player zero-sum game between the network designer and the adversary; the task of the adversary is to choose a subset of nodes to monitor so that anonymity of routes is minimum and the task of the network designer is to choose a subset of nodes (referred to as covert relays to generate independent transmission schedules and evade flow detection so that anonymity is maximized. It is shown that a Nash equilibrium exists for a general category of finite networks. The theory is applied to the numerical example of a switching network to study the relationship between anonymity, fraction of monitored relays and the fraction of covert relays.