Privacy preserving serial data publishing by role composition

Yingyi Bu, Ada Wai-Chee Fu, Raymond Chi-Wing Wong, Lei Chen, Jiuyong Li

TL;DR

This paper introduces HD-composition, a novel method for protecting individual privacy when publishing dynamic datasets over time. It addresses the limitations of existing methods by handling changing attributes, permanent sensitive values (like chronic diseases), and dynamic external data sources, ensuring privacy even with sophisticated adversaries.

What Problem Does This Paper Address?

Publishing data about individuals, even after anonymization, poses a privacy risk. This is especially true for dynamic datasets that change over time, where new data is added, existing data is updated, or records are deleted. Traditional anonymization techniques, like k-anonymity and l-diversity, often assume static data and can fail when attributes change or when certain sensitive values are permanent (e.g., a diagnosis of HIV). Furthermore, adversaries might leverage external, dynamic data sources (like voter registration lists) to re-identify individuals. Existing methods for dynamic data publishing struggle with these complexities, particularly the combination of changing attributes, permanent sensitive values, and dynamic external information.

Methods

The core of the proposed solution is HD-composition, a generalization technique that employs a "role-based partition" and a "cohort-based partition."

  • Roles: Individuals are assigned roles as "holders" (possessing a permanent sensitive value) or "decoys" (individuals used to mask holders).
  • Role-Based Partition: For every permanent sensitive value, the method ensures that for each holder, there are l-1 decoys within the same anonymized group. This directly enforces a privacy threshold.
  • Cohort-Based Partition: To prevent linkage exclusion attacks (where an adversary deduces an individual's status by eliminating possibilities), individuals are grouped into "cohorts" based on their roles and sensitive values. This ensures that decoys from the same cohort are not grouped together in a way that reveals their true status.
  • Containers and S-Cliques: The method uses "containers" to manage individuals and their roles within specific regions. "S-cliques" are formed from these containers to create anonymized groups that satisfy both role-based and cohort-based partitioning principles.
  • Trusted Publisher Assumption: The approach relies on the assumption that the data publisher is trusted and correctly implements the anonymization algorithm. Interestingly, making the algorithm known to the public can enhance privacy by allowing for a more accurate analysis of privacy risks.
  • Refinements: The method is further refined to handle changes in quasi-identifier (QID) values and to account for adversaries with limited "participation knowledge" (knowing the presence or absence of a small number of individuals).

Datasets

The authors used a real hospital database called CADRMP for their experiments. The database consists of several tables, with "Reports" serving as the dynamic voter registration list and "Reactions" containing patient information and disease attributes. They created dynamic microdata table series and registration list series from this database to simulate real-world scenarios.

Key Insights and Ideas

  • Permanent Sensitive Values are a Game Changer: The presence of permanent sensitive values (like chronic diseases) fundamentally complicates privacy preservation in dynamic settings, making traditional methods insufficient.
  • Decoys are Crucial, but Need Structure: Simply having decoys isn't enough; their arrangement and roles must be carefully managed to prevent adversaries from deducing sensitive information through elimination.
  • Cohort-Based Partitioning Prevents Linkage Exclusion: The novel cohort-based partitioning is key to preventing adversaries from inferring an individual's status by ruling out possibilities, a common attack vector.
  • Transparency Can Enhance Privacy: Counter-intuitively, revealing the anonymization mechanism (HD-composition) to the public can actually strengthen privacy by enabling a more accurate assessment of risks.
  • Dynamic External Data is a Real Threat: The paper explicitly addresses the challenge posed by dynamic external datasets (like voter lists) that can be joined with published data to re-identify individuals.

Key Results

  • Effectiveness: HD-composition successfully protects against privacy breaches caused by dynamic data, permanent sensitive values, and dynamic external lists, achieving l-scarcity (a privacy guarantee).
  • Perturbation Rate: The rate of sensitive value perturbation required by HD-composition was found to be very low (around 0.02%) in experiments, indicating minimal impact on data utility.
  • Data Utility: The utility of published data, measured by query error, remained high and did not degrade significantly with increased publishing rounds or container sizes, performing comparably to l-diversity and m-invariance.
  • Computation Cost: The algorithm's computation cost was found to be efficient, with larger l values leading to faster anonymization. The cost was also relatively insensitive to container size.
  • Participation Knowledge: The method's performance was not drastically affected by varying levels of adversary participation knowledge, demonstrating robustness.

Limitations and Future Work

  • Trusted Publisher Assumption: The method relies on a trusted data publisher to correctly implement the anonymization algorithm. If the publisher is malicious or makes errors, privacy guarantees may be compromised.
  • Pinned Individuals: In certain edge cases (e.g., when a buddy abundance assumption is not met), individuals might be "pinned" as decoys, requiring suppression of their sensitive values. While this doesn't necessarily lead to extra privacy breaches, it's a limitation.
  • Future Work: The authors suggest extending HD-composition to guard against various kinds of background knowledge and exploring novel techniques to improve data utility in serial publishing. They also mention the possibility of adapting existing anonymization algorithms for HD-composition.

Summary updated

BibTeX
@article{bu2008privacy,
  author = {Yingyi Bu and Ada Wai-Chee Fu and Raymond Chi-Wing Wong and Lei Chen and Jiuyong Li},
  title = {{Privacy preserving serial data publishing by role composition}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  doi = {10.14778/1453856.1453948},
}
Figure