Abstract
Privacy definitions like Differential Privacy are often treated as mathematical "black boxes," making it difficult to understand the specific semantic protections they offer. This paper introduces a general framework to bridge this gap by representing algorithms as matrices and extracting a geometric object called a row cone. This approach allows for the derivation of formal bounds on how much an attacker's beliefs can change, revealing hidden protections like "parity" and enabling systematic relaxation of privacy constraints.
Introduction
The landscape of data privacy is populated by numerous syntactic definitions—mathematical constraints on algorithms—ranging from k-anonymity to Differential Privacy. However, a significant gap exists between these definitions and the semantic guarantees they provide: what an attacker actually learns about sensitive data. Organizations releasing sanitized data need to know precisely which information is protected and whether certain protections are unnecessarily strict, thereby reducing data utility. This research provides a "translation layer" to convert abstract mathematical constraints into intuitive semantic statements.
Methodology: The Geometry of Privacy
The proposed framework utilizes linear algebra and convex geometry to analyze privacy mechanisms through a four-step process:
- Algorithmic Representation: Privacy-preserving algorithms are modeled as matrices where columns represent input databases and rows represent possible outputs. Each entry is the probability of a specific output given a specific input.
- Consistent Normal Form (CNF): The framework expands a privacy definition to include all algorithms that should be considered "trusted" under that definition, based on axioms of post-processing and convexity.
- The Row Cone: The core of the framework is the extraction of the "row cone" (illustrated below)—a convex geometric shape in high-dimensional space. This cone represents the set of all possible transformations from an attacker’s prior beliefs to their posterior beliefs.
- Guarantee Extraction: The boundaries of the row cone are defined by linear inequalities. By interpreting the coefficients of these inequalities as probabilities, the authors generate formal semantic statements regarding the limits of inference.
Key Insights and Results
The geometric perspective reveals that privacy is essentially a shape. Understanding the row cone of a definition provides a complete picture of its protective capabilities.
The Parity Trap
A significant finding is that many popular techniques, such as Randomized Response and FRAPP, provide exceptionally strong protection for the parity of a dataset (e.g., whether the sum of specific bits is even or odd). Because parity is rarely the primary sensitive attribute, these definitions may be "too strong" in ways that degrade data utility without providing meaningful real-world protection.
Differential Privacy as Relaxation
The framework demonstrates that Differential Privacy can be viewed as a natural relaxation of Randomized Response. By simplifying the linear inequalities defining the row cone, the focus shifts from protecting complex properties like parity to protecting individual records.
Empirical Applications
The framework was applied to several mathematical models:
- Binary and Tuple Domains: Derived previously unknown semantic guarantees for Randomized Response and generalizations like FRAPP/PRAM, proving their inherent protection of parity.
- Additive Noise: Using Fourier series transforms, the authors derived row cones for mechanisms adding integer-valued noise, such as Skellam or Negative Binomial noise.
- Automated Relaxation: Tools like Fourier-Motzkin elimination were used to systematically weaken definitions, optimizing the balance between privacy and utility.
Limitations and Future Directions
While powerful, the framework currently requires significant mathematical expertise to implement. Future work aims to automate the extraction process. Additionally, the current model focuses on "always-hold" guarantees and assumes a computationally unbounded Bayesian attacker. Extending the framework to handle probabilistic relaxations (like $(\epsilon, \delta)$-Differential Privacy) and computationally bounded attackers remains an open challenge.
Summary updated