PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower bounds in differential privacy

Anindya De

arXiv:1107.2183v2cs.CRcs.CC

TL;DR

The paper addresses how much noise is needed to preserve different privacy guarantees across varying query classes and database settings. It develops lower bounds and comparisons among these settings. It finds that approximate differential privacy can require less distortion and provide weaker information protection than pure differential privacy, even when δ is negligible.

  • Problem

    Existing lower bounds vary with database size, universe size, privacy guarantee, and query arity, motivating stronger and more unified bounds.

    Source: §1 · p. 2

  • Method

    The paper combines prior lower-bound techniques and uses a characterization of approximate differential privacy to derive noise bounds across query classes and privacy settings.

    Source: §1 · pp. 2, 4

  • Results

    Even when δ is negligible in database size, (ε, δ)-differential privacy is weaker in mutual information and requires less distortion than (ε, 0)-differential privacy.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The bounds strengthen and unify results across database size, universe size, privacy level, and query arity.

    Source: §1 · p. 2

    The approximate differential privacy lower bounds in this section consider bit-vector databases with universe size equal to database size.

    Source: §4 · p. 12

Abstract

from arXiv · show

This is a paper about private data analysis, in which a trusted curator holding a confidential database responds to real vector-valued queries. A common approach to ensuring privacy for the database elements is to add appropriately generated random noise to the answers, releasing only these {\em noisy} responses. In this paper, we investigate various lower bounds on the noise required to maintain different kind of privacy guarantees.

1 Introduction

The paper strengthens noise lower bounds across query classes and privacy guarantees, including distinctions between counting and arbitrary low-sensitivity queries and between pure and approximate differential privacy. It also examines information leakage, attribute privacy, and blatant non-privacy.

  • Arbitrary low-sensitivity non-counting queries require more distortion than counting queries to maintain differential privacy.Source: §1 · p. 2
  • (ε, δ)-differential privacy requires less distortion than (ε, 0)-differential privacy, even when δ is negligible in database size.Source: §1 · p. 2
  • (ε, δ)-differential privacy is much weaker than (ε, 0)-differential privacy in mutual information between the mechanism transcript and database, even for negligible δ.Source: §1 · p. 2
  • For non-counting low-sensitivity queries, the paper gives tight noise lower bounds for pure differential privacy by combining techniques from and.Source: §1 · p. 4
  • The paper simplifies and makes unconditional the counting-query lower bounds of, removing their fractional-database assumption.Source: §1 · p. 4
  • The ℓ-way-marginal attack can violate attribute privacy despite a constant fraction of responses having wild noise, strengthening [KRSU10].Source: §1 · p. 4
  • Lower bounds for (ε, δ)-differential privacy use a characterization from to connect insufficient noise to blatant non-privacy.Source: §1 · p. 4
  • For some η > 0, a counting query with distortion o(n/d) on at least 1/2 + η of its answers permits recovery of a database differing in o(n) entries.Source: §1 · pp. 4–5

2 Lower bound by volume arguments

The section derives noise lower bounds for arbitrary low-sensitivity queries and uses them to distinguish query classes and privacy guarantees. It also contrasts the information revealed by pure and approximate differential privacy.

2 Lower bound by volume arguments

  • If 2s databases of size at most n have pairwise ℓ1 distance ≤Δ and F answers separated by ≥η in ℓ∞, any ε-DP mechanism must add noise η/2 when Δ≤(s−1)/ε.Source: §2 · p. 5

2.1 Linear lower bound for arbitrary queries

  • Any ε-differentially private mechanism needs Ω(min{d/ε, k/ε}) noise for some query when 0<ε≤1/40 and n≥min{k/ε, d/ε}.The paper also gives a bound for ε>1 and explains that the bounds are tight up to constants when k=O(d).Source: §2.1 · pp. 5–6

Consequences of the linear lower bound

  • For k=d and n=k/ε, some non-counting queries require Ω(n) noise, while counting queries admit ˜O(n^{2/3}) noise.The section also separates pure privacy from approximate privacy: for δ=2^{-o(n)}, approximate privacy can use o(n) noise where pure privacy requires Ω(n).Source: Consequences of the linear lower bound · pp. 7–8

2.2 Information loss in differentially private protocols

  • For δ=2^{-o(n)}, approximate privacy can reveal mutual information as large as n(1−2η), whereas pure privacy bounds it by 3εn.The pure-privacy bound is attributed to; the approximate-privacy result applies for suitable constants and δ≥2^{-C(ε,η)n}.Source: §2.2 · pp. 8–10

3 Lower bound on noise for counting queries

This section establishes noise lower bounds for counting queries without relying on a smooth extension of mechanisms to fractional databases. The bounds match the stated scale for database size O(k/ε).

3 Lower bound on noise for counting queries

  • The proof removes Hardt and Talwar's smooth-extension assumption, which requires extending mechanisms from integral databases to fractional ones.The paper notes that such an extension with similar privacy guarantees is not known to always exist.Source: §3 · pp. 10–11
  • Combinatorial-design constructions produce separated integral databases, which are converted into counting queries and then fed into the volume lower-bound argument.The construction uses databases whose entries are either 0 or a fixed integer a.Source: §3 · pp. 10–11
  • Some counting query requires Ω(min{k/ε, k log(d/k)/ε}) noise for ε-differential privacy, with database size n=O(k/ε).The bound also holds for k random queries.Source: §3 · pp. 10–11

