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.