PaperlayerView exact revision on arXiv

Source-linked AI summary

Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies

Xi He, Ashwin Machanavajjhala, Bolin Ding

arXiv:1312.3913v5cs.DB

TL;DR

Differential privacy does not fully span the privacy-utility trade-off, especially when protection is too strong for some properties or correlations enable inference. Blowfish extends differential privacy with policies specifying secrets and public constraints, formalizes the framework, and develops mechanisms for several workloads. Under reasonable policies, the paper reports improved utility, including more accurate mechanisms for histograms and range queries, while also addressing count constraints.

  • Problem

    Differential privacy provides limited flexibility when some individual properties need less protection and may not prevent disclosure from publicly known correlations in the data.

  • Method

    Blowfish extends differential privacy with policies specifying sensitive information to protect and deterministic constraints representing adversarial knowledge about the database.

  • Results

    Under reasonable policies, Blowfish mechanisms improve utility for k-means clustering, histograms, and range queries, including ordered hierarchical mechanisms more accurate than the best known differentially private mechanisms for these workloads.

  • Takeaways & Limitations

    Policy-specific privacy definitions provide additional tuning knobs for customizing protected information and limiting attacks that exploit auxiliary knowledge.

  • Takeaways & Limitations

    Exact calculation of policy-specific sensitivity remains hard for general policy graphs, although several practical scenarios are tractable.

Abstract

from arXiv · show

Privacy definitions provide ways for trading-off the privacy of individuals in a statistical database for the utility of downstream analysis of the data. In this paper, we present Blowfish, a class of privacy definitions inspired by the Pufferfish framework, that provides a rich interface for this trade-off. In particular, we allow data publishers to extend differential privacy using a policy, which specifies (a) secrets, or information that must be kept secret, and (b) constraints that may be known about the data. While the secret specification allows increased utility by lessening protection for certain individual properties, the constraint specification provides added protection against an adversary who knows correlations in the data (arising from constraints). We formalize policies and present novel algorithms that can handle general specifications of sensitive information and certain count constraints. We show that there are reasonable policies under which our privacy mechanisms for k-means clustering, histograms and range queries introduce significantly lesser noise than their differentially private counterparts. We quantify the privacy-utility trade-offs for various policies analytically and empirically on real datasets.

1. INTRODUCTION

Blowfish extends differential privacy with policies that tune what individual information is secret and what data constraints adversaries may know. The paper formalizes these policies and develops mechanisms that improve utility under selected policies while addressing correlation-based attacks.

  • Motivation: Differential privacy offers a privacy-utility knob, but it can be too restrictive for some applications and insufficient against correlations in the data.Public constraints can let attackers infer sensitive information even when noisy answers alone do not disclose it.
  • Blowfish privacy: Blowfish policies specify both sensitive information to protect and publicly known constraints about the database.These two policy components respectively support customized protection and resistance to attacks leveraging correlations.
  • Contributions: The paper formalizes sensitive information specifications, constraints, policies, and Blowfish privacy, focusing particularly on count constraints.It also considers realistic examples of sensitive information specifications.
  • Contributions: The paper adapts differential privacy mechanisms for Blowfish policies and uses k-means clustering to illustrate accuracy gains from weaker sensitive-information specifications.The contribution specifically targets policies that protect fewer individual properties.
  • Contributions: For cumulative histograms and range queries, the ordered mechanism and ordered hierarchical mechanism are analytically and empirically more accurate than the best known differentially private mechanisms under reasonable specifications.The evaluation uses experiments on real data.
  • Contributions: The paper studies noise calibration for policies expressing count constraints and applies it in several practical scenarios.This extends the policy framework beyond unconstrained settings.

2. NOTATION

The paper fixes a database model and neighboring-dataset assumption, then defines differential privacy, global sensitivity, the Laplace mechanism, and histogram accuracy using mean squared error.

  • Database model: Each database contains n tuples from a categorical domain formed as the cross product of m attributes, with one tuple corresponding to each unique individual.The tuple identifier is denoted t.id.
  • Database model: The analysis assumes the adversary knows the set of individuals in advance, so neighboring databases differ in one tuple value rather than by additions or deletions.The paper notes that this assumption can be relaxed for other differential privacy notions.
  • Core definitions: Global sensitivity is the largest L1 difference between query outputs on databases differing in one tuple.It is denoted S(f) for a function f.
  • Core definitions: The Laplace mechanism releases f(D) plus independent noise, with each component drawn using scale S(f)/ϵ.The noise magnitude therefore depends on the query’s global sensitivity and privacy parameter.
  • Histograms: A histogram query counts tuples in each partition, and its global sensitivity is 2, so Laplace noise uses parameter 2/ϵ per component.Mean squared error is the paper’s accuracy measure for histogram answers.
  • Histograms: For histograms, the Laplace mechanism’s expected mean squared error is 8|T|/ϵ^2.This follows from adding Laplace(2/ϵ) noise to each complete-histogram component.

