Optimal User-Centric Data Obfuscation

Reza Shokri

Abstract

In this paper, we design user-centric obfuscation mechanisms that impose the minimum utility loss for guaranteeing user's privacy. We optimize utility subject to a joint guarantee of differential privacy (indistinguishability) and distortion privacy (inference error). This double shield of protection limits the information leakage through obfuscation mechanism as well as the posterior inference. We show that the privacy achieved through joint differential-distortion mechanisms against optimal attacks is as large as the maximum privacy that can be achieved by either of these mechanisms separately. Their utility cost is also not larger than what either of the differential or distortion mechanisms imposes. We model the optimization problem as a leader-follower game between the designer of obfuscation mechanism and the potential adversary, and design adaptive mechanisms that anticipate and protect against optimal inference algorithms. Thus, the obfuscation mechanism is optimal against any inference algorithm.

Introduction

In our data-driven world, users frequently trade personal information, such as GPS coordinates, for personalized services. To protect sensitive data, users employ obfuscation—adding noise or ambiguity before sharing information. However, this creates a fundamental conflict: excessive noise renders the service useless (low utility), while insufficient noise allows observers to deduce secrets (low privacy).

Existing solutions often suffer from two major flaws. First, they assume static attackers, failing to account for adversaries who adapt their strategies once the obfuscation method is known. Second, they often focus on a single-metric, such as Differential Privacy, while ignoring Distortion Privacy (the actual error in an attacker's estimate). This paper introduces a framework for "user-centric" data obfuscation that achieves a mathematically optimal balance between these competing needs.

Methodology: The Stackelberg Game

The researchers model the interaction between a user and an adversary as a Stackelberg (leader-follower) game. In this model, the user (the leader) chooses and commits to an obfuscation mechanism, while the adversary (the follower) observes this mechanism and designs the mathematically optimal inference attack to guess the true secret.

System model for user-centric data obfuscation, illustrating the flow from secret to estimate and the associated utility and privacy metrics.

The core technical contribution is proving that this complex game-theoretic problem can be reduced to Linear Programming (LP). The framework minimizes utility loss while satisfying a "joint" privacy constraint. This "double shield" ensures that data is both indistinguishable (Differential Privacy) and leads to a high expected error for the attacker (Distortion Privacy), even when the attacker possesses prior knowledge about the user.

Key Insights and Results

  • Anticipating the Best Attacker: By optimizing against the most capable adaptive attack, the mechanism becomes robust against all possible inference strategies.
  • The "Double Shield" Efficiency: Surprisingly, a joint mechanism satisfying both differential and distortion privacy is often no more "expensive" in terms of utility than a mechanism satisfying only one. Users receive a second layer of protection with minimal additional utility cost.
  • User-Centricity: Unlike generic tools, this framework allows individuals to define their own sensitivity metrics—specifying exactly what they want to hide and what level of service quality they are willing to sacrifice.

Experimental evaluations using real-world location datasets (a 300-cell grid) demonstrated that the joint mechanism consistently outperforms standalone differential privacy mechanisms against Bayesian inference attacks. It effectively "fills the gaps" where differential privacy might otherwise allow an attacker with strong prior knowledge to make a successful guess.

Limitations and Future Work

While powerful, the framework faces challenges in computational complexity. Solving the required Linear Programs scales at $O(N^2)$ to $O(N^3)$ relative to the number of secrets, making it difficult to apply to massive datasets without approximation. Additionally, the model currently relies on users being able to accurately define their utility and privacy distance functions. Future research may explore dynamic priors to account for how these games evolve in real-time as users continuously share data over long periods.

Summary updated

Abstract

In this paper, we design user-centric obfuscation mechanisms that impose the minimum utility loss for guaranteeing user's privacy. We optimize utility subject to a joint guarantee of differential privacy (indistinguishability) and distortion privacy (inference error). This double shield of protection limits the information leakage through obfuscation mechanism as well as the posterior inference. We show that the privacy achieved through joint differential-distortion mechanisms against optimal attacks is as large as the maximum privacy that can be achieved by either of these mechanisms separately. Their utility cost is also not larger than what either of the differential or distortion mechanisms imposes. We model the optimization problem as a leader-follower game between the designer of obfuscation mechanism and the potential adversary, and design adaptive mechanisms that anticipate and protect against optimal inference algorithms. Thus, the obfuscation mechanism is optimal against any inference algorithm.
BibTeX
@article{shokri2015optimal,
  author = {Reza Shokri},
  title = {{Optimal User-Centric Data Obfuscation}},
  journal = {Proc. Priv. Enhancing Technol.},
  year = {2015},
  doi = {10.1515/popets-2015-0024},
}
Figure