Anonymity, Pseudonymity and Linkability

10.0 What this chapter gives you#

1. You will be able to place any system on a four-rung ladder — identified, pseudonymous, unlinkable, anonymous — and say what would have to change to move it a rung.
2. You will be able to use the words anonymity set, unlinkability and undetectability the way the field’s standard terminology paper uses them, and say which of the three a given design provides.
3. You will be able to explain why a table with every name deleted can still name people, and work the arithmetic that shows it, using the published figures for postcode, sex and date of birth.
4. You will be able to define k-anonymity, l-diversity and t-closeness and give a concrete attack that defeats each one.
5. You will be able to state the definition of differential privacy in one line, explain what epsilon controls, and say what an epsilon of 1, of 4 and of 19.61 have meant in real deployments.
6. You will be able to design a federated login that gives each relying party a different subject identifier for the same person, name the specification sections that define it, and say which collusion it stops and which it does not.
7. You will be able to describe how a website recognizes a returning visitor with no cookie and no login, quote the uniqueness rates from the three large public studies, and explain why a privacy tool can make a browser easier to recognize rather than harder.
8. You will be able to apply data minimization field by field, and say, for any dataset a colleague calls “anonymized”, what to ask before believing the word.

Every chapter of this book so far has been about making a person findable. A name that sticks, a number that never repeats, a document an office will vouch for, a register a bank will act on. This chapter is about the other direction, and it is not an afterthought. It is the half of the subject that tells you when to stop.

Identity has an opposite. Not one opposite, but a graded set of them, and the practical value of the subject lies in knowing which one you are aiming at. A person can be named. A person can be given a code that stands in for their name. A person can be given a fresh code every time, so that yesterday’s code and today’s cannot be joined. A person can be dealt with in a way that leaves no code at all. Those are four different things, they cost different amounts, and they fail in different ways. Most systems that claim the fourth have only achieved the second, and the gap between those two claims is where nearly all real privacy failures live.

The reason this matters to a builder is simple. A system with no vocabulary for its opposite has no way of deciding that it has collected enough. It keeps the extra field because the extra field might be useful later. It keeps the stable identifier because that makes debugging easier. It joins the two tables because the join is one line of code. Each of those decisions is individually defensible and collectively fatal, and the only thing that reliably stops them is a designer who can say what property is being given up and what it was worth.

There is one more reason, and it is uncomfortable. Anonymity is not a property you can inspect in a file, the way you can see whether a file has a column called “name”. It is a property of a file together with an attacker, together with everything else in the world that attacker can reach. Change the outside world and the same file becomes identifying without anybody touching it. This chapter spends a lot of its length on that idea, because it is the one otherwise competent people get wrong, and because the mathematics of the last twenty years is mostly an attempt to escape from it.

The plain version#

Four ways to buy bread#

Picture a market square in a town of about two hundred and fifty thousand people. There is a bakery on one side. You want bread, and there are four quite different ways you can get it.

The first way: you have an account at the bakery. You walk in, the baker says good morning by your name, writes your loaf in the ledger under your name and address, and you settle up at the end of the month. The baker knows what you buy, how often, and where you live. If somebody asks the baker who bought the rye loaf on Tuesday, the baker can answer.

The second way: the bakery gives you a small brass token stamped with the number 4471, with your name written down nowhere. The baker writes “4471, one rye loaf” in the ledger and you pay later against the token. The baker does not know your name, but knows an enormous amount about 4471: that 4471 comes in most Tuesdays, buys rye, sometimes buys a birthday cake in March, and once bought forty rolls the day before the school fair. Every one of those entries is joined to every other by the number on the token.

The third way: every time you come in, you take a fresh token from a bowl by the door and drop it in a slot when you leave. Today you are token 9084, tomorrow token 2213. The baker still writes down what each token bought, but nothing joins today’s line to tomorrow’s. The baker can count loaves. The baker cannot build a picture of a customer.

The fourth way: you pay cash, take the bread, and no line is written at all. There is no record that a transaction happened, only that at the end of the day there is one fewer loaf and some more money in the till.

Those four ways are the whole chapter. Named. Same code every time. New code every time. No code at all. Every real system is one of those four, or is pretending to be one of them and is actually another.

Here is the thing worth pausing on. The difference between the second way and the third way is not about the baker knowing your name. In both cases the baker does not know your name. The difference is whether two separate visits can be tied together. That tying-together is the single most important idea in this chapter, and it has almost nothing to do with names.

The size of the crowd#

Suppose you buy bread the fourth way — cash, no record, nothing written down. Are you anonymous?

It depends entirely on who else was in the shop.

If forty people bought bread that morning and you were one of them, then anyone trying to work out who bought the last rye loaf has forty people to choose from. If you were the only customer between seven and eight in the morning, there is nobody to hide behind. The cash did not protect you. The crowd protected you, and the cash only mattered because the crowd was there.

This gives us the first real tool. When you want to know how anonymous somebody is, do not ask what was written down. Ask: how many other people could this equally well have been? That number is the size of the crowd, and it is what you are actually buying when you buy privacy. A crowd of forty is worth something. A crowd of two is worth almost nothing. A crowd of one is not a crowd.

Now watch how fast the crowd shrinks when you add facts. Our town of two hundred and fifty thousand is the biggest crowd available. Say the baker notes only that the customer was a woman: about a hundred and twenty-five thousand. Note that she lives in one of the town’s sixty postal areas: about two thousand and eighty. Note her year of birth, and if about one and a half per cent of the town shares it, the crowd is about thirty-one. Note the exact day of her birth rather than the year, and thirty-one becomes, on average, less than one. No name was written down anywhere, and she is now, most likely, the only person in the whole town who fits.

Three facts. Not secret facts. Not facts anybody would hesitate to give you. Where you live, whether you are a man or a woman, and the day you were born. That is enough, most of the time, to pick one person out of a quarter of a million.

Why two lists become one list#

The reason those three facts are dangerous is not that they are sensitive. It is that they appear on two lists at once.

Imagine the town keeps a public electoral roll: name, address, sex, date of birth, for everyone entitled to vote. Anyone can buy a copy. Imagine also that the town hospital publishes a research file: it has carefully removed every name and address, and it publishes only the postal area, the sex, the date of birth, and the diagnosis.

Neither list is dangerous on its own. The electoral roll has no medical information. The hospital file has no names. But the two lists share three columns, and those three columns pick out one person. Line them up on postal area, sex and date of birth, and the name from the first list lands next to the diagnosis from the second. Nobody broke in. Nobody decrypted anything. Somebody did the thing a spreadsheet does in one click.

This is the shape of almost every real privacy failure. Not a leak of secrets, but a join between two things that were each fine alone. And the columns that do the joining are usually the boring ones, which is why they survive the review meeting.

Hiding a person in a group of ten#

Once you see the join, the obvious defence appears. Make the columns blurrier until each combination describes a group rather than a person.

Instead of the exact date of birth, publish the ten-year band. Instead of the postal area, publish the postal district, of which the town has five, so about fifty thousand people each. If about one person in nine is aged sixty to sixty-nine, the combination “district three, female, aged sixty to sixty-nine” now describes about two thousand eight hundred people rather than one. Line the two lists up and each row in the hospital file matches thousands of rows in the electoral roll. You cannot pick out a person.

This is a real technique and it works. Decide in advance how big the smallest group is allowed to be — ten, or a hundred, or a thousand — and keep blurring the columns until no combination in your published file describes fewer people than that.

And here is where the plain story starts to crack. Suppose that in the group “district three, female, sixty to sixty-nine” there are four people in the file and all four have the same diagnosis. You cannot tell which of the four your neighbour is. You do not need to. You know her diagnosis anyway, because everybody in her group has it. The group was big enough to hide the person and far too small to hide the fact.

That single observation started a twenty-year argument in computer science, and we will follow it properly in the technical half.

Adding a little bit of lying on purpose#

There is a completely different approach, and it is one of the few genuinely new ideas in this subject. Instead of blurring the columns, add noise to the answers.

Here is the oldest version of it, and it is beautiful. Suppose you want to know what proportion of the town’s forty thousand cyclists have ever ridden without a helmet. Nobody wants to admit it. So you give every cyclist a coin and these instructions: flip the coin where I cannot see it. If it comes up tails, answer truthfully. If it comes up heads, flip again, and say yes if the second flip is heads and no if it is tails.