3. POLICY DRIVEN PRIVACY

Blowfish represents privacy through secrets, discriminative pairs, and a policy describing both protected distinctions and adversarial knowledge. Its sensitive-information specifications include full-domain, attribute, partitioned, and distance-threshold forms, while deterministic constraints restrict possible databases.

  • Policy framework: A policy specifies which information must remain secret and what background knowledge an attacker may possess about correlations in the data.This policy becomes the input to the Blowfish privacy definition.
  • Sensitive information: Blowfish uses arbitrary propositional statements as secrets and discriminative pairs to identify mutually exclusive properties that an adversary must not distinguish.The paper focuses on secrets about single individuals, although it notes that secrets can also concern sets of individuals.
  • Sensitive information: Full-domain and attribute specifications require protection across all domain values or across values of each attribute, respectively.These specifications define which changes in an individual’s value are treated as sensitive.
  • Sensitive information: Partitioned sensitive information allows an adversary to distinguish partitions but not values within a partition, supporting coarse-grained release such as location grids.This is a paper-specific example of weakening protection for selected distinctions.
  • Sensitive information: Distance-threshold sensitive information protects distinctions between domain values whose distance is at most a threshold, while allowing farther-apart points to be distinguished better.The specification uses an inherent distance metric on the domain.
  • Sensitive information: The discriminative secret graph generalizes these specifications by connecting domain values that an adversary must not distinguish.Complete, attribute, partition, and distance-threshold graphs instantiate this abstraction.
  • Scope assumptions: The paper assumes the same discriminative-pair set for all individuals and restricts its main treatment to secrets about single individuals.It notes that individual-specific discriminative pairs are possible in principle.
  • Auxiliary knowledge: Public deterministic constraints restrict possible databases to IQ, allowing Blowfish to model auxiliary knowledge such as count-query and marginal constraints.A database satisfies Q when it belongs to IQ.

4. BLOWFISH PRIVACY

Blowfish privacy extends differential privacy by making neighboring datasets depend on a policy’s secret pairs and known constraints. It supports composition and connects to Pufferfish while exposing limitations for general constrained parallel releases.

  • Blowfish Privacy: Blowfish defines policy-dependent neighbors using discriminative secret pairs and constraints, rather than relying only on arbitrary one-tuple changes.Neighbors must satisfy the policy’s constraints, differ in a discriminative secret pair, and be minimally different under those criteria.
  • Blowfish Privacy: For policies without constraints, Blowfish neighbors change one tuple along an edge in the secret graph, while differential privacy uses a complete graph.Thus, Blowfish can distinguish protections between values according to their graph distance.
  • Composition: Sequential composition holds with additive privacy loss: mechanisms satisfying ϵ1- and ϵ2-Blowfish privacy together satisfy (ϵ1 + ϵ2)-Blowfish privacy.The result applies when the mechanisms use independent randomness.
  • Composition: Parallel composition achieves max_i ϵ_i privacy under cardinality constraints, but general constraints require each constraint to affect only its corresponding data subset.Without this separation, neighboring datasets can differ across multiple disjoint subsets, invalidating the same guarantee.
  • Relation to Other Definitions: Without constraints, Blowfish is equivalent to Pufferfish under independent-tuple adversary beliefs; with constraints, it is necessary for the corresponding constrained Pufferfish instantiation.The paper conjectures sufficiency in the constrained case.
  • Relation to Other Definitions: Restricted sensitivity can account for constraints but may fail to prevent sensitive disclosure, so Blowfish also incorporates discriminative secret pairs.The example IQ = {0^n, 1^n} shows that constant noise can leave the two possible databases distinguishable.

5. BLOWFISH WITHOUT CONSTRAINTS

