Anonymity in Multi-Instance Micro-Data Publication

In this paper we study the problem of anonymity in multi-instance (MI) micro-data publication. The classical k-anonymity approach is shown to be insufficient and/or inappropriate for MI databases. Thus, it is extended to MI databases, resulting in a more general setting of MI k-anonymity. We show that MI k-anonymity problem is NP-Hard and the attack model for MI databases is different from that of single-instance databases. We make an observation that the introduced MI k-anonymity is not a strong privacy guarantee when anonymity sets are highly unbalanced with respect to instance counts. To this end a new anonymity principle, called p-certainty, which is unique to MI case is introduced. Aclustering algorithms solving the p-certainty anonymity principle is developed and experimentally evaluated.