PaperlayerView exact revision on arXiv

Source-linked AI summary

Pufferfish Privacy Mechanisms for Correlated Data

Shuang Song, Yizhen Wang, Kamalika Chaudhuri

arXiv:1603.03977v3cs.LGcs.CRstat.ML

TL;DR

Correlated data challenges differential privacy because records may represent linked individuals or repeated measurements from one subject. The paper develops Pufferfish mechanisms, including a general Wasserstein Mechanism and a more efficient Markov Quilt Mechanism, and evaluates them on synthetic and real data. The reported results support privacy and utility for these correlated-data applications, while the framework’s effectiveness depends on choosing an appropriate distribution class and some computations may remain inefficient.

  • Problem

    Differential privacy does not adequately address privacy for correlated data, while suitable general Pufferfish mechanisms are lacking.

  • Method

    The paper introduces the Wasserstein Mechanism for general Pufferfish frameworks and the Markov Quilt Mechanism for Bayesian-network correlations, with a time-series specialization.

  • Results

    Experiments on synthetic and real data indicate that the mechanisms provide privacy and utility, with Markov Quilt utility improving for longer chains.

  • Takeaways & Limitations

    Pufferfish offers a privacy framework for correlated-data problems, with mechanisms that can exploit correlation structure and support practical time-series applications.

  • Takeaways & Limitations

    Pufferfish requires careful selection of Θ, and the general mechanism or exact max-influence computation may be computationally inefficient.

Abstract

from arXiv · show

Many modern databases include personal and sensitive correlated data, such as private information on users connected together in a social network, and measurements of physical activity of single subjects across time. However, differential privacy, the current gold standard in data privacy, does not adequately address privacy issues in this kind of data. This work looks at a recent generalization of differential privacy, called Pufferfish, that can be used to address privacy in correlated data. The main challenge in applying Pufferfish is a lack of suitable mechanisms. We provide the first mechanism -- the Wasserstein Mechanism -- which applies to any general Pufferfish framework. Since this mechanism may be computationally inefficient, we provide an additional mechanism that applies to some practical cases such as physical activity measurements across time, and is computationally efficient. Our experimental evaluations indicate that this mechanism provides privacy and utility for synthetic as well as real data in two separate domains.

1. INTRODUCTION

Correlated data, such as single-subject time series and socially connected records, creates privacy challenges that standard differential privacy and group privacy do not adequately address. The paper adopts Pufferfish and introduces general and computationally efficient mechanisms for these settings.

  • Motivation: Correlated records arise in applications such as physical activity monitoring, where measurements across short intervals form highly correlated time series.The paper also motivates correlated privacy through healthcare, power usage, building management, and social-network data.
  • Motivation: Entry privacy can fail to hide correlated activities, while group differential privacy may add approximately O(T) noise and destroy utility.For a histogram over T measurements, group privacy treats all correlated entries as a group.
  • Privacy framework: Pufferfish specifies secrets, secret pairs, and a distribution class whose generated data must make the secret pairs indistinguishable.The framework is used to express privacy requirements for correlated data.
  • Contributions: The paper establishes that privacy loss remains small when an adversary’s belief lies outside the modeled distribution class but is close to it.This result supports robustness of Pufferfish against adversarial beliefs near the assumed class.
  • Contributions: The Markov Quilt Mechanism reduces computational complexity for Bayesian-network correlations and is specialized to physical-activity time series.The paper provides privacy and utility guarantees, composition properties, and experiments on synthetic and real data.
  • Contributions: The Wasserstein Mechanism is the first mechanism applicable to any general Pufferfish instantiation.The paper presents it as a generalization of the Laplace mechanism for differential privacy.

2. THE SETTING

