PaperlayerView exact revision on arXiv

Source-linked AI summary

On Sampling, Anonymization, and Differential Privacy: Or, k-Anonymization Meets Differential Privacy

Ninghui Li, Wahbeh Qardaji, Dong Su

arXiv:1101.2604v2cs.CR

TL;DR

The paper asks what formal privacy guarantee k-anonymization provides and how privacy analysis can exploit uncertainty about dataset membership. It uses random sampling to connect safe k-anonymization with differential privacy and to study privacy amplification and composition. The results establish privacy benefits from sampling while identifying non-composability as a key boundary.

  • Problem

    The paper asks whether k-anonymization provides formal privacy guarantees and whether adversary uncertainty about the dataset can support a useful relaxation of differential privacy.

  • Method

    The paper analyzes safe k-anonymization and differential privacy under a preceding random-sampling step.

  • Results

    Random sampling amplifies differential privacy, while safe k-anonymization after sampling satisfies (ε, δ)-differential privacy with reasonable parameters.

  • Takeaways & Limitations

    Sampling can increase the privacy budget and enable safe k-anonymization, but using these benefits requires attention to fresh sampling and composition limits.

  • Takeaways & Limitations

    Privacy notions that exploit adversary uncertainty appear not to compose, and strengthened k-anonymity alone does not prevent re-identification attacks.

Abstract

from arXiv · show

This paper aims at answering the following two questions in privacy-preserving data analysis and publishing: What formal privacy guarantee (if any) does $k$-anonymization provide? How to benefit from the adversary's uncertainty about the data? We have found that random sampling provides a connection that helps answer these two questions, as sampling can create uncertainty. The main result of the paper is that $k$-anonymization, when done "safely", and when preceded with a random sampling step, satisfies $(ε,δ)$-differential privacy with reasonable parameters. This result illustrates that "hiding in a crowd of $k$" indeed offers some privacy guarantees. This result also suggests an alternative approach to output perturbation for satisfying differential privacy: namely, adding a random sampling step in the beginning and pruning results that are too sensitive to change of a single tuple. Regarding the second question, we provide both positive and negative results. On the positive side, we show that adding a random-sampling pre-processing step to a differentially-private algorithm can greatly amplify the level of privacy protection. Hence, when given a dataset resulted from sampling, one can utilize a much large privacy budget. On the negative side, any privacy notion that takes advantage of the adversary's uncertainty likely does not compose. We discuss what these results imply in practice.

1. INTRODUCTION

The paper asks what privacy guarantees k-anonymization provides and how to exploit adversary uncertainty, using random sampling to connect these questions. It shows that safe k-anonymization after sampling can satisfy differential privacy, while sampling amplifies privacy for differentially private algorithms but creates composition risks.

  • The paper studies privacy-preserving data use and publishing by trusted curators releasing population statistics or sanitized datasets.
  • k-anonymization has lacked strong privacy guarantees, motivating formal analysis of whether safe variants provide stronger protection.
  • Safe k-anonymization preceded by random sampling provides (ε, δ)-differential privacy with reasonable parameters.
  • The paper links syntactic k-anonymization with algorithmic differential privacy, supporting the idea that hiding in a crowd of k offers privacy guarantees.
  • Random sampling offers an alternative to output perturbation by enabling pruning of results sensitive to changes in individual tuples.
  • Sampling amplifies differential privacy: with sampling probability β, both e^ε − 1 and δ decrease by a factor of β, but uncertainty-based privacy notions are unlikely to compose.For example, sampling with probability 0.1 changes (ln 2 ≈0.69)-DP to overall (ln 1.1 ≈0.095)-DP.

2. DIFFERENTIAL PRIVACY UNDER SAMPLING

The paper defines differential privacy under sampling to exploit uncertainty about dataset membership, then studies its amplification, postprocessing, and composition properties. Sampling can strengthen privacy parameters, but uncertainty-based privacy may fail under composition.

  • Differential privacy requires neighboring datasets to produce output distributions differing by at most a multiplicative factor, with (ε,δ)-DP allowing error probability δ.
  • Non-Composability: Privacy notions that exploit adversary uncertainty may not compose, because separately private outputs can jointly reveal a sensitive predicate.
  • Differential privacy under sampling requires first including each tuple independently with probability β, then applying an algorithm whose sampled-data output satisfies (ε,δ)-DP.
  • Amplification Effect of Sampling: Smaller sampling rates proportionally reduce e^ε−1 and δ, yielding stronger privacy protection under the paper’s theorem.
  • Privacy Properties: An algorithm satisfying (β,ε,δ)-DPS remains private under arbitrary postprocessing, and randomly choosing between two such algorithms preserves the same parameters.

2.6 More Non-Composability

