"Anonymity in Wireless Networks with Localized Eavesdroppers: A Game-Theoretic Approach" P. Venkitasubramaniam and L. Tong Submitted to 2009 IEEE INFOCOM, Aug. 2008.
The problem of anonymous wireless networking is considered when eavesdroppers monitor an unknown fraction of the transmitting 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. The metric of anonymity considered is the conditional entropy of network routes given the monitored packet transmission times. In order to provide anonymity, a random subset of nodes (referred to as covert relays) are chosen to generate transmission schedules thereby evading flow detection. Depending on the routes and the throughput requirement, the network designer needs to optimize the choice of covert relays such that anonymity is maximized. Whereas, the eavesdropper needs to optimize the choice of nodes to monitor subject to a constraint on maximum number of monitored nodes, such that the anonymity of the network routes is minimized. This problem is posed as a two player zero-sum game, and it is shown that a Nash equilibrium exists for a general category of finite networks. This approach is shown to be applicable to the scenario when the adversary obtains side information by compromising a subset of nodes, and the existence of Nash equilibria is proven. Using numerical examples, the tradeoff between the achievable anonymity and the power of the adversary is demonstrated as a function of the throughput for passive and active adversaries.