Comparisons of K-anonymization and randomization schemes under linking attacks

Recently K-anonymity has gained popularity as a privacy quantification against linking attacks, in which attackers try to identify a record with values of some identifying attributes. If attacks succeed, the identity of the record will be revealed and potential confidential information contained in other attributes of the record will be disclosed. K-anonymity counters this attack by requiring that each record must be indistinguishable from at least K - 1 other records with respect to the identifying attributes. Randomization can also be used for protection against linking attacks. In this paper, we compare the performance of K-anonymization and randomization schemes under linking attacks. We present a new privacy definition that can be applied to both k-anonymization and randomization. We compare these two schemes in terms of both utility and risks of privacy disclosure, and we promote to use R-U confidentiality map for such comparisons. We also compare various randomization schemes.