Achieving k-anonymity privacy protection using generalization and suppression

Often a data holder, such as a hospital or bank, needs to share person-specific records in such a way that the identities of the individuals who are the subjects of the data cannot be determimed. One way to achieve this is to have the released records adhere to k-anonymity, which means each released record has at least (k-l) other records in the release whose values are indistinct over those fields that appear in external data. So, k-anonymity provides privacy protection by guaranteeing that each released record will relate to at least k individuals even if the records are directly linked to external information. This paper provides a formal presentation of combining generalization and suppression to achieve k-anonymity. Generalization involves replacing (or recoding) a value with a less specific but semantically consistent value. Suppression involves not releasing a value at all. The Preferred Minimal Generalization Algorithm (MinGen), which is a theoretical algorithm presented herein, combines these techniques to provide k-anonymity protection with minimal distortion. The real-world algorithms Datafly and mu-Argus are compared to MinGen. Both Datafly and mu-Argus use heuristics to make approximations, and so, they do not always yield optimal results. It is shown that Datafly can over distort data and mu-Argus can additionally fail to provide adequate protection.