On 4 August 2006 AOL published about 20 million search queries from more than 650,000 users over three months, with usernames replaced by random numbers. Within days the New York Times had identified user 4417749 as a named individual from the content of her searches alone. What failed, which design assumption made it possible, and what would have prevented it?

The trigger

A research release, intended to be helpful, in which the only privacy control applied was the substitution of a persistent random identifier for each user's account name. The data was otherwise complete: every query, in order, with timestamps.

Why it propagated

The identifiers were never what identified people. A person's search history contains their town, their surname, their employer, their medical conditions and the names of people they know — and the persistent identifier stitched all of it into one profile. Journalists identified user 4417749 from searches about a specific place and a set of personal circumstances; the case became public and AOL's chief technology officer resigned later that month.

The design assumption that failed is the one still made routinely: that removing direct identifiers makes a dataset anonymous. It does not, because identification comes from the combination of attributes — quasi-identifiers — and free text is the worst case, since it contains an unbounded and unpredictable set of them.

The second failure is the persistent pseudonym itself. Linking every query by one user into a single record is what makes the profile identifiable; the same queries, unlinked, would have been far less dangerous, which is the part most teams get backwards when they add a "privacy-safe user id".

Why detection lagged

There was no detection. A release is irreversible: the file was copied and mirrored within hours, and taking down the original changed nothing. For data publication, the only control that exists is the one applied before release — there is no rollback, no patch, and no incident response that recovers the data.

The structural fix versus the tempting local fix

The tempting fix is stronger pseudonymisation: hash the identifier, salt it, rotate it. It addresses nothing here, because the identifier was not the vector.

The structural fixes, in order of what they cost:

1. Do not release free text. Query content cannot be made safe by transformation; it can only be aggregated or withheld. Release counts of queries per category, not queries.
2. Break linkage. If per-user analysis is not required, do not carry a per-user key at all. If it is, rotate it on a short period so profiles cannot accumulate.
3. Apply a formal guarantee where a release must happen. Differential privacy provides a measurable bound on what any individual's presence can reveal, and it is a bound rather than a judgement — which is the property that matters when the reviewer is a regulator.
4. Assess re-identification risk adversarially before release, by having someone actually try, with the auxiliary datasets a real attacker would have.

The general lesson

Pseudonymised data is personal data, and both the regulatory treatment and the engineering treatment follow from that. It reduces risk — a leaked pseudonymised store is less immediately harmful than a leaked identified one — and it does not remove obligations, permit unrestricted secondary use, or make a public release safe.

The test worth carrying: could someone with ordinary auxiliary information single out one person in this dataset? For anything containing free text, location traces, or a long behavioural history, the honest answer is yes, and the decision that follows is about aggregation or suppression, not about better identifiers.

Common weak answers

• "They should have hashed the user ids." The identifier was not the vector, and a hash of a persistent key is still a persistent key. Nothing about the outcome changes.
• "Nobody would bother re-identifying a search log." Journalists did it within days, with no special tools, on a dataset of 650,000 users. The cost of the attack is the researcher's curiosity.
• "We will remove the risky queries." Deciding which of 20 million free-text strings are identifying is not a task anyone completes; it is the argument for not publishing free text.