PaperlayerView exact revision on arXiv

Source-linked AI summary

Composition Attacks and Auxiliary Information in Data Privacy

Srivatsava Ranjit Ganta, Shiva Prasad Kasiviswanathan, Adam Smith

arXiv:0803.0032v2cs.DBcs.CR

TL;DR

The paper asks how privacy can be reasoned about when adversaries possess rich auxiliary information and organizations independently release anonymized data about overlapping populations. It studies composition attacks against existing schemes and proves that differential privacy and important relaxations resist arbitrary side information. These results distinguish vulnerable partition-based methods from guarantees that support modular anonymization design.

  • Problem

    Existing privacy reasoning must account for auxiliary information and independent anonymized releases about overlapping populations, but limited-auxiliary-information models do not capture this setting.

  • Method

    The paper introduces composition attacks, empirically evaluates intersection attacks against partition-based schemes, and formulates and proves resistance to arbitrary side information for differential privacy relaxations.

  • Results

    Partition-based schemes including k-anonymity and variants are vulnerable to composition attacks, whereas differential privacy and two important relaxations resist arbitrary side information.

  • Takeaways & Limitations

    Resistance to arbitrary side information enables stand-alone, modular design of anonymization schemes without explicitly tracking other releases.

  • Takeaways & Limitations

    Independent releases fall outside the models proposed for limited auxiliary information, and a natural total-variation relaxation of differential privacy fails completely to protect privacy.

Abstract

from arXiv · show

Privacy is an increasingly important aspect of data publishing. Reasoning about privacy, however, is fraught with pitfalls. One of the most significant is the auxiliary information (also called external knowledge, background knowledge, or side information) that an adversary gleans from other channels such as the web, public records, or domain knowledge. This paper explores how one can reason about privacy in the face of rich, realistic sources of auxiliary information. Specifically, we investigate the effectiveness of current anonymization schemes in preserving privacy when multiple organizations independently release anonymized data about overlapping populations. 1. We investigate composition attacks, in which an adversary uses independent anonymized releases to breach privacy. We explain why recently proposed models of limited auxiliary information fail to capture composition attacks. Our experiments demonstrate that even a simple instance of a composition attack can breach privacy in practice, for a large class of currently proposed techniques. The class includes k-anonymity and several recent variants. 2. On a more positive note, certain randomization-based notions of privacy (such as differential privacy) provably resist composition attacks and, in fact, the use of arbitrary side information. This resistance enables stand-alone design of anonymization schemes, without the need for explicitly keeping track of other releases. We provide a precise formulation of this property, and prove that an important class of relaxations of differential privacy also satisfy the property. This significantly enlarges the class of protocols known to enable modular design.

1. INTRODUCTION

The paper examines how auxiliary information and independent anonymized releases can undermine privacy, then contrasts vulnerable partition-based schemes with randomization-based guarantees that resist arbitrary side information.

  • Motivation and problem: Composition attacks exploit independently released anonymized data about overlapping populations to breach privacy.The paper frames these attacks as a realistic vulnerability that becomes harder to manage as more organizations publish related summaries.
  • Attacks on partition-based schemes: Partition-based schemes, including k-anonymity and recent variants, publish exact group statistics and can support intersection attacks.The attack uses exact sensitive-value disclosure and locatability to intersect possible sensitive values across releases.
  • Attacks on partition-based schemes: In a hospital example, auxiliary knowledge locates an individual in two anonymized tables, whose only shared disease value reveals AIDS.The tables use independent k-anonymizations with k = 4 and k = 6, while the sensitive attribute remains untouched.
  • Randomization-based guarantees: Independent releases fall outside the limited-auxiliary-information models discussed, while differential privacy composes even with arbitrary external knowledge.The paper gives a Bayesian formulation of this resistance and proves that two important relaxations of differential privacy also satisfy it.

2. PARTITION-BASED SCHEMES

