k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
📜 Abstract
Consider a data holder, such as a hospital or a bank, that has a privately held collection of person-specific, field structured data. Suppose the data holder wants to share a version of the data with researchers. How can a data holder release a version of its private data with scientific guarantees that the individuals who are the subjects of the data cannot be re-identified while the data remain practically useful? The solution provided in this paper includes a formal protection model named k-anonymity and a set of accompanying policies for deployment. A release provides k-anonymity protection if the information for each person contained in the release cannot be distinguished from at least k-1 individuals whose information also appears in the release. This paper also examines re-identification attacks that can be realized on releases that adhere to k-anonymity unless accompanying policies are respected. The k-anonymity protection model is important because it forms the basis on which the real-world systems known as Datafly, µ-Argus and k-Similar provide guarantees of privacy protection.
✨ Summary
The paper introduced a formal definition of k-anonymity: every released quasi-identifier pattern must occur in at least k records. It also established quasi-identifiers as an operational mechanism for controlling re-identification through linkage with external data, and documented unsorted-matching, complementary-release, and temporal attacks that require release-management policies in addition to table-level anonymization.
The model became a foundation for subsequent privacy-preserving data-publishing research. Later work identified limitations involving sensitive-attribute disclosure and background knowledge, leading to the l-diversity criterion, which explicitly extends k-anonymity to address those attacks. (pure.psu.edu) Further research proposed t-closeness to constrain the distribution of sensitive values within equivalence classes relative to the overall dataset. (doi.org) Algorithmic research also studied the computational difficulty of producing utility-preserving optimal k-anonymous releases, proving NP-hardness for general formulations while giving approximation results for constant k. (researchgate.net) The paper itself identifies Datafly, µ-Argus, and k-Similar as systems applying the model, and later privacy-preserving data-publishing surveys treat k-anonymity and its extensions as a central lineage in statistical disclosure control. (dataprivacylab.org)