PaperlayerView exact revision on arXiv

Source-linked AI summary

Privacy Against Statistical Inference

Flavio du Pin Calmon, Nadia Fawaz

arXiv:1210.2123v1cs.ITcs.CR

TL;DR

The paper addresses how to protect private data inferred from released measurements while preserving analyst utility. It develops an inference-cost framework that yields information-leakage metrics and convex optimization formulations, and shows that differential privacy need not constrain leakage.

  • Problem

    The central problem is balancing a user’s privacy against an analyst’s utility when released measurements are correlated with private information.

  • Method

    The paper models privacy risk through adversarial inference cost, specializes to self-information, and formulates optimal privacy-preserving mappings as modified rate-distortion problems and convex programs.

  • Results

    Differential privacy does not necessarily provide guarantees on average or maximum information leakage, while information privacy implies differential privacy and bounded average leakage.

  • Takeaways & Limitations

    The framework provides a statistical and information-theoretic basis for designing privacy-preserving mappings under utility constraints.

Abstract

from arXiv · show

We propose a general statistical inference framework to capture the privacy threat incurred by a user that releases data to a passive but curious adversary, given utility constraints. We show that applying this general framework to the setting where the adversary uses the self-information cost function naturally leads to a non-asymptotic information-theoretic approach for characterizing the best achievable privacy subject to utility constraints. Based on these results we introduce two privacy metrics, namely average information leakage and maximum information leakage. We prove that under both metrics the resulting design problem of finding the optimal mapping from the user's data to a privacy-preserving output can be cast as a modified rate-distortion problem which, in turn, can be formulated as a convex program. Finally, we compare our framework with differential privacy.

I. INTRODUCTION

The paper frames privacy as limiting a curious analyst’s inference about private data while preserving measurement utility. It develops a general cost-based framework, specializes it to information leakage, and compares the resulting guarantees with differential privacy.

  • Growing data collection intensifies the need for privacy-preserving services across social, legal, and business settings.
  • The core problem is balancing a user’s privacy against an analyst’s utility when released measurements correlate with private information.
  • The framework models privacy risk as the inference cost gain of a passive but curious adversary and optimizes mappings under utility constraints.
  • Using self-information yields average and maximum information leakage metrics and modified rate-distortion formulations expressible as convex programs.
  • Information privacy implies differential privacy and bounded information leakage, whereas differential privacy alone does not generally guarantee low leakage.
  • The paper organizes its setup, trade-off formulation, main results, privacy-model comparison, and conclusions across Sections II–VI.

A. General setup

Alice releases a distorted version of measurements Y to Bob, who must receive utility while being unable to infer private variables S. The threat model treats Bob as passive, computationally unbounded, and fully informed about the prior and mechanism.

  • Alice and Bob communicate over a noiseless channel, with Alice holding measurements Y jointly distributed with private variables S.
  • Alice designs U as a distorted version of Y that satisfies Bob’s utility constraint while protecting S from inference.
  • The model assumes the Markov chain S → Y → U and accommodates both output and input perturbation settings.
  • A privacy-preserving mapping is a probabilistic transition from Y to U, specified by p_U|Y(u|y).
  • Utility is represented by distortion, with constraint E_Y,U[d(Y, U)] ≤ ∆; utility and accuracy are used interchangeably.
  • Alice and Bob know the prior distribution and Bob knows the complete privacy mapping, representing worst-case statistical side information.
  • Bob updates a distribution q over S to minimize expected inference cost, before and after observing U.
  • The framework measures both average and maximum adversarial cost gain and then formulates the privacy-accuracy trade-off.

III. A GENERAL FORMULATION FOR THE PRIVACY-ACCURACY TRADEOFF

The paper formulates privacy-utility design as optimizing conditional mappings from Y to U under distortion constraints. The framework also covers database queries and feature obfuscation as application settings.

  • A. The privacy-accuracy tradeoff as an optimization problem: The design objective minimizes average or maximum adversarial cost gain over conditional distributions p_U|Y for a specified distortion level.
  • A. The privacy-accuracy tradeoff as an optimization problem: The feasible set P_U|Y consists of all conditional probability distributions of U given Y.
  • A. The privacy-accuracy tradeoff as an optimization problem: Multiple distortion constraints can be incorporated by adding one linear constraint for each metric to the convex program.
  • B. Application examples: The framework illustrates privacy-preserving queries and hiding features within data sets.
  • B. Application examples: For database privacy, S contains discrete entries, a query Y=f(S1, ..., Sn) is computed, and U should hide individual entries while preserving query utility.

1) Privacy-preserving queries to a database:

The database-query example applies the framework to counting queries and distinguishes perturbing the query output from perturbing individual inputs. It also extends the framework to obfuscating sensitive features in data sets.

  • 1) Privacy-preserving queries to a database:: The counting-query example defines a database property indicator that equals 1 when an entry has property A and 0 otherwise.
  • 1) Privacy-preserving queries to a database:: Output perturbation distorts the computed query result Y directly to produce U.
  • 1) Privacy-preserving queries to a database:: Input perturbation distorts each database entry S_i before computing the resulting query output U.
  • 1) Privacy-preserving queries to a database:: Feature obfuscation distorts data-set entries Y to protect a smaller sensitive feature set S, with distortion tied to a statistical learning algorithm’s utility.

