K-anonymity: definition, worked example and its limits

Direct identifiers vs. quasi-identifiers

A direct identifier points to a person on its own: full name, National Insurance or Social Security number, NHS or patient number, email address. A quasi-identifier does not identify anyone in isolation but does in combination: date of birth, postcode, sex, job title, nationality, admission date. Removing direct identifiers does not make a table anonymous if quasi-identifiers remain that can be matched against another source such as the electoral roll, a LinkedIn profile or a local news story. That matching is the core of re-identification.

The remaining columns are usually sensitive attributes (diagnosis, salary, disciplinary outcome): exactly what analysts want to study, and exactly what must not be attributable to anyone.

How it is achieved: generalisation and suppression

• Generalisation replaces a value with a less precise one. Age 34 becomes “30–39”; postcode SW1A 2AA becomes “SW1A”; a full date of birth is reduced to the year.
• Suppression removes values or whole rows that are still unique after generalising, such as the only 97-year-old patient in a small district.
• Choosing k: no statute sets a number. A higher k lowers risk but costs detail; the right value depends on where the data will be released and who can access it.

In the US, the HIPAA Privacy Rule’s Safe Harbor method uses the same logic: it keeps only the first three digits of a ZIP code (where that area has more than 20,000 people) and only the year of most dates. The alternative, Expert Determination, asks a qualified expert to confirm that the re-identification risk is very small.

A worked example with fictitious data

Start with four fictitious patients listed with name, postcode, age, sex and diagnosis. Drop the names, generalise postcode and age, and suppress sex. The result is 2-anonymous: each quasi-identifier combination appears twice.

Look at the last two rows. You cannot tell which one is your 45-year-old neighbour from LS17, yet you now know she has diabetes, because both rows share the diagnosis. This is the homogeneity attack, and it shows that k-anonymity alone does not stop disclosure.

l-diversity and t-closeness

Two refinements were proposed to close that gap. l-diversity (Machanavajjhala et al., 2006) requires each group of equivalent rows to contain at least l well-represented values of the sensitive attribute. t-closeness (Li, Li and Venkatasubramanian, 2007) goes further: the distribution of the sensitive attribute inside each group must stay within a threshold t of its distribution across the whole table, so belonging to a group reveals little that is new.

The EU Article 29 Working Party’s Opinion 05/2014 on anonymisation techniques treats all three as forms of generalisation and concludes that none is bulletproof: they cut the risk of singling out but may still allow inference or linkage with other datasets. The UK ICO’s anonymisation guidance makes a similar point through its “motivated intruder” test.

Where k-anonymity breaks down

• It depends on your list of quasi-identifiers. If an attacker knows something you did not anticipate, such as an occupation or the exact date of an incident, the guarantee evaporates.
• It degrades with many columns. With dozens of attributes, forming groups of k rows forces so much generalisation that the data stops being useful.
• It does not cover repeated releases. Two k-anonymous versions of the same database, published months apart, can be cross-matched.
• It is not a legal standard. Neither the UK GDPR nor the EU GDPR mentions k-anonymity; Recital 26 asks you to consider all means reasonably likely to be used to identify someone.

Spreadsheets vs. free-text documents

K-anonymity was designed for databases and spreadsheets with consistent columns. If you hold a patient list or a case register, thinking in equivalence classes makes sense: anonymise the Excel file column by column and then check which combinations are still unique.

A court judgment, a clinical letter or an email thread is different. There are no columns; identifying details are woven into the narrative. What matters is finding and removing direct identifiers (names, ID numbers, addresses, phone numbers, vehicle registrations) and then reviewing context: unique job titles, very specific dates, rare events or cross-references that reveal the person even with the name blacked out. Anonymised medical records that still mention “the only female surgeon at the community hospital” still point to someone.

Anonimatum is built for that second scenario. It uses AI and patterns to detect names, dates, addresses, amounts and ID numbers in PDF, Word, Excel and other formats, and lets you review every suggestion before applying irreversible redaction. Judging which contextual detail must go remains a human decision; the tool removes the mechanical work.