Source-linked AI summary
Privacy Games: Optimal User-Centric Data Obfuscation
Reza Shokri
TL;DR
The paper addresses how to preserve user privacy while minimizing the utility loss of obfuscating shared data. It designs adaptive user-centric mechanisms with joint differential and distortion privacy guarantees, and shows that they achieve the stronger individual privacy level without extra utility loss beyond either metric alone.
Problem
User-centric obfuscation must balance service utility with privacy, while differential privacy and distortion privacy each capture only part of the privacy problem.
Method
The paper models mechanism design and adaptive inference as a leader-follower game and solves joint privacy-constrained optimization using linear programming.
Results
Joint mechanisms achieve privacy equal to the maximum provided separately by differential or distortion privacy, with utility loss no greater than either mechanism alone.
Takeaways & Limitations
User-centric obfuscation can jointly protect against observation leakage and posterior inference while achieving minimum utility loss under the specified privacy bounds.
Takeaways & Limitations
The guarantees depend on the user’s estimate of prior leakage, and cannot protect against adversaries with arbitrary knowledge outside the observation channel.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets user-centric obfuscation that preserves service utility while jointly protecting against information leakage and posterior inference. It formulates adaptive protection against optimal attacks and reports privacy and utility guarantees for the joint mechanism.
- 1 Introduction: The central design problem is minimizing utility loss while guaranteeing privacy despite no single metric capturing privacy completely.Differential privacy bounds observation leakage, whereas distortion privacy measures inference error but relies on prior knowledge.
- 1 Introduction: The mechanism anticipates adaptive inference by modeling the designer and adversary as a Stackelberg game and solving the resulting optimization with linear programming.The differential privacy guarantee is added as a constraint to the optimization.
- 1 Introduction: Joint differential-distortion mechanisms make released samples indistinguishable from secrets while preventing accurate inference using prior leakage.The paper presents this as a formal double protection against observation leakage and posterior inference.
- 1 Introduction: The optimal joint mechanism achieves privacy at least as strong as either individual metric while incurring no greater utility loss than differential or distortion privacy alone.The evaluation uses users’ locations and tests robustness against inference algorithms and background knowledge.
- 1 Introduction: The contribution is a user-centric mechanism that provably limits privacy risk against any inference attack while minimizing utility cost.The paper also frames the mechanism as optimally balancing utility with joint privacy guarantees.
2 Related Work
Prior work studies differential privacy, distortion privacy, and utility optimization separately or under narrower game formulations. This paper combines these privacy perspectives for user-centric obfuscation and provides a linear-programming solution to the resulting privacy game.
- 2 Related Work: The paper combines protection against observation leakage and posterior inference for individual users who perturb secrets before sharing them.It positions this framework within quantitative information flow, quantitative privacy, and differential privacy research.
- 2 Related Work: Existing differential-privacy work primarily addresses statistical databases, while related user-centric mechanisms use linear programming for utility-maximizing perturbation.The cited literature includes counting queries and other database settings.
- 2 Related Work: Earlier work optimized distortion privacy under utility constraints through zero-sum games against adaptive adversaries, but the privacy-guarantee formulation is not zero-sum.The user maximizes utility while the observer minimizes privacy.
- 2 Related Work: The paper addresses the unresolved formulation of maximizing utility under a lower-bound privacy constraint for generic distance functions.The resulting framework supports sensitivity functions for arbitrary secret types.
- 2 Related Work: For repeated sharing, prior leakage and the differential privacy budget must be updated over time, although this paper models one-time sharing with those quantities already adjusted.This defines the temporal scope of the presented formulation.
3 Definitions
The framework represents a secret, prior leakage, obfuscation channel, utility cost, and adaptive inference attack using user-defined distance functions. Privacy is measured through distortion of inference and differential indistinguishability, while utility reflects deviation from the true secret.
- 3 Definitions: The user’s secret s is drawn from possible values, while prior leakage π represents the user’s estimated exposed information and data predictability.The prior is updated after sharing to incorporate correlations across time.
- 3 Definitions: The protection mechanism samples an observable o from secret s, forming a noisy channel between the user and an untrusted observer.The observable space can include possible secret values or more general outputs.
- 3 Definitions: Utility loss is the expected application-dependent distance c(o,s) caused by replacing the secret with an observable.The utility function may reflect the service, user expectations, or learned preferences.
- 3 Definitions: The adaptive adversary applies inference attack q to observations and produces a distribution over estimated secrets.The adversary’s estimation error determines distortion privacy.
- 3 Definitions: Distortion privacy measures expected inference error through a user-defined distance d between the estimated and true secrets.The distance can encode semantic or application-specific sensitivity, such as geographic or set-based dissimilarity.
- 3 Definitions: Differential privacy measures information leakage through differences in the probabilities of producing the same observation from different secrets.The paper uses a generic distinguishability distance between secrets.
4 Problem Statement
The problem is to construct an obfuscation distribution that minimizes utility cost while satisfying joint differential and distortion privacy constraints. The formulation uses desired privacy thresholds and an optimal attack against the mechanism.
- 4 Problem Statement: The objective is to construct utility-maximizing obfuscation mechanisms with joint differential-distortion privacy guarantees.Equivalently, the mechanism minimizes the user’s utility cost subject to privacy constraints.
- 4 Problem Statement: The optimization minimizes expected utility cost by weighting each observable-secret distance c(o,s) by the mechanism’s probability p(o|s).The paper also considers the alternative worst-case cost over secrets.
- 4 Problem Statement: The distortion privacy constraint uses a minimum desired level d_m and an optimal inference attack q* against the candidate mechanism p*.The attack is defined relative to the mechanism being optimized.
- 4 Problem Statement: The differential privacy constraint uses a privacy budget ϵ_m and distinguishability threshold d_ϵm.The paper mainly uses one definition and uses the alternative formulation to reduce optimization cost.
5 Solution: Privacy Games
The privacy game models obfuscation as a known probabilistic mechanism followed by an adversary’s adaptive inference attack. The user chooses the mechanism first, anticipating the attacker’s best response to maximize privacy and utility payoff.
- The optimal mechanism maximizes the user’s payoff against the corresponding inference attack that optimizes the adversary’s objective.This design protects against attacks adapted to each specific mechanism rather than a fixed assumed algorithm.
- The user leads by selecting an obfuscation mechanism, while the adversary follows with an inference attack tailored to that mechanism.The equilibrium consists of mutually optimal user and adversary strategies.
- The user’s strategy space contains probability distributions over observables for each secret, while the adversary’s strategy space contains distributions over secret estimates for each observation.These mixed strategies are represented by vectors and their feasible sets P and Q.
- For distortion privacy, the game uses a Bayesian Stackelberg formulation in which the secret prior determines the equilibrium strategies.A deviation from the equilibrium mechanism admits an inference attack yielding lower user privacy.
- For differential privacy, the privacy metric does not depend on the adversary’s inference attack, so the dependency between optimizing the two strategies is broken.The user still chooses the protection mechanism first.
6 Stackelberg Privacy Games
The Stackelberg formulation alternates between designing the adversary’s best inference response and the user’s utility-maximizing protection mechanism. Linear programming constructs the user’s optimal strategy against that response.
- The adversary minimizes expected estimation error under a known secret prior and obfuscation mechanism, using a distance function to measure inference error.The resulting optimization is a linear program constrained to proper conditional probability distributions.
- Deterministic inference achieves the same user privacy as the optimal inference strategy in this formulation.The paper states that assigning one estimate with probability one to each observation produces the same privacy result.
- The user then designs a protection mechanism that minimizes utility cost while satisfying a lower bound on distortion privacy.The mechanism anticipates the adversary’s best response rather than optimizing against an assumed fixed attack.
- The mutual dependence between the user’s and adversary’s linear programs is modeled as a nonzero-sum Stackelberg game and resolved through linear programming.The user maximizes utility while the adversary minimizes privacy, yielding mutually optimal strategies.
- Theorem 1 states that the specified linear program yields the user’s optimal protection strategy against the adversary’s best response.The result is parameterized by the secret prior, distance functions, and distortion threshold.
7 Optimal Differential Privacy
The paper formulates optimal differential-privacy protection as utility maximization under a privacy constraint. The resulting linear program minimizes obfuscation cost for a specified maximum privacy budget.
- The differential-privacy mechanism is designed by maximizing utility subject to a privacy constraint.The section focuses on solving the optimization problem for differential privacy.
- The user’s optimal strategy minimizes obfuscation utility cost while guaranteeing differential privacy for a maximum privacy budget ϵm.The mechanism is obtained through a linear program.
8 Optimal Joint Differential and Distortion Privacy Mechanism
Differential and distortion privacy protect different dimensions: relative information leakage and absolute posterior privacy. The paper therefore jointly optimizes both guarantees in a single linear-program formulation.
- Differential and distortion guarantees are distinct, and a bound on one metric does not generally imply a bound on the other.The paper motivates enforcing both metrics in the same protection mechanism.
- Joint protection limits both information leakage through observations and the adversary’s posterior inference about the secret.Differential privacy addresses relative leakage, while distortion privacy addresses absolute privacy based on posterior estimation.
- The joint optimization problem is formulated as a linear program that maximizes utility while guaranteeing minimum distortion and differential privacy levels.The optimal mechanism is parameterized by the secret prior, distance functions, and distinguishability metric.
9 Analysis
The analysis compares optimal distortion, differential, and joint privacy mechanisms on location data under multiple inference attacks and privacy settings. Joint mechanisms achieve the strongest supported privacy without exceeding the utility cost of the individual mechanisms.
- Experimental setup: Experiments use Nokia Lausanne location traces, model locations as 20 × 15 secret and observable cells, and evaluate distortion, differential, and joint privacy constraints.Euclidean distance defines privacy-related distortion and Hamming distance defines utility cost for location sharing.
- Scenario 1: As the differential privacy lower bound increases, expected location privacy decreases and converges below 1 km, while differential and joint mechanisms have higher utility cost than the distortion mechanism at matched privacy.Distortion privacy is measured in kilometers as the adversary’s expected location-estimation error.
- Scenario 1: Under Bayesian inference attacks, optimal differential mechanisms are more robust than optimal distortion mechanisms, explaining their higher utility cost in the comparison.When confronted with the optimal attack, the two mechanisms provide the same distortion privacy; their difference appears under the Bayesian attack.
- Scenario 1: The optimal attack reports lower privacy than the Bayesian attack because it minimizes expected distance over secrets and estimates, whereas the Bayesian attack ignores the distance function.The comparison covers all three optimal protection mechanisms.
- Scenario 2: The joint mechanism is not more costly than the individual mechanisms and guarantees the highest privacy for a given utility cost.This comparison is reported for the evaluation scenario introducing joint distortion-differential protection.
- The joint mechanism achieves privacy equal to the maximum provided separately by the differential and distortion mechanisms, while its utility cost is not additive and is governed by the larger component cost.Across tested experiments, the differential privacy component determines the joint mechanism’s utility cost.
10 Conclusions
The paper proposes joint distortion-differential privacy mechanisms with optimal inference attacks and linear-program solutions that minimize utility loss under privacy bounds.
- 10 Conclusions: The paper introduces joint distortion-differential privacy and constructs an optimal mechanism combining the strengths of both metrics.The framework is generic to distance functions and can formalize sensitivity for different secret types.
- 10 Conclusions: The resulting linear programs provably achieve minimum utility loss under the specified privacy bounds.The paper presents these solutions as optimal protection mechanisms for user-centric data sharing.
- 10 Conclusions: The optimal inference attack minimizes conditional expected estimation error through a linear program under the stated assumptions.The formulation can use a weighted sum over secrets or a min-max objective over conditional errors.
B Proof of Theorem 1
The proof constructs an equivalent attack formulation by relating mixed inference strategies to pure strategies and replacing one constraint with two equivalent constraints.
- B Proof of Theorem 1: The optimal obfuscation is conditioned on its corresponding best-response inference attack, which minimizes expected error for each observable.This relationship is used to construct the proof’s alternative formulation.
- B Proof of Theorem 1: The proof introduces a conditional distribution q′ for each observable and uses it to characterize a particular pure inference strategy.The resulting optimization over mixed strategies includes all such pure strategies.
- B Proof of Theorem 1: Because mixed strategies contain the pure strategies as a subset, optimization over mixed strategies achieves an objective no larger than optimization over pure strategies.This inequality supports the proof’s comparison between the two strategy classes.
- B Proof of Theorem 1: The proof shows that constraint (20b) can be replaced by constraints (21b) and (21c) without changing the linear program.The equivalence follows from the preceding inequalities involving the weighted distortion expression.
C Approximating The Optimal Mechanisms
The optimal mechanisms are computed with linear programs whose cost grows quadratically or cubically with problem size, motivating constraint-based approximations that trade privacy accuracy for computation time.
- C Approximating The Optimal Mechanisms: Linear-program computation is quadratic for distortion mechanisms and cubic for differential mechanisms in the number of secrets and observables.Large secret sets therefore require substantial computation budgets.
- C Approximating The Optimal Mechanisms: Approximation methods reduce computation by stopping iterative optimization or selecting a subset of constraints, while preserving an affordable solution process.The paper also exploits secret structure and privacy definitions to reduce constraints.
- C Approximating The Optimal Mechanisms: As the approximation threshold increases, privacy error approaches zero, but computation time increases because more constraints are retained.Figure 8 summarizes this privacy-accuracy and computation-time tradeoff using boxplots over users.
- C Approximating The Optimal Mechanisms: Approximation can provide nearly the same privacy level as the optimal solution for large secret sets when a relatively small threshold is chosen.The improvement in computational speed comes at the cost of increased approximation error when fewer constraints are used.