Composition of privacy mechanisms: Only fresh noise counts

Music City Center 

Composition is a key desiderata for a differential privacy (DP) flavor because it ensures a controlled degradation of the total privacy loss as additional statistics are released. However, ever since Pufferfish DP flavors were first introduced in 2012 it has remained an open problem whether these flavors – which take a Bayesian viewpoint by incorporating into DP the attacker's uncertainty in the confidential data – satisfy composition. In this work, we resolve this question by proving that a Pufferfish flavor satisfies composition if and only if it is equivalent to a pure ε-DP flavor. Therefore, the generalization of DP to Pufferfish privacy is incompatible with the desiderata of composition. Furthermore, we determine that a Pufferfish mechanism composes with itself if and only if it satisfies pure ε-DP – i.e. if and only if it does not make use of the attacker's uncertainty in the data generation mechanism. This result establishes that any class of composable mechanisms which satisfy Pufferfish – such as those found in existing literature – in fact satisfy the stronger condition of pure ε-DP. In intuitive terms, we show that a composable mechanism cannot reuse the "noise" provided by the attacker's Bayesian model of the confidential data: only fresh noise counts when it comes to composition.