How Anonymous Is k-Anonymous? Look at Your Quasi-ID

The concept of quasi-ID (QI) is fundamental to the notion of k-anonymity that has gained popularity recently as a privacy-preserving method in microdata publication. This paper shows that it is important to provide QI with a formal underpinning, which, surprisingly, has been generally absent in the literature. The study presented in this paper provides a first look at the correct and incorrect uses of QI in k-anonymization processes and exposes the implicit conservative assumptions when QI is used correctly. The original notions introduced in this paper include (1) k-anonymity under the assumption of a formally defined external information source, independent of the QI notion, and (2) k-QI, which is an extension of the traditional QI and is shown to be a necessary refinement. The concept of k-anonymity defined in a world without using QI is an interesting artifact itself, but more importantly, it provides a sound framework to gauge the use of QI for k-anonymization. Preliminary version appeared as [2]. Part of Bettini’s work was performed at the University of Vermont and at George Mason University. The authors acknowledge the partial support from NSF with grants 0242237, 0430402, and 0430165, and from MIUR with grant InterLink II04C0EC1D.