Re-identification Risk

The most fundamental driver of risk is the inherent uniqueness of a record within a population. High-dimensional, fine-grained data—such as precise GPS coordinates, detailed browsing histories, or rare medical diagnoses—dramatically increases the probability that a record is a population singleton. Granularity refers to the resolution of attributes; a birth date is far more identifying than a birth year. The combination of multiple quasi-identifiers creates a combinatorial explosion of possible identity signatures, making even sparse datasets vulnerable when attributes are sufficiently specific.

Re-identification rarely occurs from the target dataset alone. The risk is a function of the external data an adversary can acquire to cross-reference. Common sources include:

• Public records: Voter registration databases, property tax records, and court filings.
• Commercial data brokers: Aggregated purchasing histories and demographic profiles.
• Social media and web scraping: Self-disclosed information on LinkedIn, Facebook, or personal blogs.
• Previous data breaches: Leaked credential and identity corpora circulating on dark web markets. The Sweeney and Netflix Prize re-identification attacks succeeded precisely because auxiliary datasets (public voter rolls and IMDB reviews, respectively) provided the linkage keys.

Risk assessment must model the adversary's background knowledge and objectives. A casual observer with no computational resources poses a different threat than a nation-state actor with access to massive auxiliary datasets and GPU clusters. Key adversary profiles include:

• Prosecutor adversary: Knows a specific target individual is in the dataset and seeks to isolate their record.
• Journalist adversary: Attempts to identify any high-profile individual without prior knowledge of their presence.
• Marketer adversary: Seeks to re-identify a large fraction of records for commercial targeting. The motive—whether financial gain, political exposure, or academic demonstration—determines the resources an adversary will invest.

The attack surface is defined by the number and type of quasi-identifiers shared between the target dataset and available auxiliary sources. Exact matching on categorical variables like ZIP code, gender, and date of birth remains the most common vector. However, probabilistic linkage using fuzzy matching on names, addresses, or temporal patterns significantly expands the surface. The risk is compounded in longitudinal datasets where repeated observations of the same individual create a temporal fingerprint that is highly unique, even if each snapshot is partially anonymized.

The relationship between the sample size and the underlying population critically shapes risk. A dataset that captures a large fraction of a small, well-defined population (e.g., all patients in a rare disease registry) carries extreme re-identification risk because the denominator for anonymity is small. Conversely, a tiny random sample from a massive population (e.g., 0.01% of all credit card transactions) offers natural protection through crowd-blending. The sampling methodology also matters: non-random sampling can inadvertently concentrate high-risk individuals, creating clusters of vulnerability within an otherwise large dataset.

Attributes with high temporal stability—those that remain constant or change predictably over time—pose greater long-term risk. A static identifier like a genome sequence or a fingerprint hash is permanently identifying. Quasi-identifiers like a residential address have medium stability (years), while dynamic attributes like a heart rate reading have low stability (seconds). However, even dynamic data can become identifying when captured in high-frequency time series; an accelerometer gait pattern is a biometric signature. The persistence of data in backups, logs, and third-party systems means that even a one-time release creates a permanent vulnerability if the attributes are stable.

An adversarial technique that determines whether a specific data point was included in a model's training set. By analyzing the model's confidence scores, loss values, or gradients, an attacker can infer the presence of an individual's record. This is a primary metric for quantifying re-identification risk in machine-learning-as-a-service APIs.

• Exploits overfitting: models often behave differently on training vs. unseen data
• Shadow model technique: attacker trains local models to mimic target behavior
• Defenses include differential privacy and regularization

A privacy attack where an adversary predicts sensitive attributes of an individual by exploiting correlations learned by a model from non-sensitive features. Even if a record is anonymized, the model's outputs can leak information about protected characteristics like income or health status.

• Leverages statistical correlations between public and private features
• Does not require identifying the individual, only inferring the sensitive value
• Mitigated by fairness-aware synthesis and feature suppression

A foundational privacy property ensuring that each released record is indistinguishable from at least k-1 other records with respect to quasi-identifiers like ZIP code, age, and gender. If k=5, an attacker cannot narrow an individual's record to fewer than 5 possibilities.

• Protects against identity disclosure but not attribute disclosure
• Vulnerable to homogeneity attacks when sensitive values are identical within a group
• Often used as a baseline before applying stronger guarantees like differential privacy

An attack that reconstructs representative training data directly from model parameters or prediction APIs. By iteratively querying a model and optimizing inputs to maximize confidence scores, an attacker can generate prototypical examples of each class, potentially exposing sensitive patterns.

• Particularly dangerous for facial recognition and medical imaging models
• Can recover average representations of minority classes
• Defended by gradient leakage prevention and output perturbation

The process of cross-referencing an anonymized dataset with external auxiliary information to re-identify individuals. The classic example is the Netflix Prize dataset, where researchers linked anonymized movie ratings to public IMDb reviews using overlapping timestamps and ratings.

• Exploits quasi-identifiers: combinations of non-unique attributes that become identifying together
• Auxiliary data sources include voter registries, social media, and public records
• Mitigated by data minimization and strict de-identification pipelines

A mathematical framework providing a provable upper bound on information leakage about any single individual. The privacy parameter epsilon (ε) quantifies the guarantee: lower epsilon means stronger privacy. This directly bounds re-identification risk by ensuring an adversary cannot determine whether any individual's data was included.

• Achieved through calibrated noise injection via Laplace or Gaussian mechanisms
• Composable: privacy loss accumulates across multiple queries
• The gold standard for formal privacy protection in synthetic data generation