Now every single person has a complete and honest defence. If they answered yes, they can say the coin made them. You cannot tell, for any individual, whether their yes was a confession or a coin. Their privacy is protected by the fact that a plausible innocent explanation always exists.

But the arithmetic still works in bulk. Half the people answered truthfully. The other half answered at random, and half of those said yes, so a quarter of everybody said yes because of the coin. If ten thousand of the forty thousand said yes purely because of coins, and twenty-six thousand said yes in total, then sixteen thousand yeses came from truthful answers, which were half the population, so the true count is thirty-two thousand out of forty thousand, or eighty per cent.

You learned the answer about the town. You learned nothing you can rely on about any person in it. That trade — precise about the group, noisy about the individual — is the whole of the modern approach, and the rest is working out how much noise, where to put it, and how to keep track of how much you have spent.

One name for the baker, another for the butcher#

Go back to the brass token. The bakery gave you token 4471, and the bakery can build a picture of 4471. Suppose the butcher across the square also issues tokens, and suppose the town issues them centrally so that both shops use the same one. You are 4471 everywhere.

Now the baker and the butcher can have a conversation. The baker says 4471 buys forty rolls before the school fair. The butcher says 4471 buys nothing but fish on Fridays. Neither of them knows your name. But between them they now have a much fuller picture than either had alone, and it took no effort at all, because the number matched.

The fix is obvious once you see it. The town issues a different token for each shop. You are 4471 at the baker and 9930 at the butcher. Each shop can still recognize you as a returning customer, which is the only thing either legitimately needed, and neither can join its records to the other’s, because the numbers do not match.

That is one of the most useful ideas in identity engineering and it costs almost nothing to build. The people who do it call the numbers directed identifiers, because each points in one direction only, at one relationship. Every large federated login system supports it. Most deployments do not switch it on.

Note carefully what it does not fix. The town office, which issued both tokens, knows that 4471 and 9930 are the same person. Somebody always does. The question is only whether that somebody is one accountable party or every shop in the square.

Being recognized without being named#

The last plain idea is the strangest one. You can be recognized without anybody giving you a number at all.

Suppose the bakery has no tokens, no accounts, no ledger. But the baker notices things: you are unusually tall, you have a particular accent, you always wear a green coat, you always ask for the bread sliced, and you arrive on a bicycle with a wicker basket. Any one of those is shared with hundreds of people in the town. All five together are probably shared with nobody.

The baker has not written down an identifier but has constructed one, out of measurements you did not choose to hand over and cannot easily stop giving. And it works: tomorrow, when the tall person in the green coat with the sliced-bread habit walks in, the baker knows.

Every web browser does this to its user, whether or not the user has agreed to anything. The browser tells any website that asks a long list of small, dull facts: the screen size, the exact version numbers of the software, the time zone, the list of installed typefaces, the precise way the graphics hardware draws a curve. Every one of those facts is shared with thousands of people. Their combination usually is not.

There is a cruel twist in it, and it is worth carrying away from the plain half. Making yourself unusual in order to be more private makes you easier to recognize. The customer who wears a disguise into a small bakery is the most memorable person who came in that day.

Where the plain version stops being true#

Anonymity is not in the file#

The market-square story quietly suggests that anonymity is something you can build into a record: write less down and the record becomes anonymous. That is the most expensive misunderstanding in the field.

The honest version: anonymity is a relationship between a record, an attacker, and everything else in the world. The same file is anonymous against one attacker and identifying against another, and it can change from the first to the second while sitting untouched on a disk, because the outside world moved. A file of postal areas and birth dates was reasonably safe in 1985 when nobody could buy an electoral roll on a disc. It became identifying the moment somebody could. Nothing in the file changed.

This has a hard practical consequence. You cannot certify a dataset as anonymous once and be done. Any such certificate is a statement about the state of the world on the day it was written, and it decays.

It also means every anonymization claim silently contains a model of who is attacking and what they already know. The classical techniques require the publisher to name, in advance, the columns an attacker might hold — which is a guess about the future contents of every other database in the world. When somebody says a dataset is anonymized, the question to ask is not “how” but “against whom, knowing what”. If they cannot answer, the word is decoration.

The crowd is not the number of people in the room#

The plain half said: count how many other people it could equally well have been. The word doing the work there is “equally”.

If the crowd of forty in the bakery includes thirty-eight children, one elderly man and you, and the observer is trying to identify the person who bought a bottle of wine, the crowd is not forty. It is two, and if the elderly man is teetotal, it is one. Crowd size is only meaningful when the members are roughly equally likely, and in real populations they never are.

The honest version: the useful measure is not how many candidates there are but how the probability is spread across them. A crowd of ten thousand in which one member carries ninety-five per cent of the probability offers about as much protection as a crowd of one. This is why serious work counts in bits of information rather than in heads.

Removing the name does not remove the person#

The plain half was already sceptical about this, but it is worth being blunt. In a rich dataset, the name is one of the least identifying columns in the file.

The reason is that human behaviour is far more distinctive than human demographics. Where you were at four separate moments, which four films you rated and roughly when, which four shops you used and on which days — any of those picks you out of millions. There is no way to blur them without destroying exactly the thing that made the data worth publishing, because the fine detail is both the value and the risk. They are the same detail.

The honest version: for high-dimensional data — long lists of things a person did — the classical approach of deleting identifiers and blurring columns does not have a version that both protects and preserves utility. This is not a matter of trying harder. It is a structural property of sparse, wide data.

The coin trick understates what it costs#

The randomized-response story is lovely and slightly dishonest, in two places.

First, it makes the noise sound free. It is not free. The estimate of eighty per cent came with an error range, and the range widens as the noise grows and narrows as the number of people grows. With forty thousand cyclists the error is small. With four hundred it swamps the answer. Noise buys privacy with accuracy, always, and the exchange rate is worse for small groups — which are usually the groups people most want to study, and the groups most at risk.

Second, and much more important, it makes the guarantee sound like a one-off. Ask the same population the same question twice with fresh coins and average the two answers, and the noise partially cancels. Ask a hundred times and it cancels almost entirely, and the individual protection is gone. The guarantee is not a property of one answer. It is a property of everything you ever release from that data, added up.

The honest version: the protection is a budget, it is consumed by every query, and unless somebody is keeping the ledger, it is being spent without being counted.

A pairwise number stops the shops, not the office#

Giving the baker 4471 and the butcher 9930 stops the baker and the butcher joining their records on the number. It does not stop them joining on anything else. If both shops record the customer’s phone number for delivery, or both see the same payment card, or both are visited by the same browser with the same fingerprint, the join happens anyway and the clever identifiers were decoration.

The honest version: a directed identifier removes one joining column. It is worth doing, it is cheap, and it is nowhere near sufficient on its own. A design that gives out pairwise identifiers and then also gives out the email address has achieved nothing, and this exact combination is extremely common in production.

The law and the mathematics do not agree#

There is a genuine, unresolved split here and it is fair to state both sides in one place.

European data protection law treats pseudonymized data as still personal data and truly anonymous data as outside the rules entirely. That is a cliff edge: on one side the full weight of the regulation, on the other nothing. Much practical effort goes into arguing that a dataset has crossed the line.

Researchers who study re-identification argue that for rich behavioural data the far side of the cliff is mostly empty, and that the release-and-forget model of publishing a file and hoping is no longer defensible. Statisticians who run national collections reply, in equally good faith, that some demonstration attacks rest on assumptions that do not hold for real published tables, and that over-protecting official statistics has serious costs of its own. Both camps have published their arithmetic and the disagreement is live as of August 2026. The practical answer is to stop treating “anonymous” as a state you reach and start treating it as a risk you manage, with a named threat model and a review date.

The technical version#

The four states, defined precisely#

The ladder from the plain half has exact definitions. Use these.

A subject is identified in a system when the system holds, or can trivially derive, an identifier that refers to that person in the world outside the system: a legal name, a national number, an email address, a phone number. The test is not whether the field is called “name”. The test is whether the value is meaningful to a third party who was not given it by this system.

A subject is pseudonymous when the system holds an identifier that refers to the person consistently but is meaningless outside the system. All of the person’s records inside the system can still be joined to each other. This is by far the most common real state, and it is the one most often mislabelled as anonymous.

Records are unlinkable when the system cannot determine whether two records concern the same subject. Note that this is a property of pairs of records, not of a record. Unlinkability is achieved by using an identifier that is fresh per transaction, or per session, or per relationship, depending on which links you are trying to break.

