Date Added: Jun 2009
To protect user privacy in the search engine context, most current approaches, such as private information retrieval and privacy preserving data mining, require a server-side deployment, thus users have little control over their data and privacy. In this paper the authors propose a user-side solution within the context of keyword based search. The authors model the search privacy threat as an information inference problem and show how to inject noise into user queries to minimize privacy breaches. The search privacy breach is measured as the mutual information between real user queries and the diluted queries seen by search engines. They give the lower bound for the amount of noise queries required by a perfect privacy protection and provide the optimal protection given the number of noise queries.