Rational behavior in peer-to-peer profile obfuscation for anonymous keyword search: The multi-hop scenario

Web search engines (WSEs) have become an essential tool for searching the huge amount of information stored in the World Wide Web. WSEs try to build query profiles of their users, in order to increase the accuracy of the results provided to users and also to fine-tune advertising. Profiling the query interests of users clearly encroaches on their privacy. There are several anti-profiling approaches in web search, among which those relying on peer-to-peer profile obfuscation stand out. In this paper, we analyze the multi-hop peer-to-peer profile obfuscation game, in which a peer forwards her query to a second peer, who may submit it on behalf of the first peer or just forward it to a third peer, and so on. We describe several privacy utility functions for peers (query-level entropy, category-level entropy, hierarchical variance, privacy for location-based queries) and a rational protocol in terms of a generic privacy utility function. It turns out that rational behavior leads peers to help each other.