TL;DR
This paper introduces a novel generative copula-based model that can accurately estimate the likelihood of an individual being re-identified, even in incomplete datasets. Their findings demonstrate that even heavily sampled anonymized datasets are insufficient for modern privacy standards, as 99.98% of Americans could be re-identified using just 15 demographic attributes.
What Problem Does This Paper Address?
The increasing availability and use of rich personal data for research and innovation come with significant privacy concerns. A common practice to mitigate these concerns is "de-identification," where datasets are anonymized before sharing. However, numerous studies have shown that de-identified datasets can still be re-identified, often using seemingly innocuous demographic information. A key argument from some researchers and companies is that datasets are inherently incomplete, and this incompleteness provides "plausible deniability," making re-identification unlikely or unreliable. This paper directly challenges this notion by proposing a method to accurately quantify the risk of re-identification even in highly incomplete datasets, questioning the effectiveness of current de-identification practices and the "release-and-forget" model.
Methods
The core of the paper is a generative graphical model based on Gaussian copulas. Here's a breakdown:
- Copulas: These are statistical tools used to model the dependence structure between random variables, allowing researchers to specify marginal distributions independently from the dependency structure. This is crucial for handling complex, multi-attribute datasets.
- Generative Model: The model learns the underlying probability distribution of the data, enabling it to generate synthetic data or estimate probabilities for unseen individuals.
- Estimating Uniqueness: The model quantifies the probability that a specific individual's record is unique within a given population. This "population uniqueness" is a key indicator of re-identification risk.
- Estimating Correctness: Building on uniqueness, the model estimates the likelihood that a matched record actually corresponds to the correct individual, even if the dataset is incomplete.
- Inference: The authors employ a two-step approximate inference method for estimating the copula covariance matrix, making the approach computationally feasible for large datasets. They also use a randomized quasi-Monte Carlo method for estimating multivariate normal rectangle probabilities.
What's novel is the application of this generative copula-based approach to accurately estimate re-identification risk in incomplete datasets, directly addressing the "plausible deniability" argument.
Datasets
The authors used five corpora for training and evaluation:
- USA Corpus: Extracted from the 1-Percent Public Use Microdata Sample (PUMS) files.
- MERNIS Corpus: A complete population database from Turkey.
- ADULT Corpus: Extracted from the Adult Income dataset.
- MIDUS Corpus: Extracted from the Midlife in the United States survey.
- HDV Corpus: Extracted from the Histoire de vie survey.
They created 210 different "populations" by selecting subsets of attributes from these corpora, varying the number of attributes (2-47) and records (7108-9M individuals). This diverse set of populations allowed them to test their model's robustness across different data characteristics and sampling fractions.
Key Insights and Ideas
- Incompleteness is Not a Shield: The most significant insight is that dataset incompleteness does not inherently provide plausible deniability. The model can accurately predict re-identification risk even when only a small fraction of the population is represented.
- Demographic Attributes are Powerful: Even a modest number of common demographic attributes (like date of birth, ZIP code, gender) can render a very high percentage of individuals unique in a population. The paper highlights that 15 demographic attributes could uniquely identify 99.98% of Americans.
- Beyond Simple Uniqueness: The model goes beyond just estimating if a record is unique in the dataset. It estimates the correctness of a re-identification, accounting for the probability of false positives and the overall population distribution.
- Challenging the "Release-and-Forget" Model: The findings strongly suggest that the current paradigm of de-identifying data and then releasing it without further consideration is insufficient to meet modern privacy standards like GDPR.
Key Results
- High Accuracy in Uniqueness Estimation: The model achieved AUC scores for predicting individual uniqueness ranging from 0.84 to 0.97 across 210 populations.
- Low False Discovery Rate: For re-identifications predicted with high confidence (ξ > 0.95), the false discovery rate was only 5.26%.
- Robustness to Sampling: The model performed well even when trained on very small samples (e.g., 1% of the USA population), with mean absolute errors (MAE) for population uniqueness typically below 0.05.
- 99.98% Re-identification Risk for Americans: Using 15 demographic attributes, the model predicts that this percentage of Americans would be uniquely identifiable.
- Superior to Theoretical Baselines: The model's predictions were, on average, 39% better than the best theoretically achievable prediction using only population uniqueness.
Limitations and Future Work
- Assumption of Uniform Sampling: The model assumes that the disclosed dataset is either uniformly sampled from the population or has been post-stratified to match the overall population. Biases in the data could affect its usefulness and the model's performance. The authors suggest methods to overcome sampling bias, such as training on a non-uniform sample or using external data.
- Computational Complexity: While the authors employ efficient methods, inferring marginals and association structures can still be computationally intensive, especially for very high-dimensional datasets.
- Future Work: The authors emphasize the need for new legal and regulatory frameworks that move beyond the "de-identification release-and-forget" model. They suggest exploring provable privacy-enhancing systems and security measures that allow data usage while preserving privacy. The paper also opens avenues for further research into more advanced statistical disclosure control methods.
Summary updated