Non-homogeneous Generalization in Privacy Preserving Data Publishing

摘要

Most previous research on privacy-preserving data publishing, based on the fc-anonymity model, has followed the simplistic approach of homogeneously giving the same generalized value in all quasi-identifiers within a partition. We observe that the anonymiza-tion error can be reduced if we follow a non-homogeneous generalization approach for groups of size larger than fc. Such an approach would allow tuples within a partition to take different generalized quasi-identifier values. Anonymization following this model is not trivial, as its direct application can easily violate fc-anonymity. In addition, non-homogeneous generalization allows for additional types of attack, which should be considered in the process. We provide a methodology for verifying whether a non-homogeneous generalization violates fc-anonymity. Then, we propose a technique that generates a non-homogeneous generalization for a partition and show that its result satisfies fc-anonymity, however by straightforwardly applying it, privacy can be compromised if the attacker knows the anonymization algorithm. Based on this, we propose a randomization method that prevents this type of attack and show that fc-anonymity is not compromised by it. Non-homogeneous generalization can be used on top of any existing partitioning approach to improve its utility. In addition, we show that a new partitioning technique tailored for non-homogeneous generalization can further improve quality. A thorough experimental evaluation demonstrates that our methodology greatly improves the utility of anonymized data in practice.