The paper shows that uncertainty from sampling can amplify privacy and support safe k-anonymization, but privacy gains are fragile when additional outputs reduce that uncertainty. This limits uncertainty-based mechanisms primarily to non-interactive publication.

  • More Non-Composability: Combining a sampling-based mechanism with an ε-DP mechanism can reveal a sensitive predicate, despite each mechanism satisfying its respective privacy notion.
  • More Non-Composability: For a 10,000-tuple dataset sampled at β=0.5, the composed mechanism yields event probabilities approximately 0 and 1/4 on neighboring datasets.
  • Practical Implications: The paper therefore advises applying (β,ε,δ)-DPS mechanisms alone, making them unsuitable for interactive multiple-query settings but potentially acceptable for one-time publication.
  • Benefiting from Sampling: Sampling can permit larger privacy budgets for ordinary (ε,δ)-DP mechanisms, while safe k-anonymization can provide sampling-based privacy only once on the same dataset.
  • Benefiting from Sampling: Fresh sampling enables repeated publication because each sampled dataset introduces new uncertainty and can support separate applications of privacy-preserving mechanisms.
  • Safe k-Anonymization: Safe k-anonymization, preceded by random sampling, satisfies (ε,δ)-differential privacy, whereas ordinary methods can leak through extreme tuples.

3.2 Towards “Safe” k-Anonymization

The section argues that dataset-dependent anonymization mappings can undermine the intuition of hiding in a crowd, motivating safe k-anonymization. It then gives a sampling-based differential-privacy guarantee and reports how privacy varies with k, β, ε, and δ.

  • Motivation: Dataset-dependent recoding can expose tuples because a single input tuple may determine the generalized output shared by a crowd.The paper uses an extreme-value example to show why identical output tuples need not imply indistinguishable input tuples.
  • Safe k-Anonymization: Strongly-safe k-anonymization uses a dataset-independent mapping and removes every output value appearing fewer than k times.The algorithm is specified through a mapping function g followed by pruning of underrepresented outputs.
  • Safe k-Anonymization: Strongly-safe k-anonymization alone cannot satisfy (ε, δ)-DP for any δ < 1.The proof constructs neighboring datasets whose outputs have different numbers of a mapped tuple, making one output event have probabilities 1 and 0.
  • Privacy Guarantee: Any strongly-safe algorithm preceded by sampling satisfies (β, ε, δ)-DPS for 0 < β < 1, ε ≥ −ln(1 − β), and δ = d(k, β, ε).The function d links the privacy parameters ε and δ with the data-quality parameters k and β.
  • Parameter Relationships: When β = 0.2 and ε = 2, increasing k by 10 roughly decreases δ by 10^-5.The reported relationship is close to exponential for the examined k values.
  • Parameter Relationships: Decreasing β improves privacy protection, while increasing k and decreasing β create a privacy–utility trade-off.For k = 20, the paper reports dramatic improvement as β decreases; it also examines matched privacy levels when k and β vary.

3.4 ǫ-Safe k-Anonymization

The section relaxes strong safety so the generalization scheme may depend on the dataset without overly depending on any individual tuple. It defines ε-safe anonymization and states its differential-privacy guarantee and parameter relationships.

  • Relaxing Strong Safety: Strong safety is likely to produce low-utility outputs, motivating a dataset-dependent generalization scheme that does not overly depend on one tuple.The paper proposes relaxing strong safety rather than retaining a fixed global recoding scheme.
  • Definition: An ε-safe k-anonymization algorithm is one whose mapping-selection function Am satisfies ε-DP.The paper suggests the exponential mechanism as one way to select a useful generalization scheme privately.
  • Parameter Relationships: For k = 20, Table 2 reports δ for combinations of β and ε, with smaller β improving privacy protection.The table fixes k at 20 and uses each cell to report δ under the corresponding β and ε values.
  • Privacy Guarantee: Any ε1-safe k-anonymization algorithm satisfies (β, ε, δ)-DPS when ε ≥ −ln(1 − β) + ε1 and δ = d(k, β, ε − ε1).The guarantee extends the strongly-safe result by accounting for the privacy loss of selecting the mapping.

4. RELATED WORK

Related work includes weaker data-publishing privacy notions, differential-privacy mechanisms, sampling-based privacy analysis, and frameworks for relaxing differential privacy. The paper positions its approach as input perturbation and emphasizes composability issues.

  • Privacy-Preserving Data Publishing: k-anonymity and related notions such as ℓ-diversity and t-closeness rely on assumptions about adversarial knowledge and attribute roles.The paper notes that weaker notions can be attacked by changing what the adversary knows or seeks to learn.
  • Differential Privacy: Differential privacy has been implemented through global-sensitivity noise, smooth-local-sensitivity noise, the exponential mechanism, and related microdata methods.The paper contrasts these output-perturbation approaches with its sampling-based alternative.
  • Sampling: Prior sampling work found a linear relationship between sampling probability and δ, including an approach that anonymizes before sampling.The paper studies a different ordering in which sampling precedes safe anonymization.
  • Privacy Definitions: Kifer and Lin’s framework identifies Transformation Invariance and the Privacy Axiom of Choice, both satisfied by (β, ε, δ)-DPS.The paper distinguishes its emphasis on composability from that framework’s focus.