IV. PRIVACY-ACCURACY TRADEOFF RESULTS

The general formulation is specialized here to the case where the adversary uses the self-information cost function.

  • The formulation is particularized to the adversary’s self-information cost function.

A. The self-information cost function

The self-information, or log-loss, cost function is motivated by its distinctive prediction properties and its connection to privacy-utility optimization. Using it enables convex formulations that can be solved efficiently.

  • The self-information cost function is also called the log-loss cost function.
  • It is the only local, proper, and smooth cost function for alphabets with at least three symbols.
  • Its minimum-loss probability assignments are essentially maximum-likelihood estimates, making it consistent with a rational adversary.
  • Average cost gain under self-information can be related to cost gain under any other bounded cost function.
  • The resulting cost-minimization problems can be cast as convex programs and efficiently solved with interior-point methods or standard convex solvers.

B. Average information leakage

Average information leakage is defined as mutual information between private data and the privacy-preserving output. Under the paper’s constraints, minimizing it becomes a modified rate-distortion problem with a convex formulation.

  • Average information leakage is defined as I(S; U), the mutual information between private features S and privacy-preserving output U.
  • The optimal privacy-preserving mapping minimizes I(S; U) subject to the distortion constraint ∆.
  • The minimization is a modified rate-distortion problem and can equivalently minimize expected KL-divergence between posterior and prior distributions.
  • This KL formulation seeks posterior distributions after observing U that remain as close as possible to the prior distribution.
  • The design optimization uses pU|Y and pU|S coupled by a linear equality constraint and is formulated as a convex program.
  • When Y is deterministic in S and S → Y → U, the minimization simplifies to a rate-distortion problem; additive noise further yields H(Y|U)=H(Z).

C. Maximum information leakage

Maximum information leakage measures the largest log-loss gain obtained from any single output. Its constrained optimization is convex, while deterministic-query cases reveal how optimal mappings allocate posterior probability according to inherent uncertainty.

  • Maximum information leakage is the largest log-loss cost gain an adversary obtains from observing a single output.
  • The minmax mapping minimizes distortion subject to a constraint ǫ on maximum information leakage.
  • The resulting optimization is a convex program and can be solved to arbitrary precision by line-searching over ǫ.
  • Although Theorem 2 applies generally, it provides limited structural insight into the optimal mapping outside the deterministic-function setting.
  • For deterministic Y=f(S) with S → Y → U, the optimal privacy-preserving mapping has a specialized form determined by the fixed prior pY,S.
  • For deterministic Y=f(S), the optimal mechanism approximates the posterior distribution of Y given U to ζ in KL-divergence.
  • The mechanism augments uncertainty while respecting distortion, assigning larger posterior probability to outputs with greater H(S|Y=y).
  • For counting queries with iid database inputs, the optimal posterior is proportional to the pre-image size of each output.

V. COMPARISON OF PRIVACY METRICS

The comparison shows that differential privacy can coexist with substantial information leakage, while information privacy provides guarantees for both differential privacy and information leakage. Differential privacy has the operational advantage of requiring no prior, but may be suboptimal under information-leakage measures.

  • Information privacy implies 2ε-differential privacy and limits maximum information leakage to at most ε/ln 2 bits.Under the stated support condition, it also limits average information leakage to at most ε/ln 2 bits.
  • Differential privacy does not guarantee low average information leakage, which can become arbitrarily large.The paper constructs an ε-differentially private mechanism leaking at least δ bits on average for any ε > 0 and δ ≥ 0.
  • The counterexample can let an adversary recover the inputs with arbitrarily high probability by exploiting input correlations.The construction assumes ordered, correlated inputs so that the counting-query output identifies the initial sequence of ones.
  • For sufficiently large n, differential privacy permits average information leakage bounded only by O(εn).This bound corroborates that differential privacy does not provide an upper bound independent of dataset size.
  • Differential privacy requires no prior information, but ignoring priors can produce mechanisms that are suboptimal under information-leakage measures.The formulations can instead be made prior independent by maximizing the minimum information leakage over a set of possible priors.

VI. CONCLUSIONS

The paper develops a statistical-inference framework for privacy threats under utility constraints and an information-theoretic approach based on self-information. It introduces leakage metrics, formulates their privacy-utility design problems as convex programs, and finds that differential privacy does not necessarily constrain information leakage.

  • The framework models privacy threats from releasing data to a passive but curious adversary while satisfying utility constraints.
  • Applying self-information yields a non-asymptotic information-theoretic characterization of privacy subject to utility constraints.
  • Average and maximum information leakage define two privacy metrics whose optimal privacy-utility design problems become convex programs.
  • The comparison shows that differential privacy does not necessarily constrain information leakage from a data set.
Loading 1210.2123v1…