Privacy Games: Optimal Protection Mechanism Design for Bayesian and Differential Privacy

Reza Shokri

Abstract

In the era of pervasive data collection, users face a persistent conflict between sharing personal information for service utility and maintaining privacy. This paper presents a game-theoretic approach to optimal user-centric data obfuscation. By framing the interaction between a data-sharing user and an adaptive adversary as a Stackelberg game, the authors derive a mechanism that minimizes utility loss while satisfying both Differential Privacy (DP) and Distortion Privacy constraints. Experimental results using real-world location traces demonstrate that this "double shield" approach offers superior robustness against sophisticated inference attacks without incurring additional utility costs beyond those imposed by individual privacy metrics.

Introduction

Modern location-based services (LBS) require users to share precise coordinates to function effectively, creating a significant privacy risk. Traditionally, privacy has been measured using two distinct paradigms: Differential Privacy (DP), which ensures indistinguishability between similar secrets, and Distortion Privacy, which focuses on maximizing the adversary's inference error.

However, DP often ignores the adversary's prior knowledge, while Distortion Privacy can be fragile if the adversary's strategy deviates from expectations. This research addresses these gaps by proposing a unified framework that optimizes utility under a "double shield" of both DP and Distortion Privacy, specifically designed to withstand adaptive adversaries who change their strategy to beat the defense.

Methodology

The core of the proposed framework is a Stackelberg game where the user acts as the leader and the adversary as the follower. The user chooses an obfuscation mechanism $p(o|s)$—a conditional probability distribution that maps a secret $s$ to an observable $o$—to minimize expected utility cost. The adversary, observing $o$, selects an optimal inference strategy $q(\hat{s}|o)$ to minimize their own estimation error, thereby maximizing the user's privacy.

The system model of the privacy game, illustrating the flow from secret to estimate and the associated costs and privacy metrics.

The authors demonstrate that this complex interaction can be formulated as a Linear Program (LP). By treating privacy requirements as constraints within the LP, the user can identify the optimal obfuscation strategy. To handle large-scale datasets, such as high-resolution GPS grids, the paper introduces approximation techniques that prune distant, less relevant constraints, significantly reducing computational overhead with negligible impact on privacy guarantees.

Experimental Evaluation

The framework was evaluated using the Nokia Lausanne Data Collection Campaign, which contains high-resolution location traces. A 15x8km area was discretized into a grid of 300 cells. Using traces from 10 users to establish prior probability distributions (priors), the authors compared their joint mechanism against standalone DP and Distortion Privacy approaches.

Key Results and Insights

  • Privacy for "Free": A primary finding is that adding Distortion Privacy constraints to a mechanism already satisfying DP often does not increase utility loss. Because DP is typically the more restrictive requirement, users can gain the absolute protection of distortion-based metrics without further degrading service quality.
  • Robustness Against Optimal Attacks: By assuming an optimal adversary, the resulting defense remains effective against any possible inference algorithm. The joint mechanism achieves the maximum privacy possible while keeping utility loss at the level of the more restrictive individual metric.
  • Resilience to Prior Knowledge: The study also highlighted that Differential Privacy maintains its effectiveness even when the adversary possesses significantly more background knowledge than anticipated by the user.

Conclusion and Future Work

This work provides a rigorous mathematical foundation for balancing data utility and privacy. By combining the strengths of Differential and Distortion Privacy within a game-theoretic model, it offers a robust defense mechanism for modern data-sharing applications.

However, limitations remain. The computational cost of solving LPs scales poorly with the number of possible secrets, and the current model primarily addresses static data sharing. Future research directions include extending the model to handle continuous temporal data streams and developing more intuitive methods for users to define their specific utility and privacy distance functions.

Summary updated

BibTeX
@article{shokri2015privacy,
  author = {Reza Shokri},
  title = {{Privacy Games: Optimal Protection Mechanism Design for Bayesian and Differential Privacy}},
  journal = {Proc. Priv. Enhancing Technol.},
  year = {2015},
  doi = {10.1515/popets-2015-0024},
}
Figure