The setting models privacy for correlated records through Pufferfish, using secrets, secret pairs, and plausible data distributions. Physical-activity and flu-status examples show why correlation-aware noise can preserve utility where entry- or group-based privacy does not.

  • Pufferfish framework: Pufferfish is instantiated by a secret set S, secret pairs Q, and a distribution class Θ describing plausible data-generating models.Privacy requires secret pairs in Q to be indistinguishable for data generated from every θ ∈ Θ.
  • Pufferfish framework: Choosing Θ involves a privacy–utility trade-off: all-distribution classes preclude simultaneous privacy and utility, while restrictive classes may fail to cover legitimate adversaries.The paper emphasizes that Θ must be selected carefully.
  • Pufferfish framework: Pufferfish privacy does not always compose gracefully across repeated computations, although some mechanisms in this work have composition properties.The paper separately establishes composition properties for its mechanisms.
  • Physical activity: For physical-activity data, secrets are activities at individual times, secret pairs compare activities, and Θ can contain Markov-chain models of activity transitions.The goal is to release an activity histogram while hiding the activity at any particular time.
  • Physical activity: Entry privacy adds approximately 1/ϵ noise per histogram bin, whereas group privacy adds approximately T/ϵ noise and destroys utility when all entries are correlated.The paper motivates Pufferfish as a way to address this correlated time-series setting.
  • Physical activity: An ϵ-Pufferfish mechanism adds noise approximately equal to the mixing time divided by ϵ, offering privacy and utility for rapidly mixing chains.This provides the paper’s targeted utility claim for the physical-activity example.
  • Flu status: For socially connected flu data, Pufferfish models individual flu statuses as secrets and uses distributions describing infection spread over interaction graphs.The example reflects group-level participation and correlated statuses.
  • Flu status: Pufferfish noise can be proportional to the average spread of flu, potentially requiring less noise than group differential privacy.The passage presents this as a route to privacy and utility in the flu-status example.

3. A GENERAL MECHANISM

The paper introduces the Wasserstein Mechanism, a general mechanism for Pufferfish privacy that calibrates Laplace noise to distributional distances between secret-conditioned query outputs. It guarantees privacy, generalizes the Laplace mechanism, and can offer better utility than group differential privacy in correlated settings.

  • General mechanism: The Wasserstein Mechanism applies to any general Pufferfish instantiation by approximating a scalar query while satisfying ϵ-Pufferfish privacy.It addresses the absence of a mechanism that works across general Pufferfish frameworks.
  • General mechanism: It compares P(F(X)|s_i, θ) and P(F(X)|s_j, θ) for secret pairs and calibrates noise to their ∞-Wasserstein distance.This distance is the maximum movement of probability mass under an optimal coupling.
  • General mechanism: For each secret pair and distribution, the mechanism computes W∞, takes the maximum W, and releases F(D) plus Laplace noise with scale W/ϵ.The algorithm evaluates conditional query-output distributions before selecting the worst-case scale.
  • General mechanism: When Pufferfish reduces to differential privacy, the Wasserstein Mechanism reduces to the Laplace mechanism.This establishes the mechanism as a generalization of the standard differential-privacy construction.
  • Performance guarantees: In the flu-status example, W=2 yields Lap(2/ϵ) noise, compared with Lap(4/ϵ) under group differential privacy.The example has four mutually correlated variables, so the Wasserstein Mechanism provides the smaller noise scale.
  • Performance guarantees: For an L-Lipschitz query, W is at most the global sensitivity under the corresponding group differential privacy framework.Thus, the Wasserstein Mechanism never performs worse than the corresponding group-differential-privacy Laplace mechanism in the stated setting.

4. A MECHANISM FOR BAYESIAN NETWORKS

The paper develops mechanisms for Pufferfish privacy in Bayesian-network settings, including a general Wasserstein mechanism and a more efficient Markov Quilt mechanism with privacy and utility guarantees.

  • Setting: The Bayesian-network setting models dependencies among variables X1 through Xn, including Markov chains and trees.The network is represented by a directed acyclic graph whose edges induce parent-child relationships.
  • Markov Quilt Mechanism: The Markov Quilt Mechanism protects Xi by selecting a quilt with low max-influence and adding Laplace noise scaled by L·card(XN)/(ϵ−δ).The mechanism searches a set of quilts and chooses the one requiring the least noise.
  • Privacy guarantees: The Markov Quilt Mechanism preserves ϵ-Pufferfish privacy for L-Lipschitz queries when each candidate set includes the trivial quilt.The result is stated in Theorem 4.3 for the Bayesian-network instantiation.
  • Composition: Sequential composition provides Kϵ-Pufferfish privacy for K released mechanisms under the stated shared-quilt condition.The same set SQ,i must be used across the mechanisms.
  • Markov-chain efficiency: For Markov chains, structural information reduces computation, with the exact implementation running in O(Tℓ^2k^3|Θ|).Dynamic programming computes required probabilities in O(Tk^3), while quilt and distribution searches produce the stated overall runtime.
  • Approximation and utility: For sufficiently long chains, the approximate mechanism adds noise with scale at most C/ϵ, independent of chain length T.The relative accuracy improves with more observations; for rapidly mixing chains, the mechanism provides both privacy and utility.

