Source-linked AI summary
Worst-Case Background Knowledge for Privacy-Preserving Data Publishing
David J. Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes Gehrke, Joseph Y. Halpern
TL;DR
The paper addresses privacy disclosure when publishers do not know an attacker’s background knowledge. It introduces an expressive language and efficient worst-case analysis, then uses that analysis to sanitize data below a chosen disclosure threshold.
Problem
Publishers generally do not know which background knowledge attackers possess, while existing privacy criteria do not cover all knowledge types or dependencies between sensitive values.
Method
The paper represents background knowledge with basic implications, bounds attacker power by their number, and computes worst-case disclosure to guide bucketization.
Results
The paper provides an efficient method to determine worst-case disclosure over sets of bounded-size background knowledge and to find a bucketization robust below a desired threshold.
Takeaways & Limitations
Worst-case analysis enables privacy protection without requiring the publisher to know the attacker’s exact background knowledge.
Takeaways & Limitations
Using basic implications can produce conservative bucketizations when relevant attacker knowledge requires many such units, motivating richer basic atoms.
Abstract
from arXiv · showhide
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 a specified number of 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.
1. Introduction
Privacy-preserving publication must account for attackers’ unknown background knowledge, because existing criteria can leave sensitive values inferable. The paper proposes a general framework to measure and limit worst-case disclosure.
- Motivation: Attackers may combine published non-sensitive attributes with external data to identify individuals and infer their sensitive values.The motivating setting includes tables containing sensitive attributes such as disease and non-sensitive attributes such as address, gender, and age.
- Limitations of Existing Criteria: k-anonymity can disclose an individual’s sensitive value when all records in a bucket share that value, and background knowledge can make disease frequencies informative.The paper illustrates these risks using a 5-anonymous table and an attacker identifying individuals through age, gender, and ZIP code.
- Limitations of Existing Criteria: ℓ-diversity addresses knowledge that an individual does not have a particular sensitive value, but does not protect against other background knowledge such as correlations between people’s health conditions.In the example, knowledge about Hannah’s flu vaccination changes the inferred probability that Charlie has flu from 2/5 to 10/19.
- Proposed Framework: The paper proposes a language expressive enough to represent arbitrary properties of sensitive values and uses basic information units to model an attacker’s background knowledge.This generalizes beyond the restricted knowledge type handled by ℓ-diversity.
- Proposed Framework: Given a bound on the number of knowledge units, the framework quantifies worst-case disclosure and supports efficient sanitization below a specified threshold.The method also searches for a minimally sanitized table, preserving utility subject to the disclosure constraint.
2. Framework
The framework models privacy-preserving publication with bucketization, a language for arbitrary background knowledge, and bounded attackers whose knowledge is limited by the number of basic implications. It defines worst-case disclosure and develops polynomial-time computation and sanitization techniques, while identifying dependencies across buckets and representation size as important considerations.
- Formal model: The publisher models a table of individuals with one sensitive attribute and non-sensitive attributes, then publishes a sanitized version protecting sensitive information from attackers described in language L.The paper uses bucketization as its primary sanitization method, while noting that the results also hold for full-domain generalization.
- Sanitization methods: Bucketization partitions tuples into buckets and randomly permutes sensitive values within each bucket; full-domain generalization instead coarsens non-sensitive attribute domains.Under full identification information, the two sanitization methods are equivalent.
- Attacker model: The attacker is pessimistically assumed to know table membership, non-sensitive values, and bucket assignments, while remaining uncertainty is evaluated under the random worlds assumption.All tables consistent with the bucketization are treated as equally likely absent additional knowledge.
- Background-knowledge language: The proposed background-knowledge language uses conjunctions of basic implications, and completeness shows that any predicate on tables can be represented this way given full identification information.This expressiveness permits modeling arbitrarily powerful attackers before bounding their knowledge by the number k of basic implications.
- Attacker power and limitations: The bound k measures attacker power, but basic implications can require exponentially many units for some DNF properties, creating a representation-dependent limitation.The paper notes that many natural background-knowledge properties nevertheless have succinct representations in this language.
- Disclosure and sanitization: The framework addresses dependencies between sensitive assignments across buckets and provides a polynomial-time algorithm for maximum disclosure, plus efficient minimally sanitized bucketizations below a threshold.The minimally sanitized objective is intended to preserve data utility while meeting the disclosure bound.
3. Checking And Enforcing Privacy
The paper reduces worst-case disclosure search to simple implications sharing one consequent, enabling polynomial-time computation and privacy-preserving sanitization. It also establishes monotonicity for disclosure under bucketization refinement.
- Hardness of computing disclosure risk: #P-hardness makes direct disclosure-risk computation intractable, while consistency checking is NP-complete for simple implications.
- Efficient computation: This reduction supports a polynomial-time dynamic-programming algorithm for computing maximum disclosure.The algorithm minimizes the relevant expression within buckets using MINIMIZE1, then across the bucketization using MINIMIZE2.
- A special form for maximum disclosure: Theorem 9 shows that k simple implications with a common consequent suffice to maximize disclosure over L_k^basic.The antecedents can be atoms involving people and sensitive values.
- Generality: The reduction remains valid without restrictions on the attacker’s bucketization knowledge or the underlying probability distribution.Thus, the maximizing background-knowledge form applies broadly across anonymization settings.
- Privacy enforcement: Theorem 14 states that refining bucketizations under the paper’s ordering cannot increase maximum disclosure.
4. Experiments
Experiments use the UCI Adult Database to examine maximum disclosure as bounded background knowledge increases and to compare implication-based knowledge with negated atoms. The observed implication-based risk is always at least as large, but the gap is not too large in the tested anonymization.
- Case study: 45,222 Adult Database tuples and fourteen sensitive Occupation values form the experimental case study.The analysis projects onto Age, Marital Status, Race, Gender, and Occupation.
- Disclosure versus knowledge: Maximum disclosure is evaluated for k from 0 through 12, with disclosure reaching 1 at k = 13 because fourteen sensitive values exist.
- Background-knowledge comparison: For the anonymized table, maximum disclosure for k negated atoms is always smaller than for k implications.The comparison uses suppressed non-Age attributes and Age generalized to intervals of size 20.
- Background-knowledge comparison: The difference between negated-atom and implication-based disclosure is not too large for a given k, so defending against negated atoms may require little additional anonymization.
- Entropy analysis: The entropy experiment fixes k and searches tables with each minimum bucket entropy for the least maximum disclosure under k implications.
5. Related Work
Prior privacy definitions address disclosure through query restrictions, anonymization, or limited background knowledge, but each has important limitations. Related work also studies anonymization methods and utility for specific downstream uses.
- Perfect privacy can make checking disclosure computationally hard and restrict publication of aggregate statistics.
- k-anonymity and blending in a crowd prevent unique tuple association but can still disclose sensitive information when groups are homogeneous.
- ℓ-diversity addresses limited background knowledge, while other work considers known functional dependencies and indirect inference channels.
- Anonymization approaches include generalization, suppression, noise addition, safe marginals, data swapping, and audited or perturbed query answering.
- Utility studies target association rules, distribution reconstruction, clustering, and decision-tree accuracy, while k-anonymity can require extensive suppression in high-dimensional data.
6. Conclusions
The paper formalizes worst-case disclosure when the publisher does not know the attacker's exact background knowledge. It proposes efficient analysis and sanitization based on bounded basic implications, while identifying conservativeness and broader extensions as limitations and future work.
- The paper models worst-case disclosure without assuming knowledge of the attacker's exact background knowledge.
- Basic implications form expressive knowledge units, and the worst case over all sets of k units can be computed efficiently despite specific-disclosure intractability.
- The authors combine (c, k)-safety checks with lattice-search algorithms to find bucketizations whose maximum disclosure stays below a desired threshold.
- In practice, ℓ-diversity has similar maximum disclosure to (c, k)-safety, which protects against a richer class of background knowledge.
- Using basic implications can produce conservative bucketizations when attacker knowledge requires many such units, motivating more powerful atoms and better knowledge languages.
- Future work includes probabilistic background knowledge, cost-based disclosure, and other anonymization forms such as data swapping and anonymized marginals.