Source-linked AI summary
Concentrated Differential Privacy
Cynthia Dwork, Guy N. Rothblum
TL;DR
The paper addresses how to obtain accurate answers to many database analyses while controlling cumulative privacy loss. It introduces Concentrated Differential Privacy, proves sharper composition and expected-loss results, and shows improved accuracy for Gaussian mechanisms, with scope limitations for algorithms permitting infinite privacy loss.
Problem
Differential privacy supports cumulative privacy accounting, but before this work its bounds were not tight and many computations required very low per-query privacy loss.
Method
The paper introduces Concentrated Differential Privacy, defining privacy through the mean and subgaussian concentration of the privacy loss random variable.
Results
For n counting queries, the Gaussian mechanism uses noise from N(0, n/ε2) per query and achieves (ε(eε−1)/2, ε)-concentrated differential privacy.
Takeaways & Limitations
Concentrated Differential Privacy permits less concern about individual-query loss while providing high-probability bounds for cumulative loss across many computations.
Takeaways & Limitations
Algorithms with some probability δ′ ≤δ of infinite privacy loss are ruled out by concentrated differential privacy, including many but not all Propose-Test-Release algorithms.
Abstract
from arXiv · showhide
We introduce Concentrated Differential Privacy, a relaxation of Differential Privacy enjoying better accuracy than both pure differential privacy and its popular "(epsilon,delta)" relaxation without compromising on cumulative privacy loss over multiple computations.
1 Introduction
The paper introduces Concentrated Differential Privacy, a relaxation designed to improve accuracy for many computations while preserving strong cumulative privacy guarantees. It also sharpens composition and expected-loss bounds and studies group privacy and mechanism-specific limitations.
- A New Relaxation: Concentrated Differential Privacy models privacy loss through its mean and subgaussian concentration, offering high-probability cumulative-loss control under composition.An algorithm is (µ, τ)-CDP when privacy loss has mean µ and centered subgaussian parameter τ.
- Improved Accuracy: The composition of k (µ, τ)-concentrated differential privacy mechanisms is (kµ, kτ)-concentrated differential privacy.This supports cumulative privacy accounting across multiple adaptive computations.
- Improved Accuracy: For n counting queries, the Gaussian mechanism adds independent noise from N(0, n/ε2) to each query and achieves (ε(eε−1)/2, ε)-concentrated differential privacy.When ε = Θ(1), the noise is scaled to O(√
- Group Privacy: For group size s, qualifying concentrated differential privacy mechanisms satisfy (s2·µ, s·τ)-concentrated differential privacy, and this bound is optimal.The result applies under conditions satisfied by pure differential privacy mechanisms and Gaussian noise addition.
- Tight Bounds on Expected Loss: The paper improves by a factor of two the known upper bound on expected privacy loss for any (ε, 0)-differentially private mechanism.The resulting bound is tight and improves the utility/privacy tradeoff in applications of Advanced Composition.
- Limitations: Some (ε, δ)-differentially private algorithms with probability δ′ ≤δ of infinite privacy loss are excluded from concentrated differential privacy.The paper identifies this issue for many, but not all, algorithms in the Propose-Test-Release framework.
2 Preliminaries
The preliminaries introduce divergence measures, differential privacy mechanisms, privacy loss, and subgaussian random variables as the mathematical tools used to analyze privacy.
- The paper introduces subgaussian divergence as a new divergence notion for its concentrated differential privacy analysis.
- KL-divergence measures relative entropy between two random variables, but is undefined when their supports differ.
- Max divergence and approximate divergence provide additional ways to compare distributions, subject to support conditions.
- A database mechanism maps a database to an output, with databases treated as row multisets and adjacency defined by changing one row.
- Differential privacy bounds distributional differences between neighboring databases, while privacy loss records the outcome-specific log probability ratio.
- A τ-subgaussian random variable has Gaussian-like moment-generating-function bounds, implying mean zero, variance at most τ^2, and concentration of sums.
3 Concentrated Differential Privacy: Definition and Properties
Concentrated Differential Privacy (CDP) measures privacy loss through its mean and subgaussian concentration, yielding a relaxation with strong composition properties. The paper relates CDP to differential privacy and characterizes Gaussian mechanisms within this framework.
- Definition: CDP requires the privacy-loss distribution between adjacent databases to have mean µ and centered subgaussian parameter at most τ.The paper defines (µ, τ)-CDP through subgaussian divergence for every adjacent database pair.
- Gaussian Mechanism: The Gaussian mechanism with noise magnitude σ is (τ^2/2, τ)-CDP, where τ = ∆f/σ.Its privacy-loss distribution is Gaussian with expectation (∆f/σ)^2/2 and standard deviation ∆f/σ.
- Gaussian Mechanism: Adding independent N(0, n/ε^2) noise to each query achieves (ε(e^ε − 1)/2, ε)-CDP.For small ε, the paper states that a further relaxation can yield an order-of-magnitude reduction in distortion when further composition is expected.
- Composition: k adaptively chosen CDP mechanisms compose with cumulative parameters formed from the sums of their µ_i values and squared τ_i values.The composition theorem applies to adversarially and adaptively chosen mechanisms and database pairs.
- Relationship to DP: Every ε-differentially private mechanism is also (ε(e^ε − 1)/2, ε)-CDP.The paper improves the expected privacy-loss bound for ε-DP algorithms to roughly ε^2/2 for small ε.
4 Group Privacy
The paper extends concentrated differential privacy from individual records to groups by recursively composing privacy-loss bounds across database differences. Under smallness conditions, the resulting group guarantees are nearly tight up to low-order terms.
- Scope: The group-CDP bounds are asymptotically nearly tight, but tightening them to match known Gaussian and pure-ε mechanisms remains open.The authors identify this comparison as an interesting direction for improving the bounds.
- Theorem: Arbitrary (µ, τ)-CDP mechanisms provide group CDP guarantees for databases differing in s rows.The theorem assumes τ · s · log^3 s is sufficiently small and µ ≤ τ^2/2.
- Theorem: For groups, the privacy-loss expectation is roughly (s·τ)^2/2 and the subgaussian standard is roughly s·τ, up to low-order terms.These bounds are stated under the theorem’s smallness assumptions.
- Proof strategy: The proof recursively combines midpoint databases for pairs differing on 2^m rows and maintains µ_m ≤ τ_m^2/2.The induction uses bounds on both the expected privacy loss and the centered privacy-loss standard.
- Proof strategy: The recursion yields τ_{m+1} ≤ (2^{m+1} · τ) + α · (2^{m+1} · (m + 1)^3 · τ)^1.5.The paper states that this implies the claimed bound on τ_log s.