A Composition Theorem via f-Divergence Differential Privacy
Shota Saito, Koji Chida, Osamu Takaki · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2025
Differential privacy is used to guarantee privacy protection and has become the de facto standard for privacy protection data analysis. The (α, ε)-Rényi differential privacy ((α, ε)-RDP), which is based on the Rényi divergence, has been proposed as a relaxation of the ε-differential privacy (ε-DP). The Rényi divergence is a generalization of the Kullback-Leibler divergence. The f-divergence, on the other hand, is also a generalization of the Kullback-Leibler divergence, where f : [0, ∞) → ℝ is a convex function satisfying f(1) = 0. Hence, we can consider differential privacy based on the f-divergence in the same manner as the Rényi differential privacy. This paper introduces (f, ε)-differential privacy ((f, ε)-DP) based on the f-divergence. We prove a novel composition theorem of an adaptive composition of n mechanisms all satisfying ε-DP. To derive this result, the following three propositions play an important role: (i) a probability preservation inequality via the f-divergence; (ii) a composition of two (f, ε)-DP; (iii) a relationship between the ε-DP and the (f, ε)-DP. Numerical examples show that there are cases where the proposed composition theorem is tighter than the previous composition theorems.