Privacy-Guaranteed Two-Agent Interactions Using Information-Theoretic Mechanisms

Bahman Moraffah, Lalitha Sankar

TL;DR

This paper tackles the challenge of two agents sharing correlated data while protecting sensitive private information. They introduce a novel framework for multi-round interactions, showing how to balance data utility with privacy guarantees using information-theoretic tools. A key finding is that interaction can sometimes reduce privacy leakage compared to a single-round exchange, especially under log-loss distortion.

What Problem Does This Paper Address?

In many real-world scenarios, such as distributed systems or sensor networks, multiple entities need to share data to achieve a common goal (e.g., state estimation). However, this data often contains both public features (useful for the task) and private features (sensitive information that must be protected). The challenge is to design communication protocols that allow for effective sharing of public data while minimizing the leakage of private data to the other agent. Traditional privacy definitions like differential privacy, which focus on individual data points, may not be sufficient for this scenario where the threat is primarily about inference of correlated private features. This paper addresses this by formulating a multi-round interactive data sharing problem with information-theoretic privacy constraints, aiming to find the optimal trade-off between data utility and privacy leakage.

Methods

The authors propose a K-round interactive privacy mechanism, where agents A and B alternately share information over K rounds. Each round involves a probabilistic mapping (mechanism) that transforms public data into a revealed sequence, aiming to achieve a certain utility (distortion) while bounding the leakage of private data. The core of their approach involves:

  • Information-Theoretic Formulation: Using mutual information to quantify leakage and distortion.
  • Distortion-Leakage Region: Determining the set of all achievable pairs of distortion and leakage for both agents.
  • Composition Theorem: Showing that privacy budgets can be composed across multiple rounds without loss.
  • Log-Loss Distortion: Focusing on log-loss as a relevant utility metric for machine learning and soft decision scenarios.
  • Interactive Information Bottleneck (IB) Analogy: Framing the problem as an interactive version of the IB problem.
  • Agglomerative Interactive Privacy Algorithm: A novel algorithm, extending the agglomerative IB algorithm, to find provably locally optimal solutions for the non-convex optimization problem.
  • Merge-and-Search Technique: A specific technique developed to generalize the agglomerative algorithm to multivariate settings and multi-round interactions.

Datasets

Not discussed in the paper. The paper uses synthetic data distributions (discrete, Gaussian) for theoretical analysis and illustration.

Key Insights and Ideas

  • Interaction Can Reduce Leakage: Counter-intuitively, sharing data over multiple rounds can sometimes lead to less privacy leakage for a given level of data utility, especially when using log-loss distortion. This is a significant finding as one might expect more interaction to always increase leakage.
  • Composition of Privacy Budgets: The proposed mechanisms allow for a clean "composition" of privacy budgets across rounds, meaning the total privacy cost is simply the sum of individual round costs, without any loss or overhead. This is crucial for designing practical, multi-stage privacy protocols.
  • Dual to Information Bottleneck: The problem is shown to be a dual of the information bottleneck problem, where the roles of what to reveal (public data) and what to hide (private data) are swapped. This connection allows leveraging existing techniques from IB research.
  • Log-Loss Relevance: The focus on log-loss distortion highlights its importance in scenarios involving soft decisions or probabilistic reconstructions, common in machine learning.
  • Optimality of One-Shot for Gaussian Sources: For Gaussian sources, a single round of interaction is sufficient to achieve the optimal utility-privacy trade-off, simplifying the problem significantly in this important case.

Key Results

  • Characterization of Distortion-Leakage Region: The paper provides a formal characterization of the achievable distortion-leakage region for K-round interactive mechanisms.
  • Conditions for Leakage Reduction: Conditions are derived under which interaction demonstrably reduces net leakage.
  • Optimality for Gaussian Sources: For jointly Gaussian sources, one-shot privacy mechanisms are shown to be optimal for both mean-square error and log-loss distortions.
  • Illustrative Example: An example using binary sources demonstrates that interaction can indeed reduce leakage under log-loss distortion.
  • Algorithm for Local Optimality: A new agglomerative interactive privacy algorithm is introduced, which finds provably locally optimal solutions for the complex optimization problem.

Limitations and Future Work

  • Local Optimality: The proposed algorithm guarantees locally optimal solutions, not necessarily global optima, due to the non-convex nature of the problem.
  • General Source Distributions: While the paper provides conditions for interaction helping, precisely characterizing the rate of convergence to the infinite-round limit for arbitrary source distributions remains challenging.
  • Future Work: The authors suggest extending the work to:
  • Multiple agents.
  • Data-driven empirical and approximate approaches.
  • Evaluating leakage against different statistical inference attacks.
  • Modeling canonical mechanisms for various source classes.

Summary updated

Abstract

This paper introduces a multi-round interaction problem with privacy constraints between two agents that observe correlated data. The data are assumed to have both public and private features, and the goal of the interaction is to share the public data subject to utility constraints (bounds on the distortion of public feature) while ensuring bounds on the information leakage of the private data at the other agent. The agents alternately share data with one another for a total of K rounds such that each agent initiates sharing over K/2 rounds. The interactions are modeled as a collection of K random mechanisms (mappings), one for each round. The goal is to jointly design the K private mechanisms to determine the set of all achievable distortion-leakage pairs at each agent. Arguing that a mutual information-based leakage metric can be appropriate for streaming data settings, this paper: 1) determines the set of all achievable distortion-leakage tuples; 2) shows that the K mechanisms allow for precisely composing the total privacy budget over K rounds without loss; and 3) develops conditions under which interaction reduces the net leakage at both agents and illustrates it for a specific class of sources. The paper then focuses on log-loss distortion to better understand the effect on leakage of using a commonly used utility metric in learning theory. The resulting interaction problem leads to a non-convex sum-leakage-distortion optimization problem that can be viewed as an interactive version of the information bottleneck problem. A new merge-and-search algorithm that extends the classical agglomerative information bottleneck algorithm to the interactive setting is introduced to determine a provable locally optimal solution. Finally, the benefit of interaction under log-loss is illustrated for specific source classes, and the optimality of one-shot is proved for Gaussian sources under both mean-square and log-loss distortions constraints.
BibTeX
@article{moraffah2017privacy,
  author = {Bahman Moraffah and Lalitha Sankar},
  title = {{Privacy-Guaranteed Two-Agent Interactions Using Information-Theoretic Mechanisms}},
  journal = {IEEE Trans. Information Forensics and Security},
  year = {2017},
  url = {https://openreview.net/forum?id=jQy9adR8INN},
}
Figure