Adversarial privacy: an attack-defence approach to modern privacy protection

Abstract

Throughout our daily lives, our personal data is collected on an unprecedented scale. The field of computational privacy seeks to quantify and mitigate the risks to our privacy caused by the collection and usage of data. Research in this field studies privacy under three broad paradigms: as a property of the data, of processes running over sensitive data, and of data collection systems. In this thesis, we study five questions related to data privacy spanning all three paradigms, from an adversarial perspective, i.e., assuming the point of view of a motivated attacker. In the first three main chapters, we propose and analyse attacks over data publishing systems, practices, and infrastructures. First, we propose an attack against the commercial query- based system Diffix that can recover private information about records in the database with a small number of queries. Second, we develop a framework to estimate the reach of data collections based on observing the local neighbourhoods of compromised nodes in a network. We show empirically that such collections can observe large fractions of the network from a very small fraction of compromised nodes. Third, we study how re-identification attacks in location datasets scale with population size. We show that the decrease of unicity with population size is provably convex and significantly slower than previously estimated.In the last two main chapters, we study privacy-preserving solutions for the collection and use of data. First, we propose an adversarial framework to evaluate query obfuscation systems, where users attempt to hide their real interests by sending artificial data along with their genuine queries. Second, we study private sketches, representations of datasets that guarantee differential privacy and can be used for data analysis tasks. We propose a novel heuristic method to perform a wide range of tasks from these sketches.