date: |
     IBM Research - India, New Delhi and Bengaluru.\
    [*{vechakra, pvinayak, ysabharwal}@in.ibm.com*]{} 
title: ' On the Complexity of the $k$-Anonymization Problem '
---

Introduction {#sec:intro}
============

Various organization such as hospitals and insurance companies collect massive amount of personal data. These need to be released publicly for the purpose of scientific data mining; for instance, data collected by hospitals could be mined to infer epidemics. However, a major risk in releasing personal data is that they can be used to infer sensitive information about individuals. A natural idea for protecting privacy is to remove obvious personal identifiers such as social security number, name and driving license number. However, Sweeney [@Swe02] showed that such a deidentified database can be joined with other publicly available databases (such as voter lists) to reidentify individuals. For instance, she showed that 87% of the population of the United States can be uniquely identified on the basis of gender, date of birth and zipcode. In the literature, such an identity leaking attribute combination is called a quasi-identifier. It is important to recognize quasi-identifiers and apply protective measures to eliminate the risk of identity disclosure via join attacks. Samaratti and Sweeyney [@Sam-Swe; @Swe02] introduced the notion 