Privacy protection of user profiles in online search via semantic randomization

Querying a search engine is one of the most frequent activities performed by Internet users. As queries are submitted, the server collects and aggregates them to build detailed user profiles. While user profiles are used to offer personalized search services, they may also be employed in behavioral targeting or, even worse, be transferred to third parties. Proactive protection of users' privacy in front of search engines has been tackled by submitting fake queries that aim at distorting the users' real profile. However, most approaches submit either random queries (which do not allow controlling the profile distortion) or queries constructed by following deterministic algorithms (which may be detected by aware search engines). In this paper, we propose a semantically grounded method to generate fake queries that (i) is driven by the privacy requirements of the user, (ii) submits the least number of fake queries needed to fulfill the requirements and (iii) creates queries in a non-deterministic way. Unlike related works, we accurately analyze and exploit the semantics underlying to user queries and their influence in the resulting profile. As a result, our approach offers more control—because users can tailor how their profile should be protected—and greater efficiency—because the desired protection is achieved with fewer fake queries. The experimental results on real query logs illustrate the benefits of our approach.