Without constraints, Blowfish calibrates noise to policy-specific sensitivity, which is never larger than global sensitivity and can improve utility for selected tasks. The benefit depends on the sensitive-information policy and workload.

  • Policy-Specific Sensitivity: Policy-specific sensitivity defines the maximum query change over policy neighbors, and Laplace noise calibrated to it ensures Blowfish privacy.The mechanism adds independent Laplace noise with scale S(f, P)/ϵ.
  • Policy-Specific Sensitivity: S(f, P) is never larger than global sensitivity S(f), so Laplace mechanisms can provide better utility under Blowfish policies.The improvement follows from calibrating noise to the restricted set of policy neighbors.
  • Examples: For a weighted sum, G_full yields sensitivity (b − a) · (max_i w_i), whereas G_d,θ yields θ · (max_i w_i), which can be much smaller when θ ≪ (b − a).The smaller sensitivity arises from limiting discriminative changes through the distance-based secret graph.
  • Examples: Under partitioned sensitive information, the histogram of the partition or any coarser partition has policy-specific sensitivity 0 and can be released without noise.This is a policy-specific example of improved utility.
  • Applications: For most reasonable unconstrained histogram policies, policy-specific sensitivity remains 2, equal to global sensitivity, so accuracy cannot improve significantly.Partitioned sensitive information is identified as the exception.
  • Applications: Blowfish mechanisms can improve utility over differential privacy for k-means clustering and cumulative histogram workloads without constraints.The clustering gain comes from reducing intermediate-query sensitivity, while cumulative histograms use novel query-answering strategies.

6. K-MEANS CLUSTERING

Blowfish policies reduce the sensitivity of k-means queries by tailoring protected secrets and discriminative graphs, improving accuracy over differential privacy in evaluated settings. Experiments show the gains depend on dimensionality, dataset size, and policy structure.

  • Private k-means mechanism: K-means privately releases cluster sizes and point sums, with qsum sensitivity up to 2 · d(T) under differential privacy.The qsize sensitivity is 2, while changing one tuple can alter two cluster sums by at most the domain diameter.
  • Policy-specific sensitivity: Blowfish policies make qsum sensitivity smaller than under differential privacy for attribute, distance, and partition discriminative graphs.The policy-specific sensitivities are bounded by graph- or partition-dependent distances, while qsize remains 2.
  • Empirical utility: Laplace error can reach 100 times the non-private objective, whereas Blowfish objective values remain below 5 times the non-private result.This pattern is reported across the evaluated datasets and policies, although private-mechanism error need not decrease monotonically as θ decreases.
  • Policy and dataset effects: Attribute-graph Blowfish reduces error by an order of magnitude for skin01 and synthetic data, but yields little gain for the larger 2D Twitter dataset.The reported gains are associated with higher dimensionality and smaller dataset size in the former datasets.
  • Policy and dataset effects: Partition-based Blowfish objectives are smaller than Laplace objectives, and partition|120000 permits exact clustering because both query sensitivities are 0.The partition|120000 policy protects locations within each original grid cell.
  • Empirical utility: Blowfish policies attain k-means objective values close to 10 times smaller than the Laplace mechanism in some cases.The improvement gap increases with dimensionality and decreases with data size.

7. CUMULATIVE HISTOGRAMS

The paper develops ordered mechanisms for cumulative histograms and range queries under Blowfish policies, exploiting ordered or hierarchical structure to reduce error. Ordered mechanisms outperform differential privacy for restrictive policies, while the hybrid ordered hierarchical mechanism remains no worse than the standard hierarchical mechanism.

  • Cumulative histograms and range queries: Cumulative histograms support range queries, quantiles, histograms, and index construction, motivating mechanisms tailored to ordered domains.A range query is obtained from at most two noisy cumulative counts.
  • Ordered Mechanism: Under the line-graph policy Gd,1, cumulative-histogram sensitivity is 1, enabling the Ordered Mechanism to add Laplace noise calibrated to that sensitivity.Only adjacent domain values may form a secret pair under this policy.
  • Constrained inference: Sparse cumulative histograms can benefit from constrained inference because their number of distinct cumulative counts p is much smaller than |T|.The resulting error is O(√(p log^3 |T|/ϵ^2)), compared with hierarchical release error O(|T| log^3 |T|/ϵ^2).
  • Ordered Mechanism: For line-graph policies, Ordered Mechanism range-query error is independent of |T| and lower than hierarchical Laplace error, which scales with log^3 |T|.The paper also notes an SVD lower bound against O(1/ϵ^2) error for every range query under differential privacy.
  • Ordered Hierarchical Mechanism: For general Gd,θ, Ordered Mechanism error remains asymptotically smaller than differential privacy for small θ, but becomes comparable near log |T| and worse at θ = O(log^3/2 |T|).The threshold reflects the privacy-utility trade-off induced by the graph distance parameter.
  • Ordered Hierarchical Mechanism: The Ordered Hierarchical Mechanism combines ordered and hierarchical structures and always has error less than or equal to the hierarchical mechanism for all θ.Its empirical evaluation measures mean squared error for random range queries on adult and Twitter datasets.

8. BLOWFISH WITH CONSTRAINTS

