Differential privacy composition theorems

Differential privacy composition theorems are mathematical tools used in differential privacy to analyze and bound the accumulated privacy loss when multiple differentially private mechanisms are applied to the same dataset.

Uses your system voice; voice and rate in settings.

≈ 2 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Differential privacy composition theorems are mathematical tools used in differential privacy to analyze and bound the accumulated privacy loss when multiple differentially private mechanisms are applied to the same dataset. They quantify how privacy guarantees degrade as more queries or analyses are performed, and are essential for designing complex differentially private systems and algorithms.

For example, if user submits multiple queries to a differentially private database, each query might individually satisfies ε-differential privacy but the repeated interaction can cumulatively leak more information than intended. Composition theorems address this by providing a way to calculate the overall privacy loss after multiple mechanisms have been applied.

Differential privacy is a property of a randomized algorithm, or mechanism, , which takes a database as input and produces an output. Informally, a mechanism is differentially private if each possible output is nearly as likely whether or not any one individual's data is included in the input.

Formally, is (\varepsilon,\delta) -differentially private if, for every pair of neighboring databases and (databases differing in the data of a single individual) and every set of possible outputs, \Pr[M(x)\in S] \;\le\; e^{\varepsilon}\,\Pr[M(y)\in S] + \delta, where the probability is taken over the random choices of . Smaller values of ε and δ correspond to stronger privacy.

When δ = 0 the mechanism is called ε-differentially private. The definition is closed under post-processing: applying any data-independent function to the output of a differentially private mechanism cannot weaken its guarantee. Composition theorems specifically address what guarantee results when several differentially private mechanisms are combined.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378164554 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001378164554 · captured 2026-10-03 · ledger · version history

Cite this page as: encyclopegia.org, “Differential privacy composition theorems”, snapshot enwiki-001378164554. https://encyclopegia.org/a/differential-privacy-composition-theorems

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.