Generalized Rainbow Differential Privacy
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916193942634496 |
|---|---|
| author | Gu, Yuzhou Zhou, Ziqi Günlü, Onur D'Oliveira, Rafael G. L. Sadeghi, Parastoo Médard, Muriel Schaefer, Rafael F. |
| author_facet | Gu, Yuzhou Zhou, Ziqi Günlü, Onur D'Oliveira, Rafael G. L. Sadeghi, Parastoo Médard, Muriel Schaefer, Rafael F. |
| contents | 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 $(ε,δ)$-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 $(ε,δ)$-DP, improving upon previous results that only apply to at most three colors and for $ε$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_05871 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Generalized Rainbow Differential Privacy Gu, Yuzhou Zhou, Ziqi Günlü, Onur D'Oliveira, Rafael G. L. Sadeghi, Parastoo Médard, Muriel Schaefer, Rafael F. Cryptography and Security Information Retrieval Information Theory 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 $(ε,δ)$-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 $(ε,δ)$-DP, improving upon previous results that only apply to at most three colors and for $ε$-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. |
| title | Generalized Rainbow Differential Privacy |
| topic | Cryptography and Security Information Retrieval Information Theory |
| url | https://arxiv.org/abs/2309.05871 |