Lowering the cost of anonymization

a PhD thesis

tl;dr

Abstract

The objective of this thesis is to make it easier to understand, use, and deploy strong anonymization practices. We make progress towards this goal in three ways.

First, we make it easier to understand what anonymization means, and lower the cost of entry for new practitioners. After a historical tour of a number of possible definitions, we introduce differential privacy, a central concept studied throughout this thesis. We then systematize and organize the existing literature on variants and extensions of differential privacy: we categorize them in seven dimensions, compare them with each other, and list some of their main properties.

Second, we consider a natural class of weaker variants of differential privacy: definitions that assume that the attacker only has partial knowledge over the original data. We raise some fundamental issues with existing definitions, and we establish strong theoretical foundations to solve these issues and clearly delineate between distinct attack models. We use these foundations to improve existing results on the privacy of common aggregations and draw links between our notions and older syntactic definitions of privacy. Then, we provide strong negative results for cardinality estimators, a class of algorithms that cannot be made private even under very weak assumptions.

Third, we focus on practical applications. We present novel algorithms to detect reidentifiability and joinability risks of large datasets, and we describe the design of a differentially private query engine designed to be usable to non-experts. We propose multiple possible improvements to this query engine, and discuss a number of trade-offs between privacy, utility, usability, and extensibility; we then discuss operational challenges arising when rolling out anonymization at scale, from choosing parameters to providing appropriate education and guidance to engineers working on anonymization pipelines.

Résumé

Le but de cette thèse est de simplifier
L’art d’empêcher que l’on puisse identifier
Un seul individu dans un jeu de données
Même si l’on se sert de voies insoupçonnées.

Définir ce problème est loin d’être évident :
Bon nombre d’érudits s’y sont cassé la dent.
D’abord, on retranscrit le parcours historique
Ayant déterminé la notion unique
Utilisée ici pour définition
Grâce à ses attributs et son intuition.
Nous classons et trions toutes ses variantes
En sept dimensions dociles et brillantes.

On s’attarde plus tard sur un point compliqué :
Comment modéliser l’attaquant étriqué
Ayant a priori bien trop d’incertitude
Pour accomplir son rôle avec exactitude.
Grâce à des fondements que l’on rend adéquats
Nous améliorons d’anciens résultats.
Certains sont positifs : on peut enfin comprendre
Comment voter pour l’une et pour autant prétendre
Avoir voté pour l’autre, en restant clandestins.
Certains sont négatifs : en comptant les distincts
Alors on doit choisir ; soit on passe à l’échelle,
Soit on protège bien chaque info personnelle.

Les principes, c’est bien, les actions, c’est mieux.
C’est pourquoi l’on poursuit un but audacieux :
Rendre l’anonymat accessible en pratique.
Un accord adéquat de sens mathématique
Et d’innovation technique est précieux
Pour accomplir un jour ce rêve ambitieux.
Et l’outil n’est pas tout : c’est aussi nécessaire
D’aider tout un chacun pour être l’émissaire
Du maintien et respect de principes moraux.
Chaque choix peut changer un quidam en héros.

Zusammenfassung

Das Ziel dieser Doktorarbeit liegt in der Erleichterung des Verständnisses und der Verwendung von starken Anonymisierungstechniken, sowie der Bereitstellung von Prozeduren zur Anonymisierung. Hierbei erzielen wir auf drei verschiedene Arten Fortschritte.

Zuerst beleuchten wir die Grundlagen von Anonymisierung, um Neulingen einen einfacheren Zugang zum Fachgebiet zu ermöglichen. Nach einem geschichtlichen Überblick über ausgewählte andere Datenschutzdefinitionen wird Differential Privacy eingeführt, ein zentrales Konzept dieser Doktorarbeit. Der anschließende Schwerpunkt liegt auf der Systematisierung und Organisierung der wissenschaftlichen Literatur zu Varianten und Erweiterungen von Differential Privacy. Wir kategorisieren die vorhandenen Definitionsvarianten in sieben Dimensionen, vergleichen sie miteinander und führen einige ihrer Haupteigenschaften auf.

Als Zweites überprüfen wir natürliche Verallgemeinerungen der Differential Privacy: Definitionen, die einen Angreifer mit nur teilweiser Kenntnis der Originaldaten annehmen. Wir zeigen grundsätzliche Probleme bei diesen Definitionen auf und etablieren starke theoretische Grundlagen zur Lösung diese Schwierigkeiten. Hierbei ist unsere deutliche Abgrenzung zwischen zwei unterschiedlichen Angreifermodellen hervorzuheben. Wir nutzen diese Grundlagen, um bestehende Ergebnisse über verbreiteter Aggregationen zu verbessern, und um Verbindungen zwischen unseren Anonymisierungsegriffen und älteren syntaktischen Definitionen zu ziehen. Darauf aufbauend legen wir starke negative Ergebnisse für Kardinalitätsschätzer vor: Diese Klasse von Algorithmen wird selbst unter schwächsten Annahmen nicht dem Privatsphärenschutz gerecht.

Als Drittes betrachten wir praktische Anwendungen. Wir präsentieren neuartige Algorithmen zur Ermittlung von Informationszusammenführungs- und Identifizierungsrisiken in großen Datenmengen. Außerdem beschreiben wir den Entwurf eines Systems, welches Laien erlaubt, statistische Abfragen unter Wahrung der Differential Privacy auszuführen. Wir schlagen mehrere mögliche Verbesserungen für dieses System vor und besprechen eine Reihe von Kompromissen zwischen Datenschutz, Genauigkeit, Benutzerfreundlichkeit und Erweiterbarkeit; wir betrachten auch die Herausforderungen bei anonymisierten Datenveröffentlichungen von der Auswahl adäquater Datenschutzparameter bis zur angemessenen Schulung und Anleitung von EntwicklerInnen, die an Anonymisierungspipelines arbeiten.

All opinions here are my own, not my employers.
I'm always glad to get feedback! If you'd like to contact me, please do so via e-mail (se.niatnofsed@neimad) or Twitter (@TedOnPrivacy).