K-anonymity


k-anonymity is a property possessed by certain anonymized data. The concept of k-anonymity was first introduced by Latanya Sweeney and Pierangela Samarati in a paper published in 1998 as an attempt to solve the problem: "Given person-specific field-structured data, produce a release of the data with scientific guarantees that the individuals who are the subjects of the data cannot be re-identified while the data remain practically useful." A release of data is said to have the k-anonymity property if the information for each person contained in the release cannot be distinguished from at least individuals whose information also appear in the release.
k-anonymity received widespread media coverage in 2018 when British computer scientist Junade Ali used the property alongside cryptographic hashing to create a communication protocol to anonymously verify if a password was leaked without disclosing the searched password. This protocol was implemented as a public API in Troy Hunt's Have I Been Pwned? service and is consumed by multiple services including password managers and browser extensions. This approach was later replicated by Google's Password Checkup feature.

Methods for ''k''-anonymization

In the context of k-anonymization problems, a database is a table with n rows and m columns. Each row of the table represents a record relating to a specific member of a population and the entries in the various rows need not be unique. The values in the various columns are the values of attributes associated with the members of the population. The following table is a nonanonymized database consisting of the patient records of some fictitious hospital in Kochi.

NameAgeGenderState of domicileReligionDisease
Ramsha30FemaleTamil NaduHinduCancer
Yadu24FemaleKeralaHinduViral infection
Salima28FemaleTamil NaduMuslimTB
Sunny27MaleKarnatakaParsiNo illness
Joan24FemaleKeralaChristianHeart-related
Bahuksana23MaleKarnatakaBuddhistTB
Rambha19MaleKeralaHinduCancer
Kishor29MaleKarnatakaHinduHeart-related
Johnson17MaleKeralaChristianHeart-related
John19MaleKeralaChristianViral infection


There are 6 attributes and 10 records in this data. There are two common methods for achieving k-anonymity for some value of k.
  1. Suppression: In this method, certain values of the attributes are replaced by an asterisk '*'. All or some values of a column may be replaced by '*'. In the anonymized table below, we have replaced all the values in the 'Name' attribute and all the values in the 'Religion' attribute with a '*'.
  2. Generalization: In this method, individual values of attributes are replaced with a broader category. For example, the value '19' of the attribute 'Age' may be replaced by ' ≤ 20', the value '23' by '20 < Age ≤ 30', etc.
The next table shows the anonymized database.

NameAgeGenderState of domicileReligionDisease
*20 < Age ≤ 30FemaleTamil Nadu*Cancer
*20 < Age ≤ 30FemaleKerala*Viral infection
*20 < Age ≤ 30FemaleTamil Nadu*TB
*20 < Age ≤ 30MaleKarnataka*No illness
*20 < Age ≤ 30FemaleKerala*Heart-related
*20 < Age ≤ 30MaleKarnataka*TB
*Age ≤ 20MaleKerala*Cancer
*20 < Age ≤ 30MaleKarnataka*Heart-related
*Age ≤ 20MaleKerala*Heart-related
*Age ≤ 20MaleKerala*Viral infection


This data has 2-anonymity with respect to the attributes 'Age', 'Gender' and 'State of domicile' since for any combination of these attributes found in any row of the table there are always at least 2 rows with those exact attributes. The attributes available to an adversary are called quasi-identifiers. Each quasi-identifier tuple occurs in at least k records for a dataset with k-anonymity.
Meyerson and Williams demonstrated that optimal k-anonymity is an NP-hard problem, however heuristic methods such as k-Optimize as given by Bayardo and Agrawal often yield effective results. A practical approximation algorithm that enables solving the k-anonymization problem with an approximation guarantee of was presented by Kenig and Tassa.

Possible attacks

While k-anonymity is a promising approach to take for group based anonymization given its simplicity and wide array of algorithms that perform it, it is however susceptible to many attacks. When background knowledge is available to an attacker, such attacks become even more effective. Such attacks include:
Because k-anonymization does not include any randomization, attackers can still make inferences about data sets that may harm individuals. For example, if the 19-year-old John from Kerala is known to be in the database above, then it can be reliably said that he has either cancer, a heart-related disease, or a viral infection.
K-anonymization is not a good method to anonymize high-dimensional datasets. For example, researchers showed that, given 4 locations, the unicity of mobile phone timestamp-location datasets can be as high as 95%.
It has also been shown that k-anonymity can skew the results of a data set if it disproportionately suppresses and generalizes data points with unrepresentative characteristics. The suppression and generalization algorithms used to k-anonymize datasets can be altered, however, so that they do not have such a skewing effect.

Hash-based ''k''-Anonymity

Hash-based k-Anonymity has been largely developed by Junade Ali, initially for preventing Compromised Credential Checking and later for real-time anonymisation of MAC addresses.
This approach works by taking a cryptographic hash of one dimensional data and truncating the hash such that there are at least hash collisions. This approach allows for efficient anonymised searching of large datasets, such as breached passwords. This approach can further be used to provide a formally demonstrable level of anonymity to privacy-sensitive data, allowing a precise trade-off to be made between information leakage and functionality.