Differential Privacy Part-III: Composition

Composition is one of the major features of DP. This allows us to not only quantify how privacy is guaranteed for a single query or mechanism but a series of of them

Basic Composition Simplest rule of them is basic composition , which states that if k DP algorithms are run the privacy is now


Composition takes into account two possible ways privacy could be degraded:

When the multiple queries are ran on the same database multiple times Queries are run on seperate databases containing information on same individuals. It is also possible for adversery to influence creation of databases to learn about given target. Advanced Composition The basic composition could handle only linear possible degradation in privacy which may not be the case in practice. Introducing Advanced composition which could handle more advanced forms of privacy degradation. When an adversery ideally plans to learn about the database they don’t typically do it linearly , they do in a fashion where they adapt better with increased number of queries. The adversery uses information from previous mechanisms and use information of current mechanism to learn in future mechanisms. Advanced composition given by

It is usually a pessimistic bound for understanding privacy degradation


Blog URL at hrishikamath.com

less than 1 minute read

Hello there, thanks for visiting this page. My blog has moved to hrishikamath.com. Won't put effort into even making this page look nice for you :P.

Back to top ↑