A Coalitional Game Theoretic Mechanism for Privacy Preserving Publishing Based on k-Anonymity.

Abstract: k-Anonymity is one of the most popular techniques for protecting the privacy of an individual and hence preventing an adversary from gaining sensitive information. The observed limitations in this process are: i) The anonymization is done based on an assumed value of k, ii) the information loss can be found only after the anonymization is done, iii) if the information loss is found to be more than the affordable loss then another k is assumed, iv) For each k the whole process has to be repeated. This paper discusses a novel approach using Coalitional Game Theory to overcome the limitations of k-anonymity. The approach helps fix up the privacy levels based on the threshold given for the information loss. To achieve the anonymity, each tuple is assumed to be an agent and is assigned payoff using concept hierarchy tree (CHT) of quasi identifiers (QID) of the given data, later coalitions between the tuples are formed based on their payoffs. We can fix up the boundaries of k for k-anonymity based on the threshold given for the information loss. The experimental results showing the practicality and scalability are presented. [Copyright &y& Elsevier]