5. EXPERIMENTS

The experiments evaluate Pufferfish mechanisms across synthetic Markov-chain data and real physical-activity and electricity datasets. The Markov Quilt Mechanism generally offers stronger utility or broader applicability than baselines, with MQMExact trading higher accuracy for longer runtime.

  • Experimental setup: The evaluation compares GroupDP, GK16, MQMApprox, and MQMExact across synthetic, physical-activity, and electricity-consumption settings.The experiments vary privacy level, distribution class, dataset scale, and approximation method.
  • Synthetic simulations: As α increases and Θ narrows, the errors of GK16, MQMApprox, and MQMExact decrease for a fixed ϵ.GK16 becomes inapplicable when the influence-matrix spectral norm exceeds 1, whereas both Markov Quilt variants continue to provide privacy and reasonable utility.
  • Synthetic simulations: The Markov Quilt Mechanism applies to a wider range of synthetic distribution families than GK16 and outperforms GK16 for a range of parameter values where both apply.MQMExact is more accurate than MQMApprox, while MQMApprox requires less running time.
  • Physical activity measurement: MQMApprox and MQMExact have significantly better utility than GroupDP across all physical-activity datasets and tasks, and better utility than DP for aggregate release.GK16 cannot be applied to these tasks because its spectral-norm condition is not satisfied.
  • Electricity consumption: For electricity data, MQMApprox and MQMExact retain high utility despite many bins, while GroupDP has very large error and GK16 does not apply.MQMExact has about 0.25 percent per-bin error at ϵ = 0.2.
  • Discussion: MQMExact is recommended for medium-sized problems with smaller state spaces, whereas MQMApprox is recommended for larger state spaces with more data.MQMExact remains manageable for relatively large problems, but MQMApprox reduces computational demands through approximation.

6. CONCLUSION

The paper develops Pufferfish mechanisms for correlated data and presents robustness and computational results. It frames the work as an initial step toward broader privacy models for emerging correlated-data settings.

  • Contributions: The study provides a mechanism applicable to any Pufferfish instantiation and an efficient mechanism for Bayesian networks.It also derives a Markov-chain version and evaluates it on time-series problems.
  • Future scope: The authors identify privacy for social-network users and sensor-based spatio-temporal information as important directions for future work.They characterize the present work as a first step toward comprehensive privacy analysis for correlated data.
  • Mechanism guarantee: The Wasserstein-mechanism proof establishes privacy by bounding output-probability ratios using a coupling between conditional distributions.The proof selects an optimal coupling and applies properties of the Laplace distribution to obtain the privacy bound.

B. WASSERSTEIN MECHANISM PROOFS

The Wasserstein Mechanism proof uses an optimal coupling of the relevant conditional distributions to control how much outputs can differ across secret values. Laplace-noise properties then yield the required privacy ratio bound.

  • Coupling construction: The proof begins with a coupling achieving the ∞-Wasserstein distance between the two conditional output distributions.The coupling is denoted γ* and is constructed for the secret pair under consideration.
  • Ratio bound: The mechanism proof bounds output-probability ratios by combining the mechanism definition with properties of the Laplace distribution.The argument uses the Wasserstein distance as the relevant bound on paired outputs.
  • Privacy conclusion: The coupling assigns zero mass to pairs farther apart than the Wasserstein threshold, enabling the final bound on the ratio.An analogous argument handles the reverse ratio, completing the privacy proof.

B.1 Comparison with Group DP

The comparison with group differential privacy relates Pufferfish sensitivity to ∞-Wasserstein distance. Shared-mixture structure preserves the maximum component distance, yielding a group-sensitivity bound and a Laplace-noise guarantee.

  • Sensitivity: The global group sensitivity is the maximum query change over neighboring datasets differing within any one group.The paper defines ∆GkF per group and ∆GF as the maximum across groups.
  • Noise guarantee: Adding Laplace noise with scale ∆GF/ϵ to query F provides ϵ-group differential privacy.This is the standard group-DP consequence stated alongside the comparison.
  • Framework correspondence: A group-DP framework partitions records into groups whose cross-group variables are independent under every distribution in Θ.The corresponding Pufferfish secrets vary individual components within this framework.
  • Comparison result: The Wasserstein noise parameter satisfies W ≤ ∆GF for the corresponding group-DP framework.This connects the Pufferfish mechanism’s noise requirement to ordinary group sensitivity.
  • Mixture lemma: For shared-weight mixtures, ∞-Wasserstein distance is at most the maximum component distance.The proof constructs a coupling by mixing component couplings with the same weights.

