Privacy foundations, re-identification and anonymization

Machine learning runs on data, and much of that data is about people: their health, purchases, movements, messages and faces. Privacy is the second pillar of this course. This lesson introduces what privacy means for data systems, why simply removing names does not make data anonymous, the classical anonymization models such as k-anonymity and their weaknesses, and the principles that guide privacy-respecting system design. It sets up the mathematical approach of differential privacy in Lesson 8.

What privacy protects

Privacy is not only about secrecy. Helen Nissenbaum's idea of contextual integrity holds that information flows carry norms tied to their context: medical details shared with a doctor are appropriate, but the same details flowing to an employer or advertiser violate privacy, even if the information is not secret. For AI systems, privacy concerns include:

• Collection: gathering more data than needed, or without meaningful consent.
• Identification: linking data back to specific people.
• Inference: deriving sensitive facts people never disclosed, such as health conditions, sexual orientation or pregnancy, from innocuous data.
• Disclosure: releasing data or model outputs that reveal personal information.
• Secondary use: using data for purposes other than those for which it was collected.
• Surveillance: continuous tracking of behaviour, for example through face recognition or location data.

Identifiers and quasi-identifiers

Direct identifiers, such as names, government identification numbers, email addresses and phone numbers, identify a person on their own. Quasi-identifiers do not identify someone alone but can do so in combination: postal code, date of birth, sex, occupation, or a sequence of locations. Latanya Sweeney showed in the late 1990s that about 87 % of the US population could be uniquely identified by five-digit ZIP code, full date of birth and sex. She demonstrated the risk by finding the medical records of the governor of Massachusetts in a "de-identified" state health data set, by linking it with a public voter list on those three fields.

Later studies reinforced the point. Researchers re-identified Netflix users in a released ratings data set by matching a handful of ratings and dates with public reviews. A study of mobile phone data found that four spatio-temporal points were enough to uniquely identify 95 % of individuals. Anonymous web search logs released by AOL revealed individuals from the content of their queries. High-dimensional data, such as ratings, location traces, genomes and browsing histories, are especially hard to anonymize because almost every record is unique.

A linkage attack in code

The simulation creates a health table with no names, just a postal area, birth year, sex and diagnosis, and an attacker who holds a public list with names and the same three fields for 1,000 of these people.

