k-Anonymity V. Ciriani, S. De Capitani di Vimercati, S. Foresti, and P. Samarati Università degli Studi di Milano, 26013 Crema, Italia {ciriani, decapita, foresti, samarati}@dti.unimi.it To protect respondents’ identity when releasing microdata, data holders often remove or encrypt explicit identifiers, such as names and social security num- bers. De-identifying data, however, provide no guarante