C.1 General Properties

The general-properties analysis bounds privacy for multiple noisy queries by combining per-query likelihood ratios under a shared active Markov Quilt. The resulting bound depends on the number of queries and the quilt’s influence score.

  • Joint-query analysis: The proof analyzes the joint output probability of multiple queries Fk(X) + Zk under two secret values.It conditions on quilt and non-quilt variables before comparing the two secret-conditioned distributions.
  • Ratio simplification: The conditional distributions of the remaining variables integrate to one, simplifying the likelihood-ratio calculation.This isolates the contribution of query changes and conditional dependence to the privacy bound.
  • Noise calibration: Each query’s change is controlled by its Lipschitz coefficient and the size of the non-quilt variables.The active quilt determines the lower bound on the Laplace scale used for each query.
  • First ratio: The first likelihood ratio is bounded by the product of per-query terms involving ϵ and the quilt influence score.The displayed bound is Πk e^(ϵ−eΘ(XQ|Xi)).
  • Composition: Combining the two likelihood-ratio bounds yields an overall privacy guarantee of e^(Kϵ) for K queries.The second ratio contributes the opposing quilt-influence term, which cancels in the combined bound.

C.2 Markov Chains

This section analyzes Markov quilts for Bayesian-network correlations represented by Markov chains, deriving bounds that support efficient privacy computation. It specializes the analysis to irreducible, aperiodic chains and uses mixing properties to bound quilt influence and score.

  • Markov Quilts: Markov quilts partition a chain around Xi into quilt nodes XQ and local nodes XN, with remaining nodes conditionally independent of Xi.The analysis considers quilts with nodes on the left, right, or both sides of Xi.
  • Markov Quilts: For two-sided quilts, replacing XQ with its nearest nodes {Xi−a, Xi+b} does not increase the score, while the intervening nodes form XN.The proof uses conditional independence on each side of Xi and lower-bounds the local-node count by a + b − 1.
  • Markov Quilts: For one-sided quilts, the same reduction applies: retaining the nearest quilt node preserves the relevant influence while minimizing the corresponding local-node region.The left-only and right-only cases are treated symmetrically.
  • Mixing Bounds: For irreducible, aperiodic Markov chains, the influence bound uses the chain’s mixing parameter gΘ and decays with separation as Δt = exp(−tgΘ/2).The bound also depends on the minimum stationary probability πmin.
  • Score Bounds: A middle-node quilt with endpoints at distance a∗ bounds every node’s score, yielding maxj∈{1,...,T} σj ≤ C/ϵ.The proof selects X⌈T/2⌉ and uses Lemma 4.8 together with the definition of a∗.

C.3 Fast MQMApprox

This section shows that MQMApprox can transfer a low-score interior quilt across chain positions and handle boundary nodes with one-sided quilts. The resulting search is bounded by the interior optimum.

  • Score Propagation: If an interior node achieves its minimum score with a two-sided quilt, every node has score no greater than that interior score.Interior nodes reuse the same offsets, while boundary nodes use one-sided quilts with no larger local-node sets.
  • Interior Quilt: A central quilt with radius a∗ has score at most (4a∗−2)/ϵ when T ≥ 8a∗.The argument compares it against quilts whose local-node cardinality is at least 4a∗−2.
  • Search Restriction: For sufficiently long chains, an optimal quilt can therefore be restricted to the two-sided form {Xi−a, Xi+b} with a + b ≤ 4a∗.Lemma C.4 then extends the central-node bound to all positions.

C.4 MQMExact Optimization

This section accelerates MQMExact when the distribution class factors into arbitrary initial distributions and a set of transition matrices. The optimization then searches over transition matrices rather than a grid over the full parameter space.

  • Distribution-Class Structure: MQMExact is expedited when Θ = ∆k × P, where ∆k is the probability simplex over k initial states and P is a set of transition matrices.The class contains tuples combining an initial distribution q with a transition matrix P.
  • Optimization: For each transition matrix P, the maximum over initial distributions is attained by a point-mass distribution q = ey∗.The maximizing state y∗ is selected by the largest relevant transition probability.
  • Computational Consequence: The procedure therefore iterates over transition matrices P instead of grid-searching over Θ, improving computational efficiency.This removes the need to enumerate the full product space of initial distributions and transition matrices.
Loading 1603.03977v3…