Partition-based schemes group individuals into equivalence classes, generalize non-sensitive attributes, and leave sensitive values unchanged. The intersection attack exploits exact sensitive-value disclosure and locatability across independent releases to reduce effective anonymity.

  • Partition-based schemes cluster individuals into groups and recode non-sensitive values so each group forms a quasi-identifier equivalence class.
  • k-anonymity requires every equivalence class to contain at least k individuals.
  • Locatability lets an adversary identify an individual’s group from quasi-identifier values using a k-anonymized release.
  • An intersection attack combines sensitive-value sets from an individual’s groups across independent releases.
  • Effective anonymity is the number of distinct sensitive values in an individual’s partition, rather than the release’s promised minimum partition size.
  • The vulnerable population comprises overlapping individuals whose effective anonymity decreases after intersection, with confidence defined as the reciprocal of posterior effective anonymity.

3. EXPERIMENTAL RESULTS

The experimental study quantifies the severity of intersection attacks on existing anonymization schemes, addressing a gap in prior work on auxiliary independent releases.

  • The study quantifies intersection-attack severity because prior studies did not address attacks from auxiliary independent releases or quantify their severity.

3.1 Setup

The experiments apply partition-based anonymization techniques to two census databases with independently anonymized overlapping subsets. The intersection attack is then run on the resulting releases.

  • The study evaluates k-anonymity, entropy ℓ-diversity, and t-closeness using partition-based anonymization techniques.
  • The experiments use the Adult and IPUMS census databases, both drawn from the UCI Machine Learning repository.
  • The Adult database contains 30162 individual records after preparation for the experiments.
  • For each database, two subsets are randomly sampled without replacement, their overlap is fixed at P = 5000, and the subsets are anonymized independently.

3.2 Severity of the Attack

Intersection attacks can produce perfect or partial breaches by narrowing sensitive-value sets across releases. The experiments show substantial vulnerability, especially when partial disclosure requires only modest confidence.

  • 3.2 Severity of the Attack: A perfect breach occurs when the intersection leaves exactly one possible sensitive value, corresponding to 100% adversarial confidence.
  • 3.2 Severity of the Attack: The experiments compare Mondrian, microaggregation, and mixed anonymization scenarios, using equal k values for both subsets.
  • 3.2.1 Perfect Breach: 12% of the Adult population was vulnerable to a perfect breach at k1 = k2 = 5, compared with around 60% for IPUMS.
  • 3.2.1 Perfect Breach: Increasing k reduces perfect-breach vulnerability because larger partitions produce larger intersection sets and make singleton intersections less likely.
  • 3.2.2 Partial Breach: A partial breach narrows the sensitive-value possibilities to a smaller set rather than a single value, with confidence determined by that set’s size.
  • 3.2.2 Partial Breach: At 25% confidence and k1 = k2 = 5, around 95% of IPUMS and more than 60% of Adult were vulnerable under Mondrian anonymization.

3.3 Drop in Anonymity

The intersection attack substantially reduces effective anonymity: the sensitive-value sets become much smaller than the partitions released by partitioning-based schemes. Presumed k-anonymity can therefore overstate the protection actually provided.

  • Effective anonymity is the number of distinct sensitive values in an individual’s partition, rather than the partition’s full size.
  • In IPUMS, k = 5 produced average partitions close to 40, far above the minimum k required by k-anonymity.Generalization-based hierarchies produced partitions much larger than the minimum required value.
  • The effective anonymity was much lower than partition size for both Adult and IPUMS overlapping populations.
  • The attack measures anonymity loss by comparing average effective prior anonymity before intersection with average effective posterior anonymity afterward.
  • Figures 1 and 2 report perfect and partial breaches of the Adult and IPUMS databases under the intersection attack.

3.4 ℓ-diversity and t-closeness

ℓ-diversity and t-closeness still permit considerable intersection breaches, despite appearing stronger than k-anonymity. They also produce substantially larger partitions and consequently greater information loss.

  • Figure 4 measures the average effective-anonymity drop caused by the intersection attack in the Adult and IPUMS databases.
  • ℓ-diversity and t-closeness still lead to considerable breaches under intersection attacks.The paper evaluates partial breaches across adversary confidence levels for Adult and IPUMS databases.
  • For IPUMS with k = 10, average partition size was 45 for k-anonymity, close to 450 for ℓ-diversity with ℓ = 5, and close to 1300 for t-closeness with t = 0.4.
  • The intersection of two well-diverse sensitive-value sets is not guaranteed to remain well diverse, explaining the vulnerability of ℓ-diversity.