Under general constraints, policy-specific sensitivity is hard to compute, but sparse count constraints enable analytical sensitivity bounds and practical histogram-release mechanisms. The policy graph reduces sensitivity analysis to graph structure and yields specialized results for marginals and range queries.

  • General constraints: NP-hardness applies to testing whether policy-specific sensitivity is positive, including for complete histograms and general count query constraints.The hardness extends to checking whether sensitivity is at most a threshold.
  • Sparse count constraints: Sparse knowledge requires each secret pair to lift at most one count query and lower at most one count query.Lift means a query changes from false to true; lower means it changes from true to false.
  • Policy graph: The policy graph contains count-query vertices plus v+ and v−, with edges encoding how secret pairs lift and lower queries.Its key structural quantities are the longest simple cycle α(GP) and longest v+-to-v− path ξ(GP).
  • Sensitivity characterization: For sparse constraints, histogram sensitivity is characterized by twice the larger of α(GP) and ξ(GP), under the theorem’s stated equality condition.The resulting upper bound is S(h, P) ≤ 2 max{|Q|, 1}.
  • Histogram release: Laplace(2 max{|Q|, 1}/ϵ) noise suffices for releasing a complete histogram with (ϵ, P)-Blowfish privacy under sparse constraints.This calibration may not be necessary in every instance.
  • Applications: For practical policies, exact graph calculations become tractable for one marginal, disjoint attribute marginals, and disjoint range queries.The corresponding sensitivities include 2 size(C), 2 max_i size(Ci), and 2(maxcomp(Q)+1).

9. CONCLUSIONS

The conclusion presents Blowfish privacy as a policy-based framework for tuning privacy and utility. It reports improved utility under weaker sensitive-information specifications and analytical noise calibration for count constraints.

  • Framework: Blowfish privacy lets users specify both sensitive information to protect and database knowledge available to adversaries.These policy components provide the framework’s tuning interface.
  • Utility: Reasonable policies with weaker privacy specifications improve utility for k-means clustering, cumulative histograms, and range queries.For cumulative histograms and range queries, the paper develops strategies reported as more accurate than differentially private mechanisms.
  • Count constraints: The paper studies noise calibration for Blowfish policies with count constraints when publishing histograms and applies the general result to practical scenarios.The conclusion also identifies policy customization as a way to limit attacks using auxiliary knowledge.

A. PROOF OF THEOREM 7.1

The proof characterizes histogram sensitivity through cycles and endpoint paths in the policy graph. It establishes an upper bound by decomposing excessive differences and a matching lower bound by constructing neighboring databases.

  • Sensitivity definition: Histogram sensitivity is the maximum L1 distance between histogram outputs over policy-neighboring databases.This definition is used as the target quantity in the proof.
  • Upper bound: Any neighboring pair differs in at most max{α(GP), ξ(GP)} tuple changes, yielding S(h, P) ≤ 2 max{α(GP), ξ(GP)}.The proof constructs a smaller witness database when the tuple difference exceeds this graph bound.
  • Upper bound: The difference graph is Eulerian except possibly at v+ and v−, so an oversized graph contains a proper simple cycle or endpoint path.Removing that substructure produces the smaller witness needed for the upper-bound argument.
  • Lower bound: For every simple cycle or v+-to-v− path, the proof constructs neighboring databases whose differing tuple count equals that structure’s length.This establishes the matching lower bound under the theorem’s condition.
  • Conclusion: Combining both directions gives S(h, P) = 2 max{α(GP), ξ(GP)} when the stated equality condition holds.The equality follows from the upper and lower bounds together.

B. PROOF OF THEOREM 4.1

The proof establishes privacy for sequentially releasing two mechanisms by applying each mechanism’s Blowfish guarantee conditionally and multiplying the resulting bounds. The privacy parameters therefore add.

  • Sequential composition: The first mechanism’s output becomes an input to the second mechanism during sequential release.The second mechanism is evaluated using both the original dataset and the first output.
  • Privacy bound: Applying the first mechanism’s guarantee and the conditional second guarantee bounds the joint output probability by e^ϵ1+ϵ2 times the neighboring-dataset probability.The argument applies to every neighboring database pair and output sequence.
  • Privacy bound: Sequential composition of mechanisms satisfying (ϵ1, P)- and (ϵ2, P)-Blowfish privacy satisfies an overall bound with parameter ϵ1 + ϵ2.The proof derives this by multiplying the two exponential privacy factors.

C. PROOF OF THEOREM 4.2-4.3

The proof sketch analyzes neighboring databases under a cardinality constraint or disjoint constraint subsets. It identifies a unique subset whose values differ while all other subset intersections remain unchanged.

  • The proof considers every neighboring database pair in N(P) satisfying a cardinality constraint or disjoint constraint subsets.
  • For each such pair, only one subset of ids, S_i*, has different values between the databases.
  • All other subset intersections remain equal across the neighboring databases.
Loading 1312.3913v5…