Theoretical models for web search privacy through query obfuscation

Details

Supervisors

Hendrickx, Julien

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées

Abstract

With the emergence of the Big Data era, privacy has become an increasingly important issue. The constant and ubiquitous logging of personal and professional data raises concerns, as this data is used for commercial, political or juridic purposes, with little to no regards for the users’ intimacy. In particular, Web search – the activity through which users of search engines access information on the Internet from their search queries – has recently come to light as an area where privacy is both primordial and as of now unachievable. Indeed, Web search data is seen as extremely intimate, as it may contain commercial, financial and medical information, yet very few solutions exist to protect its privacy. A promising solution that has been proposed is query obfuscation, where a program on the user’s computer sends many artificial queries in the hope of drowning the user’s queries in noise. This approach is valuable, as it makes the user the sole responsible of her own privacy, and additionally ensures protection against an eavesdropper. However, no obfuscator developed up to now has been proven to address the privacy issues of Web search data in a meaningful way, and existing implementations have been shown to be either unusable or useless in practice. Assessing whether efficient and effective obfuscators can be designed is a crucial question for the future of Web search privacy. In this master thesis, we propose a novel framework for the analysis and design of query obfuscators. Our contributions are fourfold. Firstly, we analyze the literature and discuss the user’s needs to define design principles for obfuscators. Secondly, we define three novel privacy notions that answer these needs. Thirdly, we introduce a new model for practical obfuscators that implements the principles discussed. Fourthly, we build on this model and notions to discuss the feasibility of query obfuscation for Web search. Our conclusion is that query obfuscation is not a suitable solution for Web search privacy, but it is nonetheless a surprisingly valuable tool. Indeed, query obfuscation is a powerful technique that is inadequate to address the daunting task of Web search data, due to the sheer volume of data involved. We argue that the rigorous analysis proposed in this master thesis serves as a strong – and arguably the first – basis for the study of obfuscators as a solution to privacy issues in other domains, such as the privacy of patent search.