Re-identification risk: what it is, how we measure it

« We removed the names, so it is anonymous now. » That sentence has been the source of every famous data leak in the last twenty years. Here is what re-identification actually is, three cases that made it famous, and how we measure the risk before we trust a transformation.

What re-identification is

Re-identification is the process of matching anonymized records back to the individuals they describe, reversing the protections that anonymization was supposed to provide. Direct identifiers are removed (name, email, social security number), but the rest of the data, called quasi-identifiers, can be combined to single out a person.

Three famous incidents

2006: the Netflix Prize

Netflix released 100 million « anonymized » movie ratings from 480,000 subscribers. Researchers at UT Austin cross-referenced timestamps and rating patterns with public IMDb profiles. They identified users and exposed their complete viewing histories. A class action followed. Netflix cancelled the sequel competition.

2006: AOL search data

AOL released 20 million « anonymized » search queries from 650,000 users. The New York Times identified user #4417749 as Thelma Arnold, a 62-year-old widow, purely from her search patterns: pets, local landmarks, recurring health questions. The CTO resigned. Multiple employees were fired. The damage to AOL's reputation has never fully recovered.

2013: NYC taxi data

New York City released trip records with « anonymized » medallion numbers using a weak cryptographic hash. Researchers reversed the hash in minutes, enabling tracking of individual drivers and passengers. Celebrity tips became traceable from paparazzi photos. Driver earnings, passenger pickup locations, all exposed.

How we measure the risk

Before we trust any substitution, we run three measurements on the protected version of the file:

• k-anonymity. How many records in the protected file share the same combination of quasi-identifiers? A k of 1 means a row is unique, hence trivially identifiable. We aim for k ≥ 5 for any record that leaves the machine.
• l-diversity. Within a k-group, how many distinct sensitive values exist? If everyone in the group has the same diagnosis, knowing the group reveals the diagnosis.
• Linkage risk. Could a determined reader cross-reference the protected file with a public dataset to recover the original identity? We test this systematically.

Why a stable marker scheme matters

When we replace a real value with a marker, the marker has to be:

• Stable across the file. If « ACME Corp » becomes PARTY_A in paragraph 1, it must stay PARTY_A in paragraph 47. Otherwise the AI cannot reason.
• Stable across time. If the same client appears in a file you process six months later, the marker should match. Otherwise threading the work back together becomes painful.
• Not reversible from the marker alone. The mapping « marker ↔ real value » must live somewhere outside what is sent to the AI. With Hexagone AI, that somewhere is your local disk.

What this means in practice

Real anonymization is not about deleting fields. It is about making sure that no combination of remaining fields, alone or cross-referenced, can lead back to a person. That is harder than it sounds, and easier when you have a tool that does the measurement for you.