4 Lower bounds for approximate differential privacy

The section proves noise lower bounds for approximate differential privacy using a connection between private mechanisms and unpredictable sources. For bit-vector databases, sufficiently accurate answers to a linear number of counting queries violate approximate privacy.

4 Lower bounds for approximate differential privacy

  • For every positive δ, the section gives distortion lower bounds for (ε,δ)-differential privacy, stated to be tight when ε and δ are constant.The proof uses a characterization from linking private mechanisms to unpredictable sources.Source: §4 · pp. 12–13
  • On bit-vector databases, answering at least 1/2+γ of k=αn counting queries with at most η√n noise with probability at least 3δ is not (ε,δ)-differentially private.Here α, γ, and η are positive constants, and the theorem assumes 0<δ<1/20.Source: §4 · p. 12
  • For k=αn counting queries on bit-vector databases, any mechanism adding o(√n) noise is not (ε,δ)-differentially private when ε>0 and δ<1/20.The section explicitly restricts this result to databases in {0,1}^n.Source: §4 · p. 12

5 LP decoding, Euclidean sections and hardness of releasing ℓ-way marginals

The section connects LP decoding to Euclidean sections to show privacy attacks can tolerate a constant fraction of arbitrarily noisy answers. Applied to ℓ-way marginals, it yields attribute non-privacy even when most queries have noise o(√n).

5 LP decoding, Euclidean sections and hardness of releasing ℓ-way marginals

  • The attack formulates database recovery as a linear program that seeks a database consistent with the noisy query answers.The query matrix has entries in [−1, 1] so the query coordinates are 1-Lipschitz.Source: §5 · p. 14

Correctness of the LP decoding

  • When the query matrix has a Euclidean-section range and minimum singular value σ, LP decoding estimates the database within o(d) in ℓ1 despite a fixed fraction of arbitrary errors.The remaining coordinates must have error α=o(σ).Source: Correctness of the LP decoding · p. 15

5.1 Releasing ℓ-way marginals privately

  • For ℓ-way marginals, noise o(√n) on at least 1−γ of queries still permits attribute non-privacy, and an efficient attack uses LP decoding.The result applies under the theorem’s stated parameter conditions.Source: §5.1 · pp. 17, 19
  • LP decoding improves on the earlier matrix-inversion attack because it can withstand a constant fraction of answers with wild noise.The proof combines the LP-decoding technique with a Euclidean-section condition; Rudelson’s result supplies a relevant bound for ℓ-way marginals.Source: §5.1 · pp. 18–19

6 Noise lower bounds for blatant non-privacy

This section studies noise lower bounds for preventing blatant non-privacy when answering random counting queries. It considers a smaller-universe setting and states that preventing blatant non-privacy there requires much larger noise than when the universe and database have equal size.

6 Noise lower bounds for blatant non-privacy

  • The section’s lower-bound question concerns noise needed to prevent blatant non-privacy for random counting queries.Dinur and Nissim had shown blatant non-privacy for O(n log^2 n) subset-sum queries with o(√n) noise.Source: §6 · p. 19
  • When the universe is smaller than the database, preventing blatant non-privacy requires much larger noise than in the equal-size setting.Earlier results considered a universe the same size as the database, namely n.Source: §6 · p. 20
  • The proof describes two attack algorithms, and the first can be made efficient using linear programming.The authors leave both algorithms inefficient in their presentation for simplicity.Source: §6 · p. 20

A Construction of databases with large differences

This appendix constructs sets of databases with large pairwise differences, supporting the lower-bound arguments. It gives constructions for different parameter regimes, using error-correcting codes and combinatorial designs.

A Construction of databases with large differences

B Large deviation of Rademacher sums from their mean

This appendix develops a large-deviation bound for Rademacher sums and applies it in the paper’s proofs. Its argument uses a lower bound on a K-functional, established by considering alternative sizes of the approximating vector.

B Large deviation of Rademacher sums from their mean

  • The appendix’s central result concerns large deviations of mean-zero Rademacher sums from their mean.Theorem B.1 assumes independent, unbiased ±1 variables and nonnegative coefficients.Source: B Large deviation of Rademacher sums… · p. 25
  • The proof invokes Montgomery-Smith’s result on large deviations of Rademacher sums.The appendix introduces the theorem as an ingredient for proving Theorem B.1.Source: B Large deviation of Rademacher sums… · pp. 25–26
  • A lower bound on K(y,t) is proved by splitting according to whether the minimizing vector has large ℓ2 norm or small ℓ1 norm.In the small-ℓ2 case, Cauchy–Schwarz bounds its ℓ1 norm by n/2, yielding an ℓ1-distance bound by the triangle inequality.Source: B Large deviation of Rademacher sums… · p. 26

C Concentration of measure for the sum of squares of Gaussians

The section proves a concentration result for the sum of squares of k iid N(0, σ) variables, motivated by the authors’ inability to find a usable existing result.

Related papers

Loading 1107.2183v2…