Providing incentives for cooperation in anonymity systems

In an environment where privacy is an increasing concern to users that communicate through a public network, anonymity systems can play a fundamental role in helping safeguard users' identities. The peer-to-peer (P2P) architecture has emerged as a promising paradigm for designing large-scale anonymity systems capable of providing interactive anonymous communication with little infrastructure. In P2P anonymity systems, users that care about privacy collectively provide anonymous communication to one another, by participating in the system and relaying messages before the intended destination is reached. Although such a design certainly has many advantages, there are reasons to doubt its full potential. In particular, the success of P2P systems is highly dependent on the cooperation of the peers using the system. In anonymity systems, peer availability is a fundamentally important aspect of cooperation. If peers fail to be available in the system beyond the time required to satisfy their immediate needs, the service provided by P2P anonymity systems can be jeopardized. In this thesis, we investigate the threat that low peer availability poses to P2P anonymity systems. We model and evaluate an attack on a P2P anonymity system to show that the effort required by the attacker to reveal the identity of a peer is proportional to the average number of peers in the system. We then focus on designing and evaluating explicit incentive mechanisms that can be coupled with existing P2P anonymity systems to promote high peer availability. The key idea in our approach is to attach a financial cost to peers that fail to participate and provide service to others. Under the challenging design constraints imposed by anonymity systems, we propose a payment-based incentive mechanism where peers exchange money in return for relaying services. We also develop a reputation mechanism to ensure that peers also comply with the system protocol. Using a game-theoretic framework, we model and evaluate the effectiveness of the payment mechanism on promoting peer availability. This analysis provides several insights in understanding payment-based incentives. Finally, we investigate the close relationship between P2P systems and the concept of public goods in economics. Classical models from the economics literature are then used to illustrate the impact that selfish peers can have on system capacity.