3.5 Role of Sensitive Attribute Domain

The sensitive-attribute domain may influence intersection-attack severity: IPUMS uses domains of 14 values for Adult’s Occupation and 247 for IPUMS’s Occupation. The paper compares alternative IPUMS attributes with domains of 145 and 471.

  • The Adult Occupation domain contains 14 values, whereas the IPUMS Occupation domain contains 247.The paper identifies sensitive-attribute domain size as one plausible reason the attack is more severe for IPUMS.
  • As the number of possible sensitive values increases, intersecting two different sensitive-value sets can produce a less diverse set.
  • The experiments replace IPUMS Occupation with Industry and Income, whose domains contain 145 and 471 values, respectively.The resulting database versions retain the original non-sensitive attributes.

3.6 Number of Databases

More overlapping anonymized releases make intersection attacks more severe, especially when k is small. For larger k, additional releases provide less benefit because partitions are already large.

  • The study examines intersection attacks using more than two anonymized releases over a fixed overlapping IPUMS population.
  • Figures 8(a) and 8(b) examine vulnerable-population percentage and average effective-anonymity drop as the number of releases changes.
  • For larger k, additional releases produce no significant increase because the partitions are already large enough to limit further attack benefit.

4. DIFFERENTIAL PRIVACY

This section formulates resistance to arbitrary side information using Bayesian posteriors and shows that differential privacy and important relaxations imply semantic privacy. It also describes the proof strategy and the resulting parameter guarantees.

  • Differential privacy: Differential privacy requires neighboring databases to induce output distributions whose event probabilities differ by at most a multiplicative factor, with relaxed definitions adding δ.The strict definition uses e^ϵ; the relaxed definition adds δ.
  • Bayesian formulation: Arbitrary external knowledge is modeled by a prior distribution on databases, while conclusions are represented by the posterior after observing a transcript.The adversary updates beliefs using Bayes’ rule.
  • Semantic privacy: Privacy is breached when an adversary’s conclusions differ depending on whether an individual’s data was included, measured using statistical difference between posteriors.The analysis compares real and hypothetical games using D and D−i.
  • Main result: (ϵ, δ)-differential privacy implies (ϵ′, δ′)-semantic privacy, with ϵ′ = e3ϵ −1 + 2 in the stated main theorem.The paper states that the result extends the Dwork–McSherry implication to relaxed differential privacy.
  • Scope and boundary: The result covers several relaxations of differential privacy, but replacing multiplicative distance with total variation distance can fail to protect privacy.The paper gives a sanitizer that publishes one person’s complete identified record as a counterexample.
  • Proof strategy: The main proof uses indistinguishability of randomized outputs to establish indistinguishability of the corresponding posterior distributions after observing a transcript.Lemma 18 supplies the posterior-transfer step used in the main theorems.

5. CONCLUDING REMARKS

The paper concludes that composition attacks expose vulnerabilities in several partition-based anonymization schemes, while several differential-privacy relaxations resist arbitrary side information. It identifies whether randomness is necessary for such resistance and other composition settings as open questions.

  • Findings: Experiments indicate that k-anonymity and several partition-based variants are vulnerable to composition attacks involving independent releases about overlapping populations.The conclusion describes these schemes as currently proposed partition-based anonymization methods.
  • Findings: The paper gives a precise formulation of resistance to arbitrary side information and shows that several relaxations of differential privacy satisfy it.This property supports reasoning about privacy across independent releases.
  • Open questions: Whether randomness in anonymization is necessary to resist complex side information remains an open question, alongside composition attacks involving overlapping contingency tables.The authors identify both as directions for future investigation.
Loading 0803.0032v2…