When the signal is in the noise: exploiting Diffix's sticky noise
File(s)
Supporting information
Accepted version
Author(s)
Gadotti, Andrea
Houssiau, Florimond
Rocher, Luc
Livshits, Benjamin
de Montjoye, Yves-Alexandre
Type
Conference Paper
Abstract
Anonymized data is highly valuable to both businesses and researchers. A large body of research has however shown the strong limits of the de-identification release-and-forget model, where data is anonymized and shared. This has led to the development of privacy-preserving query-based systems. Based on the idea of “sticky noise”, Diffix has been recently pro-posed as a novel query-based mechanism satisfying alone the EU Article 29 Working Party’s definition of anonymization. According to its authors, Diffix adds less noise to answers than solutions based on differential privacy while allowing for an unlimited number of queries.This paper presents a new class of noise-exploitation attacks, exploiting the noise added by the system to infer privateinformation about individuals in the dataset. Our first differential attack uses samples extracted from Diffix in a likelihood ratio test to discriminate between two probability distributions.We show that using this attack against a synthetic best-case dataset allows us to infer private information with 89.4% accuracy using only 5 attributes. Our second cloning attack uses dummy conditions that conditionally strongly affect the output of the query depending on the value of the private attribute. Using this attack on four real-world datasets, we show that we can infer private attributes of at least 93% of the users in the dataset with accuracy between 93.3% and 97.1%, issuing a median of 304 queries per user. We show how to optimize this attack, targeting 55.4% of the users and achieving 91.7% accuracy, using a maximum of only 32 queries per user. Our attacks demonstrate that adding data-dependent noise, as done by Diffix, is not sufficient to prevent inference of private attributes. We furthermore argue that Diffix alone fails to satisfy Art. 29 WP’s definition of anonymization. We conclude by discussing how non-provable privacy-preserving systems can be combined with fundamental security principles such as defense-in-depth and auditability to build practically useful anonymization systems without relying on differential privacy.
Date Issued
2019-08-14
Date Acceptance
2019-03-14
Citation
28th USENIX Security Symposium, 2019, pp.1081-1098
ISBN
9781939133069
Publisher
USENIX
Start Page
1081
End Page
1098
Journal / Book Title
28th USENIX Security Symposium
Copyright Statement
This paper is embargoed until publication.
Identifier
https://www.usenix.org/conference/usenixsecurity19/technical-sessions
Source
28th USENIX Security Symposium (USENIX Security '19)
Subjects
Science & Technology
Technology
Computer Science, Information Systems
Computer Science
SENSITIVITY
Publication Status
Published
Start Date
2019-08-14
Finish Date
2019-08-16
Coverage Spatial
Santa Clara, CA, USA
Date Publish Online
2019-08-14