| Paper ID | D1-S7-T4.1 |
| Paper Title |
Differential Privacy for Binary Functions via Randomized Graph Colorings |
| Authors |
Rafael D’Oliveira, Muriel Medard, Massachusetts Institute of Technology, United States; Parastoo Sadeghi, University of New South Wales, Australia |
| Session |
D1-S7-T4: Differential Privacy II |
| Chaired Session: |
Tuesday, 13 July, 00:00 - 00:20 |
| Engagement Session: |
Tuesday, 13 July, 00:20 - 00:40 |
| Abstract |
We present a framework for designing differentially private (DP) mechanisms for binary functions via a graph representation of datasets. Datasets are nodes in the graph and any two neighboring datasets are connected by an edge. The true binary function we want to approximate assigns a value (or true color) to a dataset. Randomized DP mechanisms are then equivalent to randomized colorings of the graph. A key notion we use is that of the boundary of the graph. Any two neighboring datasets assigned a different true color belong to the boundary. Under this framework, we show that fixing the mechanism behavior at the boundary induces a unique optimal mechanism. Moreover, if the mechanism is to have a homogeneous behavior at the boundary, we present a closed expression for the optimal mechanism, which is obtained by means of a \emph{pullback} operation on the optimal mechanism of a line graph. For balanced mechanisms, not favoring one binary value over another, the optimal $(\epsilon,\delta)$-DP mechanism takes a particularly simple form, depending only on the minimum distance to the boundary, on $\epsilon$, and on $\delta$.
|
