Resolving the Complexity of Some Data Privacy Problems

DOI10.1007/978-3-642-14162-1_33MaRDI QIDQ3587455zbMATH OpenOpenAlexFDO

Authors Jeremiah Blocki, Ryan Williams

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.3811

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Abstract: We formally study two methods for data sanitation that have been used extensively in the database community: k-anonymity and l-diversity. We settle several open problems concerning the difficulty of applying these methods optimally, proving both positive and negative results: 1. 2-anonymity is in P. 2. 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. 3. 3-anonymity with only 27 attributes per record is MAX SNP-hard. 4. For databases with n rows, k-anonymity is in O(4^n poly(n)) time for all k > 1. 5. For databases with n rows and l <= log_{2c+2} log n attributes over an alphabet of cardinality c = O(1), k-anonymity is in P. Assuming c, l = O(1), k-anonymity is in O(n). 6. 3-diversity with binary attributes is NP-hard, with one sensitive attribute. 7. 2-diversity with binary attributes is NP-hard, with three sensitive attributes.

Recommendations

• On the complexity of the privacy problem in databases
• Addressing Complexity in a Privacy Expert System
• The complexity of differential privacy
• scientific article; zbMATH DE number 2088072
• Theory of Cryptography
• Some basics on privacy techniques, anonymization and their big data challenges
• Privacy and Communication Complexity

Cited in

(16)

• The l-diversity problem: tractability and approximability
• Data disclosure limitation as a decision problem
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• Discovery Science
• Publishing anonymous survey rating data
• Pattern-guided \(k\)-anonymity
• Using patterns to form homogeneous teams
• The k-Anonymity Problem Is Hard
• Clustering with lower-bounded sizes. A general graph-theoretic framework
• On the complexity of the \(l\)-diversity problem
• The effect of homogeneity on the complexity of \(k\)-anonymity
• \(k\)-attribute-anonymity is hard even for \(k=2\)
• Addressing Complexity in a Privacy Expert System
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Constrained obfuscation of relational databases

This page was built for publication: Resolving the Complexity of Some Data Privacy Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587455)