Generalized Rainbow Differential Privacy

Main Article Content

Yuzhou Gu
Ziqi Zhou
Onur Günlü
Rafael G. L. D'Oliveira
Parastoo Sadeghi
Muriel Médard
Rafael F. Schaefer


We study a new framework for designing differentially private (DP) mechanisms via randomized graph colorings, called rainbow differential privacy. In this framework, datasets are nodes in a graph, and two neighboring datasets are connected by an edge. Each dataset in the graph has a preferential ordering for the possible outputs of the mechanism, and these orderings are called rainbows. Different rainbows partition the graph of connected datasets into different regions. We show that if a DP mechanism at the boundary of such regions is fixed and it behaves identically for all same-rainbow boundary datasets, then a unique optimal $(\epsilon,\delta)$-DP mechanism exists (as long as the boundary condition is valid) and can be expressed in closed-form. Our proof technique is based on an interesting relationship between dominance ordering and DP, which applies to any finite number of colors and for $(\epsilon,\delta)$-DP, improving upon previous results that only apply to at most three colors and for $\epsilon$-DP. We justify the homogeneous boundary condition assumption by giving an example with non-homogeneous boundary condition, for which there exists no optimal DP mechanism.

Article Details

How to Cite
Gu, Yuzhou, Ziqi Zhou, Onur Günlü, Rafael G. L. D’Oliveira, Parastoo Sadeghi, Muriel Médard, and Rafael F. Schaefer. 2024. “Generalized Rainbow Differential Privacy”. Journal of Privacy and Confidentiality 14 (2).

Funding data