How do you prevent re-identification from anonymized data?

What you need to know

Famous re-identification cases

• Massachusetts health records (1990s): Sweeney matched "anonymised" hospital data to a voter list and identified the state governor's records.
• Netflix Prize (2006–2008): researchers matched anonymised movie ratings to public IMDb reviews and identified users.

Techniques

• Generalisation: age 34 becomes "30–39"; PIN 411038 becomes "411xxx".
• Suppression: drop records or cells that remain unique after generalisation.
• k-anonymity: every combination of quasi-identifiers appears at least k times.
• l-diversity: within each group, the sensitive value (diagnosis) has at least l different values. Without it, a group of five people who all have cancer reveals everyone's diagnosis.
• t-closeness: the distribution of the sensitive value in each group is close to the overall distribution.
• Differential privacy for statistics and models: the only method with a guarantee that holds against an attacker with extra data.

1from collections import Counter23def k_anonymity(rows, quasi):4    groups = Counter(tuple(r[q] for q in quasi) for r in rows)5    return min(groups.values())67rows = [8    {"age": 34, "pin": "411038", "gender": "F", "dx": "diabetes"},9    {"age": 34, "pin": "411038", "gender": "M", "dx": "asthma"},10    {"age": 35, "pin": "411038", "gender": "M", "dx": "flu"},11    {"age": 61, "pin": "411001", "gender": "F", "dx": "cancer"},12]13print(k_anonymity(rows, ["age", "pin", "gender"]))        # 1: every row unique1415def generalise(r):16    return {**r, "age": f"{r['age'] // 10 * 10}s", "pin": r["pin"][:3] + "xxx"}1718print(k_anonymity([generalise(r) for r in rows], ["age", "pin"]))  # still 1

Generalising age and PIN groups the three people in their 30s, but the one person in their 60s is still alone, so k stays 1. That record must be suppressed or generalised further. On real data you run this check before every release.

Free text is harder

Clinical notes and support tickets hide identity in detail: "the only woman cricketer from our village", a rare condition, a date and a hospital ward. Run NER-based redaction, then have a person review a sample, because dates, rare conditions and place names survive automated scrubbing.

A real-life example

A health-tech company wants to share 50,000 symptom-checker sessions with a university for research. The first export removes names and phone numbers but keeps age, PIN code, gender and the date of the session. A test linkage against a public list of local clinic appointments re-identifies 1,200 users.

The second export uses age bands, three-digit PIN prefixes, month instead of date, suppresses any group smaller than 10 (k = 10), and runs an l-diversity check so no group has a single diagnosis. The linkage test now matches none. For published statistics, the team releases counts with DP noise instead of exact values.

Follow-up questions to expect

• "Is hashing an ID anonymisation?" — No. A hashed ID is still a stable identifier that links records; that is pseudonymisation.
• "Why not always use DP?" — DP is excellent for statistics and models but hard for releasing row-level data that researchers want to explore; noise at the row level often destroys usefulness.
• "Can embeddings be re-identified?" — Yes. Research shows text can be partially reconstructed from embeddings, so treat an embedding of personal data as personal data.