k-attribute-anonymity is hard even for k=2

DOI10.1016/J.IPL.2014.10.011MaRDI QIDQ477690zbMATH OpenOpenAlexFDO

Authors Allan Scott, Venkatesh Srinivasan, 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 complexityNP-hardnessfixed parameter tractabilitydata anonymizationdatabase privacy

Mathematics Subject Classification ID

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

Recommendations

• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• The k-Anonymity Problem Is Hard
• Database Theory - ICDT 2005
• Anonymizing binary and small tables is hard to approximate
• Parameterized complexity of \(k\)-anonymity: hardness and tractability

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Anonymizing binary and small tables is hard to approximate
• Database Theory - ICDT 2005
• Fixed-parameter tractability of anonymizing data by suppressing entries
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Pattern-guided \(k\)-anonymity
• Resolving the Complexity of Some Data Privacy Problems
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY

Cited in

(1)

• Anonymizing binary and small tables is hard to approximate

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

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