The complexity of a data privacy protection algorithm
Shih-Ying Hsu, Ruizhong Wei · 2011
To share data with other parties in computer collaboration is an important issue of data security. k-anonymity and ℓ-diversity are used to protect privacy and secure data sharing. It was proved that optimal k-anonymity are NP hard for k ≥ 3 and that there is a polynomial algorithm for optimal 2-anonymity. This paper proves that an optimal 2-diversity is NP hard. Since ℓ-diversity must be ℓ-anonymity, it follows that the ℓ-diversity is NP hard for ℓ ≥ 2. The result shows that finding polynomial algorithm for efficient (but not optimal) ℓ-diversity is important.