Properties of Effective Information Anonymity Regulations

Aloni Cohen, Micah Altman, Francesca Falzon, Evangelina Anna Markatou, Kobbi NissimarXiv 2024 · OpenReview

Abstract

A firm seeks to analyze a dataset and release the results while complying with regulations that forbid the release of the raw data. These regulations often impose conditions on the release of results to protect individual privacy. In this paper, we develop a set of technical requirements for anonymization rules and related regulations. By situating guiding principles within an abstract model of data processing, we evaluate competing interpretations of regulatory requirements, such as those found in the EU's General Data Protection Regulation (GDPR).

Introduction

Privacy law and data science often speak different languages. While regulators and courts use terms like "anonymization," "singling out," and "linkability" to determine the legality of data releases, these concepts frequently lack formal technical definitions. This ambiguity creates a significant gap: regulations may be so restrictive that they prevent any useful data analysis (the "empty release" problem) or so permissive that they fail to protect individuals against modern privacy attacks.

This research provides a rigorous bridge between these domains. By formalizing what it means for a regulation to be "well-tailored," we identify the properties that an effective information anonymity regulation should satisfy and evaluate whether common interpretations of the GDPR are technically consistent.

A Framework for Evaluation: Six Guiding Principles

The foundation of this analysis rests on six guiding principles for anonymization, derived from prior work to ensure that privacy protections are robust and logically sound:

  1. Process Protection: Privacy is a property of the algorithm (the process), not just the resulting output file.
  2. Format Neutrality: Rules must apply consistently regardless of whether the output is a spreadsheet, a graph, or a machine-learning model.
  3. Inclusion-Based Protection: The focus should be on whether an individual’s presence in the dataset significantly altered the outcome.
  4. Composition Awareness: Regulations must account for the cumulative risk when multiple "anonymous" datasets are combined.
  5. Transparency: Protection should not rely on "security by obscurity"; the algorithm itself should be public.
  6. Protective Assumptions: Regulations should minimize assumptions about the specific knowledge an attacker might possess.

Technical Requirements for Regulations

From these principles, we derive formal requirements for the "set of allowed mechanisms." These requirements serve as a yardstick for evaluating existing and proposed regulations:

  • Non-Triviality and NJER (Not Just the Empty Release): A regulation is ineffective if the only way to comply is to release nothing at all. We evaluate whether a rule allows for meaningful data utility.
  • Post-Processing: If a piece of data is deemed safe to release, further processing that data (without re-accessing the original private source) should not suddenly make it "unsafe."
  • Parallel Composition: If two independent parts of a dataset are processed separately and safely, their combined release should also be safe.

Evaluating Regulatory Concepts

Using this framework, we evaluated several prevailing interpretations of the GDPR. The results reveal significant logical inconsistencies in traditional regulatory approaches.

The Inference Paradox

Strict "inference protection"—the idea that an attacker should learn nothing new about an individual—is a common goal in policy. However, we demonstrate that this violates the NJER property. If a study reveals that "smoking causes cancer," an attacker learns something new about every smoker in the world. If a law forbids such inferences, it effectively forbids all scientific progress.

The Failure of K-Anonymity

K-anonymity, a popular technique for data de-identification, fails the Composition Awareness test. While a single k-anonymous dataset might appear safe, combining two different k-anonymous versions of the same data can allow for the total reconstruction of individual records. This fragility makes it an unreliable standard for modern data environments.

Process vs. Product in Linkability

A key insight of this work is the violation of the Process Principle by common definitions of "linkability" (such as "double matching"). We show that two different algorithms can produce identical outputs, yet one might be legally "anonymous" while the other is not, based solely on internal steps like row shuffling. This focus on the "product" rather than the "process" is logically inconsistent.

Singling Out and Predicate Singling-Out (PSO)

The common interpretation of "singling out" as "isolation" is often impossible to prevent entirely, violating the ALTER (At Least the Empty Release) property. We analyze Predicate Singling-Out (PSO), a newer concept that proves more robust than traditional isolation but still faces challenges with Parallel Composition.

Conclusion

Our analysis suggests that Differential Privacy (DP) remains the only major framework that consistently satisfies these core principles, particularly Process Protection and Inclusion-Based Protection. While the properties identified in this paper are a starting point, they highlight the urgent need for regulations that are technically grounded. Future work must address the transition from binary "allowed/disallowed" rules to nuanced risk measurements and determine how to implement these technical requirements into flexible legal frameworks without losing the necessary discretion for regulators.

Summary updated

Abstract

A firm seeks to analyze a dataset and to release the results. The dataset contains information about individual people, and the firm is subject to some regulation that forbids the release of the dataset itself. The regulation also imposes conditions on the release of the results. What properties should the regulation satisfy? We restrict our attention to regulations tailored to controlling the downstream effects of the release specifically on the individuals to whom the data relate. A particular example of interest is an anonymization rule, where a data protection regulation limiting the disclosure of personally identifiable information does not restrict the distribution of data that has been sufficiently anonymized. In this paper, we develop a set of technical requirements for anonymization rules and related regulations. The requirements are derived by situating within a simple abstract model of data processing a set of guiding general principles put forth in prior work. We describe an approach to evaluating such regulations using these requirements -- thus enabling the application of the general principles for the design of mechanisms. As an exemplar, we evaluate competing interpretations of regulatory requirements from the EU's General Data Protection Regulation.
BibTeX
@misc{cohen2024properties,
  author = {Aloni Cohen and Micah Altman and Francesca Falzon and Evangelina Anna Markatou and Kobbi Nissim},
  title = {{Properties of Effective Information Anonymity Regulations}},
  year = {2024},
  eprint = {2408.14740},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.14740},
}
Figure