Privacy Amplification by Iteration

Differential privacy [DMNS06] is a standard concept for capturing privacy of statistical algorithms. In its original formulation, (pure) differential privacy is parameterized by a single real number--the so-called privacy budget--which characterizes the privacy loss of an individual contributor to the input dataset. As applications of differential privacy start to proliferate, they bring to the fore the problem of administering the privacy budget, with specific emphasis on privacy composition and privacy amplification. Privacy composition enables modular design and analysis of complex and heterogeneous algorithms from simpler building blocks by controlling the total privacy budget of their combination. Improving on "naïve" composition, which simply (but very consequentially!) states that the privacy budgets of composition blocks sum up, "advanced" composition theorems allow subadditive accumulation of the privacy budgets. All existing proofs of advanced composition theorems assume that all intermediate outputs are revealed, whether the composite mechanism requires it or not. Privacy amplification goes even further by bounding the privacy budget--for select mechanisms--of a combination to be less than the privacy budget of its parts.