Worst-Case Background Knowledge for Privacy-Preserving Data Publishing

By David J. Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes Gehrke, Joseph Y. Halpern. IEEE International Conference on Data Engineering, 2007

316 citations recorded by the source corpus.

Recent work has shown the necessity of considering an attacker's background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what background knowledge the attacker possesses. Thus, it is important to consider the worst-case. In this paper, we initiate a formal study of worst-case background knowledge. We propose a language that can express any background knowledge about the data. We provide a polynomial time algorithm to measure the amount of disclosure of sensitive information in the worst case, given that the attacker has at most k pieces of information in this language. We also provide a method to efficiently sanitize the data so that the amount of disclosure in the worst case is less than a specified threshold.

Subfields: Artificial Intelligence, Sociology and Political Science

View Paper: https://www.semanticscholar.org/paper/a241fa9325363f58c5430cf80cb8d75968974cae

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

Citations in the corpus

Publishing Search Logs—A Comparative Study of Privacy Guarantees (2009, background): “Thus people have studied limited classes of adversaries [22, 23, 25, 31, 33].”
Composition attacks and auxiliary information in data privacy (2008, background): “This assumption was also made in previous studies [30, 27].”
Airavat: Security and Privacy for MapReduce (2010, background): “It fundamentally assumes that the adversary’s knowledge is limited to the quasi-identifying attributes and thus fails to provide any protection against adversaries who have additional inform ation [31,32].”
Minimality Attack in Privacy Preserving Data Publishing (2007, methodology): “We also have examples to show the feasibility of minimality attacks on the algorithms for (c, k)-safety in [13], Personalized Privacy in [24], and sequential releases in [18] and [25].”
Resisting structural re-identification in anonymized social networks (2008, methodology): “The use of attribute knowledge to re-identify individualsinanonymizeddatahasbeenwellstudied,ashave techniques for resisting it [31, 32 ,41,42,44].”
Trustworthy AI: From Principles to Practices (2021, background): “Different principles of quantitative data anonymization have been developed, such as k-anonymity [288], (c,k )-safety [236], and δ -presence [253].”
Privacy: Theory meets Practice on the Map (2008, background): “Subsequent work [8] characterized the worst case knowledge needed to break the anonymity of a data-set and extended the work to releases of multiple views of the data [32].”
Differentially private data release for data mining (2011, background): “Unlike generalization, bucketization [42, 29] does not modify the QID and the sensitive attribute (SA) values but instead de-associates the relationship between the two.”
On the tradeoff between privacy and utility in data publishing (2009, background): “Bucketization [30, 14, 22] was proposed to remedy this drawback.”