Plausibly Deniable Search

Query-based web search is becoming an integral part of many people’s daily activities. Most do not realize that their search history can be used to identify them (and their interests). In July 2006, AOL released an anonymized search query log of some 600K randomly selected users.While valuable as a research tool, the anonymization was insufficient: individuals could be identified from the queries alone [6]. Government requests for such logs serves to increase the concern. We propose a client-centered approach based on plausibly deniable search: actual user queries are replaced with a set of queries that hide the actual query. By using a singular-value decomposition approach (demonstrated on TREC-4), we are able to generate cover queries that have characteristics similar to the actual user query (although on unrelated topics), preventing the actual query from “standing out” from the cover queries.