Bloom Cookies: Web Search Personalization without User Tracking

We propose BloomCookies that encode a user’s profile in a compact and privacy-preserving way, without preventing online services from using it for personalization purposes. The BloomCookies design is inspired by our analysis of a large set of web search logs that shows drawbacks of two profile obfuscation techniques, namely profile generalization and noise injection, today used by many privacy-preserving personalization systems. We find that profile generalization significantly hurts personalization and fails to protect users from a server linking user sessions over time. Noise injection can address these problems, but only at the cost of a high communication overhead and a noise dictionary generated by a trusted third party. In contrast, BloomCookies leverage Bloom filters as a privacy-preserving data structure to provide a more convenient privacy, personalization, and network efficiency tradeoff: they provide similar (or better) personalization and privacy than noise injection (and profile generalization), but with an order of magnitude lower communication cost and no noise dictionary. We discuss how BloomCookies can be used for personalized web search, present an algorithm to automatically configure the noise in BloomCookiess given a user’s privacy and personalization goals, and evaluate their performance compared to the state-of-the-art.