Resolving the Complexity of Some Data Privacy Problems

DOI10.1007/978-3-642-14162-1_33zbMATH Open1288.68058arXiv1004.3811OpenAlexW1880832693MaRDI QIDQ3587455FDOQ3587455

Authors: Jeremiah Blocki, Ryan Williams 

Publication date: 7 September 2010

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

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.

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

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

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)

Cited In (16)

• Data disclosure limitation as a decision problem
• The \(l\)-diversity problem: tractability and approximability
• 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
• On the complexity of the \(l\)-diversity problem
• The effect of homogeneity on the complexity of \(k\)-anonymity
• Clustering with lower-bounded sizes. A general graph-theoretic framework
• \(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
• Parameterized complexity of \(k\)-anonymity: hardness and tractability

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)