A subject is anonymous when an observer cannot sufficiently identify the subject within a set of possible subjects. Anonymity is therefore always relative to a set, and a claim of anonymity that does not say what the set is has said nothing.

identified     the name is in the record
   |
   |  replace name with a stable code
   v
pseudonymous   one code, all records
   |
   |  fresh code per relationship or session
   v
unlinkable     records cannot be joined
   |
   |  no record refers to a subject at all
   v
anonymous      nothing points at a person

Two warnings about the ladder. It is not a ranking of quality: unlinkability destroys the ability to give a person their own history back, which is often unacceptable. And the rungs are not exclusive across a whole system: the same person can be identified to the billing component, pseudonymous to analytics and unlinkable in the published extract, which is usually the right design.

Pfitzmann and Hansen: the vocabulary the field actually uses#

The standard reference is a paper by Andreas Pfitzmann and Marit Hansen, “A terminology for talking about privacy by data minimization: Anonymity, Unlinkability, Undetectability, Unobservability, Pseudonymity, and Identity Management”. It went through many revisions; version 0.34, dated 10 August 2010, is the one people cite. It is not a standard in the sense of something you implement against. It is a convention, and it won by being careful. Its definitions, in its own words:

Anonymity. “Anonymity of a subject from an attacker’s perspective means that the attacker cannot sufficiently identify the subject within a set of subjects, the anonymity set.”

Anonymity set. The set of all possible subjects, relative to a particular context and action. The point of naming the set is that anonymity has a size. It is not present or absent.

Unlinkability. “Unlinkability of two or more items of interest (IOIs, e.g., subjects, messages, actions, ...) from an attacker’s perspective means that within the system (comprising these and possibly other items), the attacker cannot sufficiently distinguish whether these IOIs are related or not.”

Undetectability. “Undetectability of an item of interest (IOI) from an attacker’s perspective means that the attacker cannot sufficiently distinguish whether it exists or not.”

Unobservability. Undetectability of the item against all subjects uninvolved in it, plus anonymity of the subjects involved even against each other.

Pseudonymity. The use of pseudonyms as identifiers, where a pseudonym is an identifier of a subject other than one of the subject’s real names.

The word “sufficiently” appears in three of those definitions and is doing deliberate work. These are not absolutes. They are thresholds that the designer has to set.

The relationships between the properties matter more than the definitions, because they tell you what you get for free:

Attacker's question        Property that denies it

Did anything happen?       undetectability
Who was it?                anonymity
Are these two the same?    unlinkability
All of the above?          unobservability

unobservability  implies  undetectability
unobservability  implies  anonymity
sender anonymity implies  relationship anonymity

The practical reading: undetectability is strictly harder than anonymity and almost nobody achieves it. A messaging system that hides who sent a message but reveals that a message was sent has anonymity, not undetectability, and traffic analysis lives in that gap.

Kinds of pseudonym, and how long they live#

Pfitzmann and Hansen classify pseudonyms by the scope over which they stay the same, and this classification is the single most useful thing in the paper for a working engineer, because it is a design menu.

The list is ordered from most linkable to least. A person pseudonym is a national identity number with the name filed off: it links everything to everything. A transaction pseudonym links nothing to anything. Between those two extremes sit almost all the good designs.

The relationship pseudonym is the one you want most often, because it gives a counterparty exactly what a counterparty legitimately needs — a stable handle for one continuing relationship — and gives them nothing they can pool with anyone else. The federation people call it a pairwise identifier or a directed identifier, and we come to its exact form further down.

One operational note. A pseudonym does not need to be random to be opaque, but it must not be derivable by the party holding it. A pseudonym computed as a plain hash of a national identity number is a disaster: anybody with a list of candidate numbers can hash the list and reverse it. It must be a stored random value or a keyed derivation whose key only the issuer holds. The same mistake is made constantly with unsalted hashes of phone numbers, where the whole ten-digit space can be enumerated in seconds.

Quasi-identifiers and the arithmetic of re-identification#

A quasi-identifier is an attribute that does not identify a person on its own but does so in combination. The concept is due to the statistical disclosure literature and was made concrete for computer science by Pierangela Samarati and Latanya Sweeney in the late 1990s.

The founding measurement is Sweeney’s. Using 1990 United States census summary data she reported that 87 per cent of the population — 216 million of 248 million — had a combination of five-digit ZIP code, sex and full date of birth that was likely to be unique. She also reported 53 per cent unique on place, sex and date of birth, where place means the city, town or municipality; and 18 per cent unique on county, sex and date of birth. The 2000 working paper carrying the analysis is “Simple Demographics Often Identify People Uniquely”, Carnegie Mellon University, Data Privacy Working Paper 3, Pittsburgh.

That figure is repeated so often that the correction deserves equal space. In 2006 Philippe Golle of the Palo Alto Research Center redid the calculation on 2000 census data and published “Revisiting the Uniqueness of Simple Demographics in the US Population” at the Workshop on Privacy in the Electronic Society, 30 October 2006:

Golle also applied his method to the 1990 data and got 61 per cent rather than 87. He said plainly that he could not explain the discrepancy, because the earlier methodology was not published in enough detail, and speculated that the 1990 tabulations available by ZIP code carried ages only in five-year bands. Take both numbers seriously: the headline 87 per cent is probably too high, and the claim that matters survives at 63 per cent.

Golle’s second result is more useful and much less quoted. Sex, county and full date of birth leave 14.8 per cent of people unique, but also leave 43.6 per cent of people in a group of five or fewer, rising to 63 per cent for people over sixty. Uniqueness is the wrong threshold. A group of three is not privacy.

The high-water mark of this line of work is Luc Rocher, Julien Hendrickx and Yves-Alexandre de Montjoye, “Estimating the success of re-identifications in incomplete datasets using generative models”, Nature Communications volume 10, article 3069, 23 July 2019. Using a copula-based generative model validated on 210 populations, they concluded that 99.98 per cent of Americans would be correctly re-identified in any dataset using 15 demographic attributes, and that sampling — publishing only a fraction of records, long a standard defence — does not save you.

The four attacks that built the field#

Four published re-identifications shaped every rule now in force. Their dates and figures are worth knowing exactly.

Massachusetts, 1997. The Group Insurance Commission released hospital discharge data for state employees with names and addresses removed, retaining ZIP code, sex and date of birth. Latanya Sweeney matched it against the Cambridge voter roll, which she had purchased, and located the record of Governor William Weld. The account appears in her 1997 paper “Weaving technology and policy together to maintain confidentiality”, Journal of Law, Medicine and Ethics, volume 25, pages 98 to 110. It is the single most influential re-identification ever performed and it directly shaped the de-identification provisions of the United States health privacy rule.

It is also disputed, instructively. Daniel Barth-Jones, in “The ‘Re-Identification’ of Governor William Weld’s Medical Information”, July 2012, argued that Weld was identifiable mainly because he was a public figure whose hospitalization was reported in the press, and that the Cambridge voter roll was an incomplete population register: as the 2015 report NISTIR 8053 records, only about 55 per cent of Cambridge was registered to vote in 1996 to 1997, so no more than 55 per cent of the city could have been re-identified that way at all. Barth-Jones calls this “the myth of the perfect population register”. The lesson is not that the attack was wrong but that attack demonstrations are best cases and should be read as such.

AOL, 2006. On 4 August 2006 AOL Research published a compressed file of about twenty million search queries from over 650,000 users covering three months, with user identities replaced by numbers. It was withdrawn by 7 August, too late. On 9 August The New York Times published “A Face Is Exposed for AOL Searcher No. 4417749” by Michael Barbaro and Tom Zeller Jr, identifying user 4417749 as Thelma Arnold, a 62-year-old widow in Lilburn, Georgia, from the content of her searches alone. AOL’s chief technology officer resigned on 21 August 2006. The identifiers had been replaced correctly. The queries themselves were the identifier.

Netflix, 2006 to 2008. To run its recommendation prize, Netflix released a dataset of 100,480,507 ratings created by 480,189 subscribers between December 1999 and December 2005, with subscriber identities replaced by numbers. Arvind Narayanan and Vitaly Shmatikov published “Robust De-anonymization of Large Sparse Datasets” and presented it at the IEEE Symposium on Security and Privacy in 2008. Their result, in their words: “With 8 movie ratings (of which 2 may be completely wrong) and dates that may have a 14-day error, 99% of records can be uniquely identified in the dataset. For 68%, two ratings and dates (with a 3-day error) are sufficient.” They used the public Internet Movie Database as the source of that background knowledge. This is the canonical demonstration that behavioural data is high-dimensional, sparse and therefore near-uniquely identifying.

