Every Anonymization Begins with k: A Game-Theoretic Approach for Optimized k Selection in k-Anonymization

摘要

Privacy preservation is one of the greatest concerns when data is shared between different organizations. On the one hand, releasing data for research purposes is inevitable. On the other hand, sharing this data can jeopardize users' privacy. An effective solution, for the sharing organizations, is to use anonymization techniques to hide the users' sensitive information. One of the most popular anonymization techniques is k-Anonymization in which any data record is indistinguishable from at least k-1 other records. However, one of the fundamental challenges in choosing the value of k is the trade-off between achieving a higher privacy and the information loss associated with the anonymization. In this paper, the problem of choosing the optimal anonymization level for k-anonymization, under possible attacks, is studied when multiple organizations share their data to a common platform. In particular, two common types of attacks are considered that can target the k-anonymization technique. To this end, a novel game-theoretic framework is proposed to model the interactions between the sharing organizations and the attacker. The problem is formulated as a static game and its different Nash equilibria solutions are analytically derived. Simulation results show that the proposed framework can significantly improve the utility of the sharing organizations through optimizing the choice of k value.