05780561

a

05780561 Blocki, Jeremiah Williams, Ryan Resolving the complexity of some data privacy problems. Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6--10, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-14161-4/pbk). Lecture Notes in Computer Science 6199, 393-404 (2010). 2010 Berlin: Springer EN

doi:10.1007/978-3-642-14162-1_33

Summary: We formally study two methods for data sanitation that have been used extensively in the database community: $k$-anonymity and $\ell $-diversity. We settle several open problems concerning the difficulty of applying these methods optimally, proving both positive and negative results: $\bullet$ 2-anonymity is in P. $\bullet$ The problem of partitioning the edges of a triangle-free graph into 4-stars (degree-three vertices) is NP-hard. This yields an alternative proof that 3-anonymity is NP-hard even when the database attributes are all binary. $\bullet$ 3-anonymity with only 27 attributes per record is MAX SNP-hard. $\bullet$ For databases with $n$ rows, $k$-anonymity is in $O(4^{n } \cdot \text{poly}(n)))$ time for all $k > 1$. $\bullet$ For databases with $\ell $ attributes, alphabet size $c$, and $n$ rows, $k$-Anonymity can be solved in $2^{O(k^2 (2c)^\ell)} + O(n \ell)$ time. $\bullet$ 3-diversity with binary attributes is NP-hard, with one sensitive attribute. $\bullet$ 2-diversity with binary attributes is NP-hard, with three sensitive attributes.