Optimal Random Perturbation at Multiple Privacy Levels

Xiaokui Xiao, Yufei Tao, Minghua Chen

TL;DR

This paper introduces a novel algorithm for "multi-level random perturbation," allowing data holders to release multiple versions of a dataset, each anonymized to a different privacy level. This addresses the limitation of existing methods that only support a single privacy level, enabling more flexible and profitable data sharing while crucially preventing colluding recipients from inferring more information than the most trusted recipient.

What Problem Does This Paper Address?

Privacy-preserving data mining (PPDM) is crucial for extracting insights from sensitive datasets without compromising individual privacy. A common technique is "input perturbation," where data is intentionally altered to protect privacy. "Uniform perturbation" is a popular method within this category, offering a good balance between privacy and data utility. However, existing uniform perturbation methods only support a single level of privacy for all released data. This is problematic in real-world scenarios where a data holder might have diverse recipients with varying trust levels. For instance, a government agency might require less anonymized data for higher accuracy, while an unknown third party might need highly anonymized data. Releasing only one version of the data means either sacrificing accuracy for some recipients or over-exposing sensitive information to others. Furthermore, if multiple recipients collude and share their anonymized data, they might be able to infer more private information than they are individually entitled to. This paper tackles the challenge of providing multiple, distinct privacy levels for different recipients simultaneously, ensuring that collusion among recipients doesn't compromise privacy beyond the level guaranteed to the most trusted recipient in the colluding group.

Methods

The core contribution is a new algorithm called multi-pert. This algorithm builds upon the existing "uniform perturbation" method. The key idea is to generate a new anonymized version of a dataset for an incoming request with a specific retention probability p (which dictates the privacy level), by leveraging previously generated anonymized versions.

Here's how it works conceptually:

  • Leveraging Past Releases: Instead of re-perturbing the original dataset from scratch for each new request, multi-pert intelligently uses previously released anonymized versions. It identifies the closest "neighboring" privacy levels (i.e., the highest retention probability pi greater than p and the lowest retention probability pr less than p) among the already released versions.
  • Conditional Perturbation: Based on whether a "lower" privacy level (pr) exists, the algorithm uses either the original dataset (D) or the anonymized version corresponding to pr (D) to generate the new version.
  • Probabilistic Generation: The new anonymized value is generated by a coin toss with carefully calculated probabilities. These probabilities are derived to ensure two crucial properties:
  • Collusion is Useless: If a group of recipients colludes, their combined knowledge about a sensitive value will be no more than what the most trusted recipient in that group already knows. This is achieved by ensuring the probability distribution of the inferred sensitive value, given the colluded data, is identical to the distribution given only the data from the most trusted recipient.
  • Equivalence to Uniform Perturbation: Each anonymized version generated by multi-pert is statistically indistinguishable from a version produced by the standard uniform perturbation algorithm with the requested retention probability p. This allows recipients to use existing data mining tools designed for uniform perturbation directly.

The algorithm is designed to be incremental and online, meaning it can handle new requests at any time without needing to know future requests or their privacy levels in advance.

Datasets

The paper uses the Adult dataset for experimental evaluation. This is a publicly available dataset commonly used in privacy research. They specifically use the "Salary" and "Occupation" attributes as sensitive values for their experiments, with domain sizes of 50 and 27, respectively. They also use synthetic uniform and Gaussian distributions over a domain of size 50 for testing.

Key Insights and Ideas

  • The Power of "Neighboring" Privacy Levels: The core insight is that to achieve multi-level privacy without compromising collusion resistance, you don't need to re-process the original data from scratch for every new request. Instead, intelligently combining information from the closest previously released privacy levels is sufficient.
  • Collusion is a "Most Trusted" Problem: The paper formalizes the idea that the privacy guarantee against collusion should be capped by the privacy level of the most trusted recipient involved in the collusion. This is a powerful simplification that makes the problem tractable.
  • Statistical Equivalence is Key: Ensuring that each generated anonymized version is statistically equivalent to a standard uniform perturbation output is crucial for practical usability. This allows existing PPDM tools to work seamlessly with the new multi-level system.
  • Space and Time Efficiency: The proposed algorithm is not just theoretically sound but also practically efficient, achieving asymptotically optimal space and time complexities, which is vital for handling large datasets.

Key Results

  • Theoretical Guarantees: The paper provides formal proofs that the multi-pert algorithm achieves both "collusion is useless" and "equivalence to uniform perturbation" properties.
  • Experimental Validation:
    • Experiments on the Adult dataset and synthetic data demonstrate that the algorithm effectively thwarts collusion, with empirical results closely matching theoretical predictions.
  • The output of multi-pert was shown to be statistically equivalent to standard uniform perturbation across various distributions and privacy levels.
  • Failure of Independent Perturbation: A key experimental finding is that simply generating independent perturbed versions for each recipient fails dramatically when the number of recipients grows. The average reconstruction probability (how likely it is for colluding recipients to reveal the original data) quickly surges to nearly 1 after only about 30 releases, highlighting the necessity of the proposed multi-pert approach. In contrast, multi-pert maintained an average reconstruction probability of around 30% even with many releases.
  • Efficiency: The algorithm achieves O(n + m) expected space complexity and O(n + log m) expected time complexity, where n is the dataset size and m is the number of releases. This is optimal for large datasets where n >> m. The average size of the history(t) structure (used for storing perturbed values for a tuple t) is bounded by a small constant, independent of m.

Limitations and Future Work

  • Tuple Correlations: The paper acknowledges that its approach, like most input perturbation methods, assumes adversaries have no prior knowledge of correlations among tuples. If such correlations are known, no input perturbation algorithm can guarantee strong privacy without significantly impacting utility. Addressing arbitrary tuple correlations remains an open challenge.
  • Pseudo-Randomness: While the theoretical proofs rely on true randomness, the implementation uses pseudo-random generators. The paper empirically verifies that the algorithm remains effective even with pseudo-randomness, but this is an area where theoretical guarantees might be weaker.
  • Generalization to Other Methods: The authors suggest that the core idea of multi-level perturbation could potentially be adapted to other perturbation methods (e.g., non-uniform perturbation, noise adding), but note that these might not achieve the same strong privacy guarantees as uniform perturbation.
  • Practical Parameter Tuning: While the algorithm is theoretically robust, determining optimal retention probabilities (p) for different recipients in practice might require further investigation.

Summary updated

BibTeX
@article{xiao2009optimal,
  author = {Xiaokui Xiao and Yufei Tao and Minghua Chen},
  title = {{Optimal Random Perturbation at Multiple Privacy Levels}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  url = {https://openreview.net/forum?id=KdCKZbXHwRY},
}
Figure