Enhanced P-Sensitive K-Anonymity Models for Privacy Preserving Data Publishing

Abstract. Publishing data for analysis from a micro data table containing sensitive attributes, while maintaining individual privacy, is a problem of increasing significance today. The k-anonymity model was proposed for privacy preserving data publication. While focusing on identity disclosure, k-anonymity model fails to protect attribute disclosure to some extent. Many efforts are made to enhance the k-anonymity model recently. In this paper, we propose two new privacy protection models called (p, α)-sensitive k-anonymity and (p +, α)-sensitive k-anonymity, respectively. Different from previous the p-sensitive k-anonymity model, these new introduced models allow us to release a lot more information without compromising privacy. Moreover, we prove that the (p, α)-sensitive and (p +, α)-sensitive k-anonymity problems are NP-hard. We also include testing and heuristic generating algorithms to generate desired micro data table. Experimental results show that our introduced model could significantly reduce the privacy breach. 1