Differential privacy composition theorems

Last updated

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. [1] [2] [3] [4]

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.

References

  1. ↑ Kairouz, Peter; Oh, Sewoong; Viswanath, Pramod (2015-12-06), The Composition Theorem for Differential Privacy, arXiv, doi:10.48550/arXiv.1311.0776, arXiv:1311.0776, retrieved 2025-02-07
  2. ↑ Privacy, Differential. "Composition Basics". differentialprivacy.org. Retrieved 2025-02-07.{{cite web}}: |last= has generic name (help)
  3. ↑ Steinke, Thomas (2022-10-26), Composition of Differential Privacy & Privacy Amplification by Subsampling, arXiv, doi:10.48550/arXiv.2210.00597, arXiv:2210.00597, retrieved 2025-02-07
  4. ↑ Lyu, Xin (2022-12-06). "Composition Theorems for Interactive Differential Privacy". Advances in Neural Information Processing Systems. 35: 9700–9712.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.