import numpy as np
# A linkage attack on a "de-identified" health table, then k-anonymity by generalization
rng = np.random.default_rng(7)
n = 5000
zip3 = rng.integers(0, 40, n)                    # 40 postal areas
birth_year = rng.integers(1940, 2005, n)
sex = rng.integers(0, 2, n)
diagnosis = rng.choice(["asthma", "diabetes", "depression", "none"], n, p=[0.1, 0.1, 0.1, 0.7])
quasi = np.column_stack([zip3, birth_year, sex])
_, inverse, counts = np.unique(quasi, axis=0, return_inverse=True, return_counts=True)
k_each = counts[inverse.ravel()]
print(f"records unique on (area, birth year, sex): {np.mean(k_each == 1):.0%}")
# the attacker has a public voter list with names and the same three fields for 1000 of these people
known = rng.choice(n, 1000, replace=False)
reid = np.sum(k_each[known] == 1)
print(f"attacker re-identifies {reid} of 1000 people on the voter list with certainty")
# generalize: 10-year birth bands and 4 regions of 10 areas
gen = np.column_stack([zip3 // 10, birth_year // 10, sex])
_, inv2, counts2 = np.unique(gen, axis=0, return_inverse=True, return_counts=True)
k2 = counts2[inv2.ravel()]
print(f"after generalization: smallest group k = {k2.min()}, median group size = {int(np.median(k2))}")
# homogeneity check: is any group where everyone shares the same diagnosis?
worst = 0.0
for c in range(len(counts2)):
    d = diagnosis[inv2.ravel() == c]
    worst = max(worst, np.mean(d == "depression"))
print(f"highest share of depression in any group: {worst:.0%} (l-diversity looks at this)")

records unique on (area, birth year, sex): 38%
attacker re-identifies 373 of 1000 people on the voter list with certainty
after generalization: smallest group k = 43, median group size = 96
highest share of depression in any group: 21% (l-diversity looks at this)

Even with only 40 postal areas and birth year rather than full date of birth, 38 % of records are unique on the three quasi-identifiers, and the attacker re-identifies 373 of the 1,000 people on the list with certainty, learning their diagnoses. Generalizing the quasi-identifiers to four regions and ten-year birth bands makes every combination shared by at least 43 people, so the data become 43-anonymous. The last line hints at a remaining problem: in one group, 21 % of people have depression, which tells an attacker something about anyone known to be in that group even without pinpointing a record.

k-anonymity and its extensions

A data set is k-anonymous if every record shares its quasi-identifier values with at least \(k-1\) other records, so any person could be any of at least \(k\) records. It is achieved by generalization (replacing values with ranges or broader categories) and suppression (removing outlier records or values). k-anonymity defends against simple linkage but has known weaknesses:

• Homogeneity attack: if all records in a group share the same sensitive value, being in the group reveals it. l-diversity requires each group to contain at least \(l\) well-represented sensitive values.
• Background knowledge attack: knowing that a person is unlikely to have some conditions narrows the possibilities. t-closeness requires the distribution of sensitive values in each group to be close to the overall distribution.
• Composition: releasing two k-anonymous versions of overlapping data can allow an attacker to intersect them and re-identify people.
• Utility loss: in high-dimensional data, achieving k-anonymity requires so much generalization that the data lose most of their value.

These problems motivated a shift from syntactic definitions about the shape of released data to semantic guarantees about what an attacker can learn, which is what differential privacy provides.

Pseudonymization and anonymization in law

Data protection laws distinguish pseudonymized data, where identifiers are replaced with codes but re-identification remains possible with additional information, from anonymized data, from which people can no longer reasonably be identified. Pseudonymized data are still personal data under laws such as the EU General Data Protection Regulation; truly anonymized data generally fall outside it. The threshold is demanding: regulators expect organizations to consider all means reasonably likely to be used for re-identification, including linkage with other data sets, and to reassess as technology changes.

In Canada, PIPEDA and provincial laws such as Quebec's Law 25 govern personal information in the private sector; Law 25 explicitly defines anonymized information as information that irreversibly no longer allows a person to be identified, subject to generally accepted best practices, and treats de-identified (pseudonymized) information as still personal.

Privacy by design

Privacy by design, a framework developed by Ann Cavoukian when she was Ontario's Information and Privacy Commissioner, holds that privacy should be built into systems from the start rather than added later. For machine learning projects, its practical principles include:

• Data minimization: collect and keep only the data needed for a defined purpose, and delete it when no longer required.
• Purpose limitation: use data only for the purposes people were told about.
• Access control and security: restrict who can see raw data, log access, and encrypt data at rest and in transit.
• Aggregation and noise: release statistics or models rather than records, with formal privacy protections where possible.
• Transparency and choice: tell people what is collected and how it is used, and offer meaningful choices.
• Privacy impact assessments: evaluate risks before building, as discussed in Lesson 12.

Privacy risks specific to machine learning

Machine learning adds new privacy risks beyond data releases. Models can memorize training examples and reproduce them, for example a language model repeating a person's phone number or a code model emitting an API key. Attackers can infer whether a person was in a training set (membership inference) or reconstruct training examples from a model (model inversion), as Lesson 10 explains. Models can infer sensitive attributes from innocuous inputs, such as predicting sexual orientation from photos or health conditions from purchases. Inference itself can be a privacy harm even if no data are leaked, which is why some laws treat inferred sensitive data as sensitive personal information.

Inference as a privacy harm

Some of the most serious privacy harms come not from disclosure but from inference. A retailer's model reportedly identified pregnant customers from changes in their purchases and sent them baby product promotions, revealing the pregnancy to family members. Studies have shown that likes on social networks predict sexual orientation, political views and personality traits with surprising accuracy, and that location traces reveal home and work addresses, religious attendance and medical visits. These inferences can be made about people who never shared the sensitive information and never consented to the analysis. Responsible practice treats high-risk inferences as sensitive data: assess whether a model can infer protected characteristics, avoid building features or products that do so without a strong justification and consent, and restrict how inferred attributes are stored and used.

A privacy review checklist for ML projects

A practical privacy review for a machine learning project asks:

• Purpose: what is the data used for, and is each data element necessary?
• Lawful basis and consent: do people know, and did they agree or is there another legal basis?
• Identifiability: which direct and quasi-identifiers are present, and how could the data be linked with other sources?
• Retention: how long are raw data, features and models kept, and how are they deleted?
• Access: who can see raw data, and are access logs reviewed?
• Release: what statistics, models or APIs will be exposed, and what could they reveal?
• Inference: could the model infer sensitive characteristics?
• Rights: how will access, correction and deletion requests be handled, including for trained models?

The answers feed the privacy impact assessment described in Lesson 12 and determine whether formal protections such as differential privacy (Lesson 8) or privacy-enhancing technologies (Lesson 9) are needed.

Aggregates are not automatically safe

It is tempting to think that publishing only aggregate statistics avoids privacy risk. It does not. Differencing attacks subtract two aggregates that differ by one person, for example the average salary of a department before and after a new hire, to reveal an individual value. Reconstruction attacks solve for individual records from many overlapping tables, as the US Census Bureau found when it reconstructed a large share of 2010 census records from its own published tables. Small cells, such as a count of one or two people with a rare condition in a small area, reveal information directly. These attacks are why the next lesson introduces a guarantee that holds for any combination of releases.