k-anonymity explained with an example

Identifiers, quasi-identifiers and sensitive attributes

Before you can measure k, sort the columns into three groups:

• Direct identifiers name a person on their own: name, email, phone number, customer number. They are removed or replaced with pseudonyms before any release.
• Quasi-identifiers do not name anyone alone but can in combination, especially when linked with other data: age or date of birth, ZIP or postcode, gender, job title. Research on US census data famously found that ZIP code, date of birth and gender alone identify a large majority of the population.
• Sensitive attributes are what must stay protected, here the diagnosis. They are not part of the groups.

Equivalence classes and the k of a release

Records with the same values on all quasi-identifiers form an equivalence class. Someone who knows a person's age band, ZIP area and gender can narrow them down to that class, but not further. The class size of each record is one formula:

=COUNTIFS($A$2:$A$13,A2,$B$2:$B$13,B2,$C$2:$C$13,C2)

The k of the release is =MIN(E2:E13). In the example the classes have 4, 3, 3, 1 and 1 records, so k = 1. =COUNTIF(E2:E13,"<"&E15) counts the 2 records that sit in classes smaller than the target of 3. For more patterns with several criteria, see the SUMIFS and COUNTIFS examples.

Worked example: is this survey extract 3-anonymous?

Twelve generalised records with three quasi-identifiers (yellow) and the diagnosis as the sensitive attribute. Column E counts the size of each record's class, and rows 15 to 22 test the release against a target of k = 3.

Worked example: is this survey extract 3-anonymous?

	A	B	C	D	E
1	Age band	ZIP area	Gender	Diagnosis	Class size
2	30-39	803**	F	Asthma	4
3	30-39	803**	F	Flu	4
4	40-49	804**	M	Diabetes	3
5	20-29	805**	F	Flu	3
6	30-39	803**	F	Diabetes	4
7	40-49	804**	M	Diabetes	3
8	30-39	803**	M	Asthma	1
9	20-29	805**	F	Depression	3
10	40-49	804**	M	Diabetes	3
11	30-39	803**	F	Flu	4
12	50-59	804**	F	Asthma	1
13	20-29	805**	F	Asthma	3
14
15	Target k				3
16	k of the release (smallest class)				1
17	Records in classes smaller than k				2
18	Is the release 3-anonymous?				No
19	Highest re-identification risk (1 ÷ k)				100.0%
20	k after suppressing the small classes				3
21	Share of records suppressed				16.7%
22	Highest risk after suppression (1 ÷ k)				33.3%

Synthetic records for practice. Educational only, not legal advice: whether data counts as anonymous depends on the law that applies and on the whole context of the release.

Generalisation and suppression

There are two ways to raise k. Generalisation coarsens the quasi-identifiers: exact ages become 10-year bands and five-digit ZIP codes become three-digit areas such as 803**. The example has already been generalised. Suppression removes the records, or the values, that are still too rare. Removing the man aged 30–39 and the woman aged 50–59 lifts the smallest remaining class to 3, so the release becomes 3-anonymous: =MINIFS(E2:E13,E2:E13,">="&E15) returns 3.

Both cost information. Suppressing 2 of 12 records loses 16.7% of the data, and it is never random: the rare combinations are often exactly the older or minority respondents. Always check whether the statistic you care about, such as the share with asthma, moves after suppression.

Re-identification risk: 1 ÷ k

If an attacker knows which class a person belongs to, the chance of picking the right record is 1 ÷ class size. A class of 1 means a risk of 100%, a class of 3 means 33.3%. The highest risk of the release is therefore 1 ÷ k, and the average risk is the mean of 1 ÷ class size over all records. After suppression the highest risk in the example falls from 100% to 33.3%. Data-sharing guidance often sets thresholds on these risks rather than on k itself, but the idea is the same.

Where k-anonymity is not enough

k-anonymity hides who a record belongs to, not what it says. In the example, all three men aged 40–49 in area 804** have diabetes. The class has k = 3, but anyone who knows a neighbour is in it learns his diagnosis anyway. This is the homogeneity attack, and l-diversity answers it by requiring at least l different sensitive values in every class. k-anonymity also assumes you chose the right quasi-identifiers. An attacker who knows one more attribute, such as the visit date, can split a class again.

Laws such as the GDPR treat truly anonymised data differently from personal data, but they judge anonymisation by the overall re-identification risk, not by one number. Treat k as one check among several.

Common mistakes

• Leaving out a quasi-identifier. Count classes over every attribute an outsider could know. Drop one from the COUNTIFS and the classes look bigger, and safer, than they are.
• Including the sensitive attribute in the class. The diagnosis is what you protect. Grouping by it as well splits the classes and misstates k.
• Reporting the average class size as k. k is the minimum. One unique record makes the whole release 1-anonymous.
• Calling pseudonymised data anonymous. Replacing names with codes leaves every quasi-identifier in place, and whoever holds the key can reverse it.
• Ignoring homogeneous classes. A class where everyone shares the same diagnosis reveals it despite k ≥ 3. Check l-diversity too.
• Suppressing without measuring the loss. Count what you removed and check that key statistics did not shift.