Washington State, 2013. Latanya Sweeney obtained the state’s publicly sold hospital discharge data for 2011 and matched it against news stories about accidents and hospitalizations. Of 81 cases drawn from news reports she matched 35, or 43 per cent, to a unique record. The report is “Matching Known Patients to Health Records in Washington State Data”, Harvard University Data Privacy Lab, 2013.

k-anonymity, and what defeats it#

k-anonymity, introduced by Samarati and Sweeney and given its canonical statement in Sweeney’s “k-anonymity: a model for protecting privacy”, International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, volume 10, number 5, 2002, pages 557 to 570, requires that every combination of quasi-identifier values in a released table appears at least k times. Equivalently: project the table onto the quasi-identifiers, and every remaining row must appear at least k times. Each such group is an equivalence class.

You achieve it by generalization (replace a value with a broader one: 1963 becomes 1960 to 1969) and by suppression (remove a row or a cell that cannot be generalized into a big enough group).

Here is a small table, before and after, with a k of 4.

Raw quasi-identifiers          Diagnosis
  M4 3QT, F, 1963-04-11        cardiac
  M4 3QU, F, 1964-11-02        cardiac
  M4 3RA, F, 1961-07-30        cardiac
  M4 3RB, F, 1969-01-19        cardiac

Generalized to k = 4
  M4 3*,  F, 1960-1969         cardiac
  M4 3*,  F, 1960-1969         cardiac
  M4 3*,  F, 1960-1969         cardiac
  M4 3*,  F, 1960-1969         cardiac

Three failures, each with a name.

The first is the homogeneity attack. Look at the table above. Every record in the class has the same diagnosis. An attacker who knows their neighbour is a woman in her sixties in the M4 3 area, and knows she is in the dataset, learns her diagnosis with certainty. k-anonymity protects the identity of the row and says nothing at all about the sensitive value.

The second is the background-knowledge attack. Suppose the class has two values, cardiac and diabetes, so it is not homogeneous. If the attacker independently knows the target does not have diabetes, the protection collapses to nothing. k-anonymity has no way to reason about what else the attacker knows.

The third is the composition failure, and it is the worst because it is invisible in review. Two separately k-anonymous releases of overlapping populations are, together, usually not k-anonymous at all. The intersection of two large groups can be one person. Nothing in the definition of k-anonymity composes.

l-diversity, and what defeats it#

l-diversity was proposed to fix the first two failures, by Ashwin Machanavajjhala, Johannes Gehrke, Daniel Kifer and Muthuramakrishnan Venkitasubramaniam at the 22nd International Conference on Data Engineering in 2006, with the full version as “l-diversity: Privacy beyond k-anonymity”, ACM Transactions on Knowledge Discovery from Data, volume 1, issue 1, March 2007, article 3.

The requirement: each equivalence class must contain at least l “well-represented” values for each sensitive attribute. In the simplest form, at least l distinct values.

Two things defeat it.

The similarity attack. A class contains three distinct diagnoses: “gastric ulcer”, “gastritis” and “stomach cancer”. That is l equals 3 by the letter of the rule. Every one of the three is a stomach disease, so the attacker learns the target has a stomach disease. The values were distinct and semantically identical.

The skewness attack. Suppose one per cent of the population has a particular condition. An equivalence class with fifty records, half of which carry that condition, satisfies l-diversity with l equals 2. But membership in that class has moved an attacker’s belief from one per cent to fifty per cent, a factor of fifty. Diversity counts values. It does not look at how the distribution differs from the population.

t-closeness, and what defeats it#

t-closeness, from Ninghui Li, Tiancheng Li and Suresh Venkatasubramanian, “t-Closeness: Privacy Beyond k-Anonymity and l-Diversity”, presented at the 23rd IEEE International Conference on Data Engineering on 15 April 2007, pages 106 to 115, fixes the skewness problem directly. It requires that the distribution of the sensitive attribute within any equivalence class is within a threshold t of the distribution in the whole table, measured with the earth mover’s distance.

That is the right idea and it has two costs.

The first is utility. Forcing every class to look like the whole table means the classes stop carrying the correlations that made the data useful. If you are studying whether a condition clusters by neighbourhood, t-closeness with a small t deliberately destroys the signal you are looking for. It is not a bug; it is what the definition asks for.

The second is that it still shares the fatal property of the whole family: it depends on the publisher having correctly listed the quasi-identifiers in advance. Netflix had no ZIP codes, no birth dates and no obvious quasi-identifiers, which is exactly why nobody applied these techniques to it, and it was re-identified anyway. When every column is potentially a quasi-identifier, generalizing the quasi-identifiers means generalizing everything, and there is nothing left.

None of the three composes across releases, and none of the three makes any statement about an attacker with auxiliary data outside the declared quasi-identifiers. That is the gap differential privacy was invented to close.

Differential privacy, stated plainly and honestly#

The idea was introduced by Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith in “Calibrating Noise to Sensitivity in Private Data Analysis” at the Theory of Cryptography Conference in March 2006, and named and framed by Cynthia Dwork in the invited paper “Differential Privacy” at the 33rd International Colloquium on Automata, Languages and Programming, Venice, 10 to 14 July 2006, published in Lecture Notes in Computer Science volume 4052, pages 1 to 12.

Here is the definition in one sentence of English. A randomized process is differentially private if, for any two input datasets that differ by one person, the probability of seeing any particular output is almost the same either way.

And in symbols, where D and D’ differ in one person’s data, M is the process, and S is any set of outputs:

