A Novel Privacy Paradigm for Improving Serial Data Privacy

Ayesha Shaukat, Adeel Anjum, Saif Ur Rehman Malik, Munam Ali Shah, Carsten Maple

TL;DR

This paper introduces "Kanony," a novel privacy-preserving method for serial data, addressing vulnerabilities in existing approaches that fail to protect the "global bag" of sensitive information. Kanony enhances privacy by introducing counterfeits into the global bag, effectively mitigating correlation and critical absence attacks, crucial for dynamic datasets like health records.

What Problem Does This Paper Address?

In today's data-driven world, individuals increasingly share personal information, necessitating robust privacy measures. Serial data, where data is released continuously over time (e.g., yearly health records), presents unique challenges. Existing privacy-preserving techniques often struggle with the dynamic nature of serial data, where records are added or deleted, leading to potential privacy breaches. Specifically, the "global bag" – a collection of all sensitive information across releases – is vulnerable to attacks like "critical absence" (when a sensitive value is removed) and "correlation attacks" (linking sensitive and non-sensitive attributes). Previous methods, while offering some protection, leave this global bag exposed, especially when dealing with multiple sensitive values. This paper aims to bridge this gap by proposing a method that specifically safeguards the global bag in serial data publications.

Methods

The proposed method, Kanony, builds upon the concept of m-invariance and introduces several key techniques:

  • Segregation: Data is first vertically partitioned into sensitive (Ts) and non-sensitive (Ts) portions.
  • Sanitization: The sensitive portion is further divided into "cluster private" (Ts) and "global private" (Tg) segments. This step is repeated for each cluster to create a fully anonymized corpus.
  • Backward Perturbation (BP) and Forward Perturbation (FP): These techniques are applied to the private segments to mitigate composition and transitive composition attacks. BP adds counterfeits to the cluster private segment, while FP adds them to protect against transitive composition attacks.
  • Counterfeits in the Global Bag: This is the core innovation. To address critical absence and correlation attacks on the global bag, Kanony strategically introduces "counterfeit" data points. These counterfeits are designed to maintain the overall signature of the global bag across releases, even when sensitive data is added or removed, thus preventing adversaries from inferring sensitive information.
  • Categorization: For non-sensitive attributes, categorization is used to overcome correlation attacks.

Datasets

The paper evaluates Kanony using two real-world datasets:

  • BMS Webview-1 (B1): Contains 50,000 transactions.
  • BMS Webview-2 (B2): Contains 70,378 transactions.

These datasets are described as clickstream data from online stores and are used to simulate serial data releases over five timestamps.

Key Insights and Ideas

  • The "Global Bag" is a Critical Vulnerability: The paper highlights that existing serial data privacy methods often overlook the security of the aggregated sensitive information across all releases (the global bag), making it a prime target for sophisticated attacks.
  • Counterfeits as a Privacy Shield: The novel use of "counterfeits" in the global bag is a key insight. By strategically adding these artificial data points, the method maintains data integrity and privacy without significantly impacting data utility.
  • Dynamic Data Requires Dynamic Solutions: The paper emphasizes that static privacy approaches are insufficient for dynamic serial data. Kanony's ability to handle continuous data additions and deletions is crucial.
  • Correlation Attacks are More Pervasive Than Thought: The paper demonstrates how linking seemingly innocuous non-sensitive data with sensitive attributes can lead to significant privacy breaches, especially in serial releases.

Key Results

  • Reduced Vulnerability: Kanony significantly reduces the number of vulnerable records in the global bag compared to Sanony, especially as the sample size and number of releases increase. In experiments, Kanony detected no susceptible records in the global bag, while Sanony showed increasing vulnerability.
  • Effective Defense Against Attacks: The proposed method successfully mitigates critical absence and correlation attacks, which are major concerns in serial data privacy.
  • Marginal Perturbation Increase: While Kanony requires a slightly higher perturbation rate (due to counterfeits in the global bag), this increase is deemed acceptable for the enhanced privacy it provides.
  • Comparable Utility and Runtime: The utility loss (measured by relative error) and runtime of Kanony are comparable to Sanony, suggesting that the privacy gains do not come at an excessive cost.

Limitations and Future Work

  • Utility Trade-off: The paper acknowledges that while Kanony provides enhanced privacy, there is a slight increase in relative error, indicating a minor trade-off in data utility.
  • Future Work: The authors suggest exploring scenarios where sensitive records are not deleted but updated (e.g., a patient developing a new disease). They also aim to further improve data utility while maintaining privacy.

Summary updated

BibTeX
@inproceedings{shaukat2022novel,
  author = {Ayesha Shaukat and Adeel Anjum and Saif Ur Rehman Malik and Munam Ali Shah and Carsten Maple},
  title = {{A Novel Privacy Paradigm for Improving Serial Data Privacy}},
  booktitle = {Sensors},
  year = {2022},
  url = {https://openreview.net/forum?id=gsIRsnq6SZ},
}
Figure