5. CONCLUSIONS

The paper connects safe k-anonymization and differential privacy through random sampling, while identifying both the benefits and pitfalls of exploiting sampling-induced uncertainty.

  • Random sampling bridges k-anonymization and differential privacy by creating uncertainty for the adversary.
  • Sampling can increase the privacy budget and error toleration bound in differential privacy.
  • Safe k-anonymization can be used after sampling, but requires fresh sampling not used to answer another query.
  • The paper identifies potential pitfalls in exploiting sampling for private data analysis or publishing.

A. PROOFS

This appendix contains proofs that were omitted from the paper’s main body.

  • The appendix includes proofs not included in the main body.
  • Its contents supplement the paper’s main-body presentation with omitted proofs.
  • The appendix’s stated role is to provide proofs absent from the main text.

A.1 Proof of Theorem 1

The proof establishes privacy amplification by viewing the lower sampling rate as additional sampling before an already differentially private algorithm. It derives the resulting differential-privacy parameters by decomposing sampled outputs according to whether the differing tuple is included.

  • Theorem 1 transfers (β1, ǫ1, δ1)-DPS to (β2, ǫ2, δ2)-DPS for any β2 < β1.The theorem defines ǫ2 through the sampling-rate reduction, with the displayed expression truncated in the passage.
  • Aβ2 is represented as sampling with probability β = β2/β1, followed by applying Aβ1.Because Aβ1 satisfies (ǫ1, δ1)-DP, the proof analyzes the additional sampling step.
  • The proof compares neighboring datasets D and D−t by partitioning sampled outputs according to whether t is absent or present.The absent-tuple case has probability factor 1−β, while the present-tuple case has factor β.
  • The resulting inequalities combine the original privacy bound with sampling probabilities to obtain the new parameters.The proof bounds Z by (1 −β + βe^ǫ1)X + βδ1 and then identifies this with e^ǫ2X + δ2.

A.2 Proof of Theorem 5

Theorem 5 proves that strongly-safe k-anonymization satisfies differential privacy after sampling, under explicit constraints on β and ǫ. The proof bounds bad outcomes by analyzing how often an equivalence class survives suppression with at least k sampled tuples.

  • Any strongly-safe k-anonymization algorithm satisfies (β, ǫ, δ)-DPS for 0 < β < 1 and ǫ ≥ −ln(1 −β).The failure parameter is δ = d(k, β, ǫ), where d is defined in the theorem.
  • The proof models an equivalence class using n matching tuples in D and j sampled matches appearing in the output S.The generalization procedure g determines which tuples match the distinguished tuple t.
  • The theorem’s privacy statement is stronger than the differential-privacy form given in Definition 2.The passage points to an external reference for the relationship between the two definitions.
  • Because classes appearing fewer than k times are suppressed, a surviving class has j ≥ k, while j = 0 is handled separately.The proof verifies the privacy inequality in the j = 0 case using e^-ǫ ≤ 1 −β.
  • The binomial terms use Bernoulli sampling variables, with F(k −1; n−1, β) and F(k −1; n, β) representing lower-tail probabilities.The proof uses the ordering F(k −1; n, β) < F(k −1; n −1, β).
  • The bad-outcome probability is bounded by analyzing cases where j ≥ k and j > γn, with γ = (e^ǫ−1+β) e^ǫ.The analysis compares binomial probabilities across n and uses the threshold n_m separating the relevant cases.

A.3 Proof of Theorem 6

Theorem 6 establishes that any ε1-safe k-anonymization algorithm preceded by sampling satisfies differential privacy under specified parameter conditions. The proof bounds the privacy ratio and the probability that the bound is violated.

  • Theorem statement: Theorem 6 states that any ε1-safe k-anonymization algorithm satisfies (β, ε, δ)-DPS.The parameters must satisfy ε ≥ −ln(1 − β) + ε1, with δ defined as d(k, β, ε − ε1).
  • Proof setup: The proof models sampling as binomial sampling of dataset D with probability β and considers the possible outputs of the anonymization subroutine.For each fixed output g, the proof uses the subroutine’s ε1-differential privacy guarantee.
  • Privacy-ratio bound: The privacy ratio for a fixed output is bounded using j, the number of copies of g(t) in the output dataset S.The proof separately analyzes upper and lower bounds on the ratio.
  • Privacy-ratio bound: e^{−(ε−ε1)} ≤ r(g) ≤ e^(ε−ε1) bounds the ratio r(g), except with probability δ.The violation probability is analyzed through the sampling cases, including j = 0.
Loading 1101.2604v2…