Pr[ M(D) in S ]  <=  exp(epsilon) * Pr[ M(D') in S ]

Read that inequality as a promise made to one person: whatever comes out of this analysis, it would have been almost exactly as likely to come out if you had never been in the dataset at all. That is the whole thing. Notice what it does not mention: what the attacker knows, what other datasets exist, what the columns are called. The guarantee is unconditional in a way that nothing in the previous section is.

Notice also what it does not promise. It does not promise you learn nothing about a person. If a study establishes that smokers get lung cancer, and an insurer knows you smoke, you are harmed by the study whether or not you took part. Differential privacy protects your decision to participate, not the consequences of general knowledge. Dwork has been explicit about this from the start, and people still expect the stronger thing.

Epsilon, honestly. Epsilon is the number in that inequality. It is not itself the ratio: exp(epsilon) is the bound on how much more likely any output becomes because you were in the data. Because epsilon sits inside an exponential, equal steps in epsilon are not equal steps in protection:

Three honest statements about epsilon that vendors leave out. It is a bound on a worst case, not a description of typical behaviour: a mechanism with epsilon 10 usually leaks far less than epsilon 10 permits, which is a reason not to panic and not a reason to relax. It is not comparable across systems unless the neighbouring-dataset definition matches, because “differ by one person” and “differ by one record” are different relations, and a system protecting one event at epsilon 1 gives a person who contributes 500 events a per-person epsilon of as much as 500 in total. And it composes: under basic composition, k analyses at epsilon each yield epsilon times k, and advanced composition does better, roughly the square root of k for a small allowance of failure probability, but never gives something for nothing.

Mechanisms. The workhorse is the Laplace mechanism. Compute the sensitivity of your query — the largest amount the true answer can change when one person is added or removed — then add noise drawn from a Laplace distribution with scale equal to sensitivity divided by epsilon. For counting queries the sensitivity is 1, so the noise scale is 1 over epsilon and the standard deviation is the square root of 2 divided by epsilon.

import numpy as np

def dp_count(true_count, sensitivity, epsilon, rng):
    scale = sensitivity / epsilon
    return true_count + rng.laplace(0.0, scale)

rng = np.random.default_rng(20260817)
print(dp_count(41_872, 1, 1.0, rng))

Local versus central. In the central model a trusted curator holds the raw data and adds noise to the answers. In the local model each person randomizes their own data before it leaves their device, so no raw data is ever collected. Randomized response is the original local mechanism: S. L. Warner introduced it in 1965 in the Journal of the American Statistical Association, decades before anyone had a definition to measure it against. The fair-coin version described in the plain half is exactly (ln 3, 0)-differentially private, as worked through in Dwork and Roth, “The Algorithmic Foundations of Differential Privacy”, Foundations and Trends in Theoretical Computer Science volume 9, numbers 3 and 4, 2014, pages 211 to 407. The value ln 3 is about 1.0986, because a truthful yes is three times as likely as a coin-driven yes.

The local model needs vastly more people for the same accuracy, because every single record carries noise rather than every answer. That is why it suits a company with hundreds of millions of devices and does not suit a hospital with four thousand patients.

What real deployments actually chose#

Established fact, with dates. Google’s RAPPOR, published at the ACM Conference on Computer and Communications Security in 2014 by Ulfar Erlingsson, Vasyl Pihur and Aleksandra Korolova, was the first large local-model deployment, collecting Chrome settings statistics. Apple deployed local differential privacy from iOS 10 in 2016 and described it in “Learning with Privacy at Scale” in 2017: a per-event epsilon of 4 for the emoji keyboard, and, for Safari domain reporting, a sketch of width 32,768 with 1,024 hash functions at epsilon 4 over a dictionary of 250,000 domains. The critical word is per-event. Reports go once a day over an encrypted channel with no device identifier, but the quoted epsilon governs one event, not one person over a year.

The United States Census Bureau made the largest commitment, applying a differentially private disclosure avoidance system to the 2020 census. On 8 June 2021 it announced production settings with a total privacy-loss budget for the redistricting data product of epsilon 19.61, made up of 17.14 for the persons file and 2.47 for the housing unit file, against 12.2 in the April 2021 demonstration data.

Its justification was a reconstruction attack on its own 2010 data. In “A Simulated Reconstruction and Reidentification Attack on the 2010 U.S. Census”, by John Abowd and colleagues, published in the Harvard Data Science Review in 2025, the team reported that from the tabular summaries the Bureau had already released — more than 150 billion aggregate statistics in 180 table sets — they exactly reconstructed the records of 97 million people, every resident in 70 per cent of all census blocks. The Bureau’s earlier public statement was that at least 52 million 2010 respondents could be correctly re-identified this way.

This is contested. Steven Ruggles and co-authors published “The Role of Chance in the Census Bureau Database Reconstruction Experiment” in 2021, arguing that many apparent re-identifications would be expected by chance from demographic base rates, and that the harm from adding noise to small-area statistics, which allocate funds and draw boundaries, is under-counted. As of August 2026 the argument is unsettled. Hold both facts: reconstruction from published tables is mathematically real, and the size of the practical risk is disputed by competent people.

Directed identifiers and pairwise pseudonyms#

Now the engineering. A directed identifier is an identifier for a subject that is specific to one relying party, so that two relying parties holding identifiers for the same person cannot tell that they match. The federation term is pairwise pseudonym.

OpenID Connect Core 1.0, in section 8 “Subject Identifier Types”, defines exactly two types. Quoting the specification, which as of August 2026 stands as OpenID Connect Core 1.0 incorporating errata set 2 dated 15 December 2023: public “provides the same sub (subject) value to all Clients”, and pairwise “provides a different sub value to each Client, so as not to enable Clients to correlate the End-User’s activities without permission”. A provider advertises what it supports in the subject_types_supported element of its discovery document.

Section 8.1, “Pairwise Identifier Algorithm”, sets three requirements on any algorithm: the subject identifier value must not be reversible by any party other than the provider, distinct sector identifiers must produce distinct subject identifiers, and the algorithm must be deterministic. The sector identifier is normally the host component of the registered redirect URI; where a client registers redirect URIs on several hosts it must register a sector_identifier_uri, an HTTPS URL serving a JSON array of its redirect URIs, and the host of that URL becomes the sector. The specification gives three example methods, the first of which is:

sub = SHA-256 ( sector_identifier || local_account_id || salt )

with the salt kept secret by the provider. The other two are an AES-128 encryption of the same concatenation, and simply generating and storing a globally unique identifier per pair.

Two ID tokens for the same human being at two relying parties then look like this:

{ "iss": "https://idp.example.gov",
  "aud": "tax-portal",
  "sub": "e5f1a0c9d8b74a2f9c31",
  "iat": 1786579200 }

{ "iss": "https://idp.example.gov",
  "aud": "library",
  "sub": "7b02c4ee61a9f0d3448a",
  "iat": 1786579260 }

                 +--> tax portal: sub = e5f1...
                 |
  person 4471 ---+--> library:    sub = 7b02...
  at the IdP     |
                 +--> clinic:     sub = 40b8...

  The three services compare notes: no match.
  The identity provider knows all three.

SAML 2.0 got there first. The OASIS Standard “Assertions and Protocols for the OASIS Security Assertion Markup Language (SAML) V2.0”, 15 March 2005, defines name identifier formats in section 8.3. The persistent format is an opaque string shared between one identity provider and one service provider, specific to that pair, and must not exceed 256 characters. The transient format has a lifetime bounded by the processing context in which it is used, which is a transaction pseudonym in Pfitzmann and Hansen’s terms.

Three national systems have implemented the same idea in law rather than in a protocol, and the oldest of them predates the protocols.

Austria derives a sector-specific personal identifier, the bereichsspezifisches Personenkennzeichen or bPK, from a person’s source identifier, the Stammzahl, by a one-way derivation that mixes in a code for the administrative sector. The Stammzahl is held by the source-identifier register authority under the Austrian E-Government Act and is never used directly for identification. The published description shows the derivation using SHA-1, with the source identifier carried as 24 base64 characters and the resulting sector identifier as 28. Agencies in different sectors therefore hold different numbers for the same citizen and cannot join files on them; crossing sectors requires the register authority’s permission.

Germany’s national identity card does it in the chip. The protocol is Restricted Identification, specified in BSI Technical Guideline TR-03110, “Advanced Security Mechanisms for Machine Readable Travel Documents and eIDAS Token”. In the Federal Office for Information Security’s own words, it “may be used to generate a chip-specific pseudonym for a certain terminal sector”.

India’s Unique Identification Authority introduced two related mechanisms in 2018: the Virtual ID, a temporary 16-digit number a resident can generate and regenerate in place of the Aadhaar number when authenticating, and the UID Token, a 72-character alphanumeric value returned to an authenticating agency that is unique for a given resident and a given agency, so that two agencies cannot match residents by comparing tokens. [UNVERIFIED: the exact UIDAI circular number and date introducing Virtual ID, UID Token and Limited KYC]

Regulation (EU) 2024/1183 of 11 April 2024, in force from 20 May 2024, put the principle into European law: recital 22 says European Digital Identity Wallets “should include a functionality to generate user-chosen and managed pseudonyms, to authenticate when accessing online services”, and recital 60 says that “Unless specific rules of Union or national law require users to identify themselves, accessing services by using a pseudonym should not be prohibited.”

What all of these stop, and what they do not, deserves one sentence each. They stop two relying parties joining their records on the identifier the identity provider gave them. They do not stop those parties joining on an email address, a phone number, a payment instrument, an IP address or a browser fingerprint. And they do not protect anybody against the issuer, which by construction can map every pseudonym back. A pairwise identifier moves the correlation risk from many parties to one; whether that is an improvement depends entirely on whether the one party is accountable.

The ancestry is worth naming, because the idea is older than the web. David Chaum introduced mix networks in “Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms”, Communications of the ACM volume 24 number 2, February 1981, pages 84 to 90, and set out a system of per-organization pseudonyms with transferable credentials in “Security without Identification: Transaction Systems to Make Big Brother Obsolete”, Communications of the ACM volume 28 number 10, October 1985, pages 1030 to 1044. The Tor network, deployed in October 2002 with about a dozen volunteer nodes by the end of 2003 and placed under The Tor Project, Inc. in 2006, is Chaum’s 1981 idea in production.

Fingerprinting: identification without an identifier#

A browser fingerprint is a set of properties a website can read from a visiting browser which, in combination, distinguish it from other browsers. No identifier is stored on the device, so nothing can be deleted, and in most jurisdictions nothing was consented to.

The W3C group note “Mitigating Browser Fingerprinting in Web Specifications”, published by the Privacy Working Group on 25 September 2025, draws the standard distinction. Passive fingerprinting is “browser fingerprinting based on characteristics observable in the contents of Web requests, without the use of any code executed on the client” — the user agent string, the accept headers, the source address. Active fingerprinting covers “techniques where a site runs JavaScript or other code on the local client to observe additional characteristics” — screen geometry, installed typefaces, audio and canvas rendering differences, hardware concurrency.

Three large public studies measured how well it works, and reading them together is more instructive than reading any one.

Peter Eckersley’s “How Unique Is Your Web Browser?”, presented at the Privacy Enhancing Technologies Symposium in 2010, collected data between 27 January and 15 February 2010 from the Electronic Frontier Foundation’s Panopticlick site. After removing duplicates 470,161 fingerprints remained, of which 83.6 per cent were instantaneously unique, rising to 94.2 per cent among browsers with Adobe Flash or a Java virtual machine enabled. The distribution carried at least 18.1 bits of entropy: a randomly chosen browser was expected to share its fingerprint with at best one in 286,777 others. His per-variable entropies give the sense of scale:

Eckersley also measured stability. Among returning users whose fingerprints changed, a deliberately crude heuristic guessed the predecessor correctly in 99.1 per cent of the guesses it made, with a false positive rate of 0.86 per cent. Fingerprints change often and are still followable.

Pierre Laperdrix and colleagues ran AmIUnique and reported 118,934 fingerprints in 2016, 89.4 per cent unique overall, split as 105,829 desktop at 89.4 per cent and 13,105 mobile at 81 per cent. Alejandro Gomez-Boix, Pierre Laperdrix and Benoit Baudry then published “Hiding in the Crowd: an Analysis of the Effectiveness of Browser Fingerprinting at Large Scale” at The Web Conference in 2018, collecting 2,067,942 fingerprints from one of the fifteen most visited French websites — an ordinary commercial audience, not a privacy-interested one — and found only 33.6 per cent unique: 35.7 per cent of 1,816,776 desktop and 18.5 per cent of 251,166 mobile.

The right conclusion is not that fingerprinting stopped working. The earlier figures were measured on self-selected, privacy-conscious desktop populations with unusual software installed, and a general population on phones is far more uniform. Both facts hold at once: fingerprinting identifies a third of a general population outright, which is enormous, and nine in ten of the people trying hardest to avoid it, which is the paradox.

The practical lesson is that anti-fingerprinting measures adopted by few people make those people more identifiable, not less. Eckersley measured the mean surprisal of browsers running Flash blockers at 18.7 bits; a small group with “Privoxy” in the user agent averaged 15.5 bits; all seven users of one privacy-branded browser in his dataset were unique. The only defences that worked made many browsers look identical, which is why the serious approach is to standardize a common configuration rather than randomize an individual one.

The W3C note is admirably blunt about the ceiling: “Advances in techniques for browser fingerprinting suggest that complete elimination of the capability of browser fingerprinting by a determined adversary through solely technical means that are widely deployed is implausible.” The stated goals are therefore to decrease the surface, to increase anonymity sets, to make fingerprinting detectable, and to allow local state to be cleared.

One implementation-detail note with a date. Google announced on 22 April 2025 that Chrome would “maintain our current approach to offering users third-party cookie choice” and would not roll out a new standalone prompt for third-party cookies, ending a plan that had run since 2020 to remove them. As of August 2026, third-party cookies therefore remain in the largest browser, and the fingerprinting question was never a replacement for that debate but a parallel one.

Data minimization as a design rule#

The legal text first, because it is short. Regulation (EU) 2016/679, the General Data Protection Regulation, states at Article 5(1)(c) that personal data shall be “adequate, relevant and limited to what is necessary in relation to the purposes for which they are processed”, under the heading “data minimisation”. Article 4(5) defines pseudonymization as processing “in such a manner that the personal data can no longer be attributed to a specific data subject without the use of additional information, provided that such additional information is kept separately and is subject to technical and organisational measures to ensure that the personal data are not attributed to an identified or identifiable natural person”.

Recital 26 draws the line that everything else hangs from. Pseudonymized data “should be considered to be information on an identifiable natural person”. To decide whether a person is identifiable, “account should be taken of all the means reasonably likely to be used, such as singling out”, by the controller “or by another person”, weighing “the costs of and the amount of time required for identification, taking into consideration the available technology at the time of the processing and technological developments”. Only genuinely anonymous information falls outside the regulation.

Read those together and the design consequence is stark. Pseudonymizing is a security measure that keeps you inside the rules. It is not an exit. The Article 29 Working Party said so directly in Opinion 05/2014 on Anonymisation Techniques, document WP216, adopted on 10 April 2014: “Pseudonymisation reduces the linkability of a dataset with the original identity of a data subject; as such, it is a useful security measure but not a method of anonymisation.”

That same opinion gives the three-question test that is the most useful compliance artefact in this whole area, because it is also a good engineering test:

1. Singling out — can somebody isolate records that identify an individual in the dataset?
2. Linkability — can somebody link at least two records concerning the same data subject, in this dataset or across two?
3. Inference — can somebody deduce, with significant probability, the value of an attribute from the values of others?

A technique that fails any one of the three has not anonymized anything. k-anonymity alone defeats singling out and fails on inference, which is exactly what the homogeneity attack demonstrates.

Now the engineering rule, which is what this section is really for. Data minimization is not a paperwork exercise. It is a sequence of four questions asked field by field, at design time, and it is one of the few privacy activities that reliably reduces both risk and cost.

1. What decision does this field enable? If you cannot name a decision, delete the field. “Analytics” is not a decision.
2. What is the coarsest value that still supports that decision? If the decision is “may this person buy alcohol”, the field is a boolean over-18 flag and not a date of birth. If the decision is “which region should we staff”, the field is the region and not the postcode.
3. How long does the decision need it? Retention is part of minimization. A field kept for ninety days is a smaller liability than the same field kept for seven years, by roughly the ratio of the windows during which a breach can expose it.
4. Who needs to see it joined to a person? Most internal consumers of data need statistics, not people. Give the analytics pipeline a per-purpose pseudonym, not the customer identifier.

Applied to an ordinary sign-up form that sequence usually removes between a third and a half of the fields, and it removes precisely the quasi-identifiers, because quasi-identifiers are the fields that got in by seeming harmless. The full date of birth is the classic case: collected almost everywhere, needed almost nowhere, and worth more to an attacker than the password.

The worked example, carried all the way through#

Ashcombe is a city of 250,000 people. Its council runs a bicycle hire scheme with 40,000 registered members, 300 docking stations and about 2,000,000 trips in the year to 31 March 2026. The council wants to publish trip data so that researchers can study cycling patterns. Follow one record all the way down.

Stage 0, identified. The operational record holds the member’s name, email address, full postcode, date of birth, sex, and for each trip the bike number, start station, start time, end station and end time. This is the correct state for the operational system: you need it to bill people and to return lost property.

Stage 1, pseudonymous. For the research extract, replace name and email with a random 128-bit member reference, stored in a mapping table that stays inside the operations team. Nothing else changes. The extract now contains no names.

It is not anonymous, and here is the arithmetic that proves it. Member reference a91c... made 486 trips in the year. Of those, 291 started at station 118 on a weekday between 08:02 and 08:24, and 268 of those ended at station 41. Station 118 serves three residential buildings. The set of people who live beside station 118, work beside station 41 and leave at ten past eight is not 40,000 people; it is a handful, and a colleague who has seen you arrive knows which. Four points is the general threshold: in “Unique in the Crowd: The privacy bounds of human mobility”, Scientific Reports volume 3, article 1376, 25 March 2013, Yves-Alexandre de Montjoye, Cesar Hidalgo, Michel Verleysen and Vincent Blondel showed that in fifteen months of mobility data for about 1.5 million people, four spatio-temporal points uniquely identified 95 per cent of individuals.

Stage 2, the quasi-identifiers. Suppose the extract also carries postal area, sex and year of birth, because a researcher asked. Ashcombe has 60 postal areas, so about 4,167 residents each; halving for sex gives 2,083; and if about 1.5 per cent of the city shares a given year of birth, the combination describes about 31 people on average.

Average is the wrong statistic. Take the smallest postal area, with 900 residents. If about 0.9 per cent of the population is aged 78, that area holds about 8 such people, so about 4 women: the class has 4 members, not 31. Had the extract carried the full date of birth rather than the year, the expected class size would be 4 divided by 365, which is to say that woman is almost certainly the only person in Ashcombe who fits. This is Sweeney’s finding reproduced with our own numbers.

Stage 3, k-anonymity. Generalize: publish postal district rather than postal area, of which Ashcombe has 5, and a ten-year birth band rather than a year. The smallest district has 28,000 residents. Women in the 60 to 69 band, at about 11 per cent of the population, give 28,000 times 0.5 times 0.11, which is 1,540 people. Every class in the published file is now far above any reasonable k.

Now break it. The council also publishes whether each member used the adapted-cycle service, which has 214 members citywide. Within the class “district 3, female, 60 to 69” there are 4 adapted-cycle members and all 4 rented the same adaptation. Your neighbour is a 63-year-old woman in district 3 who uses the scheme. You have just learned her condition without learning which row is hers. k-anonymity held perfectly and protected nothing that mattered.

Stage 4, differential privacy. Abandon row publication. Publish instead a table of trip counts per station per year, with Laplace noise.

If the unit of protection is one trip, the sensitivity is 1, the noise scale at epsilon 1 is 1, and the standard deviation is 1.41 trips against counts in the thousands. That is free accuracy and a weak promise, because a person who made 486 trips is not protected by a guarantee about one trip.

If the unit of protection is one person, the honest sensitivity is 486, or whatever the maximum contribution turns out to be. The standard fix is to clamp: count at most 50 trips per member per station. Sensitivity becomes 50, the noise scale at epsilon 1 becomes 50, and the standard deviation becomes 70.7 trips. Against station 12 with 41,872 trips that is an error of about 0.17 per cent. Against station 267 with 412 trips it is ruinous, and the published figure could easily be negative. That asymmetry is the real cost of differential privacy and no amount of tuning removes it: the small cells, which are the interesting ones, are the ones the noise destroys.

Then count the budget. The annual per-station table at epsilon 1 costs

1. The same table broken down by 24 hours of the day, as 24 separate queries at epsilon 1, costs 24 under basic composition. Add weekday and weekend and it is 48. Nobody set out to publish with epsilon 48. They set out to publish a useful table, and the budget was spent one reasonable request at a time. This is the real failure mode of differential privacy in production, and it is organizational rather than mathematical.

The design that survives. Give operations the identified record. Give the analytics pipeline a per-purpose relationship pseudonym and no demographics. Give researchers a differentially private query interface with a per-project budget and a named person who signs off spending it. Publish per-station counts, never per-trip rows. Collect year of birth only if a decision depends on age band, and an over-18 flag if that is the real decision. Delete operational trip records after the dispute window, which for this scheme is 90 days. None of that is expensive, and all of it is decided in the first design meeting or not at all.

What actually goes wrong in production#

A short list of real failure patterns, so that you recognize them by sight.

The stable pseudonym that leaks. A per-user random identifier is correctly generated and then written into a URL, a log line, an error report sent to a third-party crash service, and an analytics event. It is now a cross-context identifier, and that it started random is irrelevant.

The hash that is not a pseudonym. An email address or phone number hashed with SHA-256 and no secret key is not pseudonymized in any meaningful sense, because the space of phone numbers is small enough to hash exhaustively.

The pairwise identifier plus the email address. The federation is configured for pairwise subject identifiers and the same assertion carries the email claim, which is the join key.

Two “anonymous” releases from the same population, each individually defensible, whose intersection is not, with nobody whose job it is to notice the second one.

The dimension nobody counted as a quasi-identifier: job title, employer, number of children, rare medication, model of car, first name in a small community. Every one has been the joining column in a real re-identification.

The differential privacy budget with no ledger, and the retention that outlived the purpose that justified it.

Where an identity error causes lasting harm to the person rather than the system, the mechanics of correction and redress are the subject of chapter 11, “What Goes Wrong When Identity Is Wrong”; and the question of which authority is entitled to assert a fact in the first place belongs to chapter 9, “The Register”.

10.98 Common wrong ideas#

Wrong: Removing names and addresses makes a dataset anonymous. Right: Names are among the weakest identifiers in a rich dataset; behavioural columns such as locations, timestamps and ratings are far more distinctive, and Narayanan and Shmatikov showed in 2008 that eight film ratings with approximate dates identified 99 per cent of Netflix subscribers uniquely.

Wrong: Anonymity is a property you can test for in a file. Right: Anonymity is a property of a file together with a stated attacker and everything else that attacker can obtain, so the same untouched file can move from anonymous to identifying because a different dataset was published elsewhere.

Wrong: Pseudonymized data is outside data protection law. Right: GDPR recital 26 states that pseudonymized data which could be attributed to a person using additional information is information on an identifiable natural person, and Article 29 Working Party Opinion 05/2014 says pseudonymization is a useful security measure but not a method of anonymization.

Wrong: k-anonymity with a large k means nobody learns anything. Right: k-anonymity only prevents singling out a row; if every record in an equivalence class shares the same sensitive value, the attacker learns that value with certainty without ever identifying the row, which is why l-diversity and then t-closeness were proposed and why both have their own documented failures.

Wrong: Differential privacy means the analysis cannot tell anyone anything about you. Right: It bounds how much the output changes because you were included, so general facts learned from the population still apply to you whether or not you took part; it protects the decision to participate, not the consequences of knowledge.

Wrong: A published epsilon is a comparable measure of privacy across systems. Right: Epsilon is only meaningful with the neighbouring-dataset definition attached, so a per-event epsilon of 4 and a per-person epsilon of 4 are entirely different promises, and epsilon adds up across releases whether or not anybody is tracking it, so an untracked budget is not a guarantee at all.

Wrong: Pairwise pseudonyms stop services correlating a user. Right: They remove one joining column, and correlation continues through email addresses, phone numbers, payment instruments, addresses, IP addresses and browser fingerprints unless those are removed too; they also never protect against the identity provider, which by construction can map every pseudonym back.

Wrong: Blocking cookies stops a website recognizing you. Right: Browser fingerprinting builds an identifier from readable properties with nothing stored on the device, and the measured uniqueness rates run from 33.6 per cent in a general French population in 2018 to 83.6 per cent among privacy-conscious visitors in 2010, with unusual privacy tools often making a browser more distinctive rather than less.

Wrong: Data minimization is a compliance box that legal fills in later. Right: It is a design activity performed field by field at design time, asking what decision each field enables, the coarsest value that supports that decision, how long it is needed and who needs it joined to a person, and it typically removes the exact fields that turn out to be quasi-identifiers.

10.99 Chapter summary in 20 lines#

1. Identity has a graded opposite with four states — identified, pseudonymous, unlinkable and anonymous — and most systems that claim the fourth have achieved only the second.
2. The difference between pseudonymous and unlinkable is not whether a name is present but whether two records about the same person can be joined.
3. Anonymity is always relative to an anonymity set, so a claim that does not state the size of the set has said nothing measurable.
4. Pfitzmann and Hansen’s terminology paper, version 0.34 of 10 August 2010, gives the field its standard definitions of anonymity, unlinkability, undetectability, unobservability and pseudonymity.
5. Undetectability is strictly harder than anonymity, and a system that hides who sent a message while revealing that a message was sent has only the weaker property.
6. Pseudonyms are classified by scope, from the person pseudonym that links everything to the transaction pseudonym that links nothing, and the relationship pseudonym is usually the right choice.
7. Latanya Sweeney reported in 2000 that 87 per cent of the United States population was likely unique on five-digit ZIP code, sex and full date of birth in 1990 census data.
8. Philippe Golle’s 2006 recalculation on 2000 census data gave 63.3 per cent for the same three attributes and 14.8 per cent with county in place of ZIP.
9. Uniqueness is the wrong threshold, because Golle also found 43.6 per cent of people in groups of five or fewer, rising to 63 per cent for people over sixty.
10. The Massachusetts 1997, AOL 2006, Netflix 2008 and Washington State 2013 cases established that identifiers, search queries, film ratings and hospital records are all re-identifiable by linkage.
11. Daniel Barth-Jones’ 2012 re-examination of the Weld case is a fair caution that published attacks are best cases resting on incomplete population registers.
12. k-anonymity requires every quasi-identifier combination to appear at least k times, and is defeated by homogeneous classes, by background knowledge, and by not composing across releases.
13. l-diversity requires several well-represented sensitive values per class and is defeated by semantically similar values and by classes skewed far from the population.
14. t-closeness bounds the distance between class and population distributions and is defeated by its own utility cost and by the impossibility of listing every quasi-identifier in advance.
15. Differential privacy, defined by Dwork and colleagues in 2006, bounds the ratio of output probabilities between datasets differing by one person, and does not depend on knowing what the attacker knows.
16. Epsilon is a worst-case bound inside an exponential, is meaningless without its neighbouring-dataset definition, and is spent by every release, so an unmanaged budget is no guarantee.
17. Apple used a per-event epsilon of 4 from 2016 and the United States Census Bureau set a total budget of 19.61 for 2020 redistricting data on 8 June 2021, and experts still disagree about that figure.
18. Directed identifiers give each relying party a different subject value for the same person, are specified in OpenID Connect Core 1.0 section 8.1 and SAML 2.0 section 8.3.7, and are law in Austria, Germany and India.
19. Browser fingerprinting identifies without storing anything, was measured at 83.6 per cent unique in 2010 and 33.6 per cent in a general population in 2018, and rare privacy tools make a browser easier to recognize.
20. Data minimization works only as a design rule applied field by field before the system exists, because every field that survives the first design meeting will still be there in ten years.

Chapter sources: Andreas Pfitzmann and Marit Hansen, “A terminology for talking about privacy by data minimization: Anonymity, Unlinkability, Undetectability, Unobservability, Pseudonymity, and Identity Management”, version 0.34, 10 August 2010, for the definitions of anonymity, anonymity set, unlinkability, undetectability and unobservability and the classification of pseudonyms by scope; Latanya Sweeney, “Simple Demographics Often Identify People Uniquely”, Carnegie Mellon University, Data Privacy Working Paper 3, Pittsburgh, 2000, for 87 per cent, 216 million of 248 million, on five-digit ZIP code, sex and full date of birth, with 53 per cent on place and 18 per cent on county; Philippe Golle, “Revisiting the Uniqueness of Simple Demographics in the US Population”, Workshop on Privacy in the Electronic Society, 30 October 2006, for 63.3 and 14.8 per cent on full date of birth, 4.2 and 0.2 per cent on year and month, 0.2 and 0.0 per cent on year alone, 61 per cent on 1990 data by his own method, and 43.6 per cent of the population in groups of five or fewer at county level rising to 63 per cent over age sixty; Latanya Sweeney, “Weaving technology and policy together to maintain confidentiality”, Journal of Law, Medicine and Ethics, volume 25, 1997, pages 98 to 110; Daniel Barth-Jones, “The ‘Re-Identification’ of Governor William Weld’s Medical Information”, July 2012, with NISTIR 8053, “De-Identification of Personal Information”, 2015, for the finding that only about 55 per cent of Cambridge was registered to vote in 1996 to 1997; the AOL Research search log release of 4 August 2006 of about twenty million queries from over 650,000 users, withdrawn by 7 August, and Michael Barbaro and Tom Zeller Jr, “A Face Is Exposed for AOL Searcher No. 4417749”, The New York Times, 9 August 2006; Arvind Narayanan and Vitaly Shmatikov, “Robust De-anonymization of Large Sparse Datasets”, IEEE Symposium on Security and Privacy, 2008, for 100,480,507 ratings by 480,189 subscribers between December 1999 and December 2005, and 99 per cent identification from eight ratings with a 14-day error and 68 per cent from two with a 3-day error; Latanya Sweeney, “Matching Known Patients to Health Records in Washington State Data”, Harvard University Data Privacy Lab, 2013, for 35 of 81 cases matched in 2011 data; Latanya Sweeney, “k-anonymity: a model for protecting privacy”, International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, volume 10, number 5, 2002, pages 557 to 570, following Pierangela Samarati and Latanya Sweeney’s late-1990s work; Ashwin Machanavajjhala, Johannes Gehrke, Daniel Kifer and Muthuramakrishnan Venkitasubramaniam, “l-diversity: Privacy beyond k-anonymity”, 22nd International Conference on Data Engineering, 2006, and ACM Transactions on Knowledge Discovery from Data volume 1, issue 1, March 2007, article 3; Ninghui Li, Tiancheng Li and Suresh Venkatasubramanian, “t-Closeness: Privacy Beyond k-Anonymity and l-Diversity”, 23rd IEEE International Conference on Data Engineering, 15 April 2007, pages 106 to 115; Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith, “Calibrating Noise to Sensitivity in Private Data Analysis”, Theory of Cryptography Conference, March 2006, and Cynthia Dwork, “Differential Privacy”, 33rd International Colloquium on Automata, Languages and Programming, Venice, 10 to 14 July 2006, Lecture Notes in Computer Science volume 4052, pages 1 to 12; Cynthia Dwork and Aaron Roth, “The Algorithmic Foundations of Differential Privacy”, Foundations and Trends in Theoretical Computer Science volume 9, numbers 3 and 4, 2014, pages 211 to 407, for the Laplace mechanism, composition and the proof that fair-coin randomized response is (ln 3, 0)-differentially private; S. L. Warner’s 1965 randomized response paper in the Journal of the American Statistical Association; Ulfar Erlingsson, Vasyl Pihur and Aleksandra Korolova, “RAPPOR”, ACM Conference on Computer and Communications Security, 2014; Apple Differential Privacy Team, “Learning with Privacy at Scale”, 2017, for a per-event epsilon of 4 with sketch parameters of 65,536 by 1,024 for the emoji keyboard and 32,768 by 1,024 over a 250,000-domain dictionary for Safari; the United States Census Bureau press release of 8 June 2021 setting the 2020 Disclosure Avoidance System privacy-loss budget at epsilon 19.61, comprising 17.14 for persons and 2.47 for housing units, against 12.2 in the April 2021 demonstration data; John Abowd and colleagues, “A Simulated Reconstruction and Reidentification Attack on the 2010 U.S. Census”, Harvard Data Science Review, for 97 million person records exactly reconstructed, every resident of 70 per cent of census blocks, from more than 150 billion statistics in 180 table sets, with the Bureau’s earlier figure of at least 52 million re-identifiable respondents, and Steven Ruggles and co-authors, “The Role of Chance in the Census Bureau Database Reconstruction Experiment”, 2021, for the contrary argument; Luc Rocher, Julien Hendrickx and Yves-Alexandre de Montjoye, “Estimating the success of re-identifications in incomplete datasets using generative models”, Nature Communications volume 10, article 3069, 23 July 2019; Yves-Alexandre de Montjoye, Cesar Hidalgo, Michel Verleysen and Vincent Blondel, “Unique in the Crowd”, Scientific Reports volume 3, article 1376, 25 March 2013; OpenID Connect Core 1.0 incorporating errata set 2, 15 December 2023, sections 8 and 8.1; “Assertions and Protocols for the OASIS Security Assertion Markup Language (SAML) V2.0”, OASIS Standard, 15 March 2005, section 8.3; the Austrian source-identifier register authority’s published description of the bereichsspezifisches Personenkennzeichen derived from the Stammzahl under the Austrian E-Government Act; BSI Technical Guideline TR-03110 for Restricted Identification; the Unique Identification Authority of India’s 2018 Virtual ID and UID Token under Limited KYC; Regulation (EU) 2024/1183 of 11 April 2024, in force 20 May 2024, recitals 22 and 60; Regulation (EU) 2016/679, Articles 4(1), 4(5) and 5(1)(c) and recital 26; Article 29 Data Protection Working Party, Opinion 05/2014 on Anonymisation Techniques, WP216, adopted 10 April 2014; NIST Special Publication 800-188, “De-Identifying Government Datasets: Techniques and Governance”, 14 September 2023; 45 CFR 164.514(b)(1) and (b)(2); Peter Eckersley, “How Unique Is Your Web Browser?”, Privacy Enhancing Technologies Symposium, 2010, for 470,161 fingerprints collected between 27 January and 15 February 2010, 83.6 per cent unique, 94.2 per cent among browsers with Flash or Java, at least 18.1 bits of entropy and one in 286,777, per-variable entropies of 15.4, 13.9, 10.0 and 4.83 bits, and 99.1 per cent correct evolution guesses at a 0.86 per cent false positive rate; Pierre Laperdrix and colleagues, AmIUnique, 2016, for 118,934 fingerprints at 89.4 per cent unique; Alejandro Gomez-Boix, Pierre Laperdrix and Benoit Baudry, “Hiding in the Crowd”, The Web Conference, 2018, for 2,067,942 fingerprints at 33.6 per cent unique, 35.7 per cent of 1,816,776 desktop and 18.5 per cent of 251,166 mobile; the W3C Privacy Working Group note “Mitigating Browser Fingerprinting in Web Specifications”, 25 September 2025; the Google Privacy Sandbox announcement of 22 April 2025; David Chaum, “Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms”, Communications of the ACM volume 24 number 2, February 1981, pages 84 to 90, and “Security without Identification”, Communications of the ACM volume 28 number 10, October 1985, pages 1030 to 1044; and The Tor Project’s published history.