K-anonymity

In this section, we introduce the concepts of de-identification, re-identification, quasi-identifier, and K-anonymity.

De-identification

The table below is a fictional healthcare database, containing the name, data of birth, ZIP code, gender and disease of hospital patient. This example is directly taken from the paper “Data Privacy: Definitions and Technique; by Sabrina De Capitani di Vimercati, Sara Foresti, Giovanni Livraga, Pierangela Samarati”, with randomly generated first and last names.

Table 1

This table clearly contains personal and confidential information, and the patients concerned have the right for this information not to be disclosed publicly. On the other hand, analysing this data might help derive some correlation between some factors (such as a age, gender, or location) and disease, leading to a better understanding of these diseases, and hopefully improving treatment.

For instance, Covid-19 seems to have a different death rate for men and women, and understanding if this difference is biological or social could help treat it or mitigate its impact.

Of course, the data controller can de-identify the data before releasing it, by removing the attributes that uniquely identify a respondent. In this case, the name in the table could be removed, keeping only the date of birth, the ZIP code and the gender.

Re-identification with quasi-identifiers

However, as demonstrated in the Netflix case mentioned before, it might be possible to re-identify data tuples, i.e., to find the identity corresponding to a data tuple using information attributes which, on their own, would not be enough. Such attributes are called quasi-identifiers. For instance, a seminal paper by Sweeney showed that 87% of the population in the United States have a unique combination based only on 5-digit ZIP, gender and date of birth.

In other words, if you assume that an attacker knows the ZIP code, gender and date of birth of the whole US population, then even if one removes the names of every single patient above, the attacker would be able to re-identify 87%.

For instance, consider the attacker has the following information about the population.

If we were to release the following de-identified Table 2, could you map each identifier with a name? Note that we use arbitrary disease names here.

Table 2

Since it is possible to identify each individual with a unique name, we now decide to remove some of the information. In Table 3, we remove the day and the month of the date of birth, as well as the gender. For each id in Table 3, which name could it correspond to?

Table 3

We do something similar in Table 4, by removing the date of birth, but keeping the gender. For each id in Table 3, which name could it correspond to?

Table 4

K-anonymity

This leads us to the definition of k-anonymity: A table is k-anonymous if every combination of values of quasi-identifiers can be indistinctly matched to at least k respondents. If you can re-identify exactly each individual, then k=1; if you know that each individual is in a group of two tuples, then k=2, etc.

In order to calculate the k-anonymity of a table, the easiest is to associate each possible combination of quasi-identifiers values present in the table with a specific class. Different tuples with the same combination of quasi-identifiers will therefore be associated with the same class. The value for k is cardinality of the smallest class (i.e., the smallest number of tuples that have the same combination of quasi-identifiers).

We provide below the identification of all the relevant classes for the tables 2-4 presented above, as well as the resulting k-anonymity.

Table 2 with classes

Table 3 with classes

It is worth remarking that, for Table 3, even though class 0 has 4 elements, the k-anonymity is 2 because the class 1 has only 2 elements.

Table 4 with classes

In the next section, we introduce data generalisation techniques to increase the k-anonymity of a table.

References

• De Capitani Di Vimercati, S., Foresti, S., Livraga, G. and Samarati, P., 2012. Data privacy: definitions and techniques. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 20(06), pp.793-817.