Jeremiah Blocki
A Complete Classification of the Computational Complexity of K-Anonymity
K-Anonymization is a technique used to publicly release a database, while
ensuring both the privacy and the accuracy of the released information. One
general model of the problem allows for cells in the database to be suppressed
until each row is identical to at least k-1 other rows. In order to maximize
the utility of the database we attempt to minimize the number of suppressed
cells necessary to guarantee K-Anonymity. We show that optimal binary
3-Anonymity, where all of the attribute values are 0 or 1, is NP-Hard. This
improves upon the result of Aggarwal et al., who showed that ternary
3-Anonymity is NP-Hard. We believe our proof that optimal 3-Anonymity is
NP-Hard is simpler than the independent proof given by Bonizzoni et al
(July, 2007). On the positive side we show that there is a polynomial time
algorithm for optimal 2-Anonymity. This completes the classification of the
computational complexity of k-anonymity.