\(k\)-attribute-anonymity is hard even for \(k=2\)

DOI10.1016/j.ipl.2014.10.011zbMath1302.68128OpenAlexW2029584013MaRDI QIDQ477690

Venkatesh Srinivasan, Allan Scott, Ulrike Stege

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.10.011

zbMATH Keywords

computational complexityfixed parameter tractabilityNP-hardnessdata anonymizationdatabase privacy

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Authentication, digital signatures and secret sharing (94A62)

Cites Work

• Unnamed Item
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Anonymizing binary and small tables is hard to approximate
• Fixed-parameter tractability of anonymizing data by suppressing entries
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• Resolving the Complexity of Some Data Privacy Problems
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• Database Theory - ICDT 2005
• Pattern-Guided k-Anonymity

This page was built for publication: \(k\)-attribute-anonymity is hard even for \(k=2\)