Literature Database Entry

zhou2022rainbow-preprint

Ziqi Zhou, Onur Günlü, Rafael G. L. D'Oliveira, Muriel Médard, Parastoo Sadeghi and Rafael F. Schaefer, "Rainbow Differential Privacy," arXiv, cs.CR, 2202.03974, February 2022.

Abstract

We extend a previous framework for designing differentially private (DP) mechanisms via randomized graph colorings that was restricted to binary functions, corresponding to colorings in a graph, to multi-valued functions. As before, datasets are nodes in the graph and any two neighboring datasets are connected by an edge. In our setting, we assume that each dataset has a preferential ordering for the possible outputs of the mechanism, each of which we refer to as a rainbow. Different rainbows partition the graph of datasets into different regions. We show that if the DP mechanism is pre-specified at the boundary of such regions and behaves identically for all same-rainbow boundary datasets, at most one optimal such mechanism can exist and the problem can be solved by means of a morphism to a line graph. We then show closed form expressions for the line graph in the case of ternary functions. Treatment of ternary queries in this paper displays enough richness to be extended to higher-dimensional query spaces with preferential query ordering, but the optimality proof does not seem to follow directly from the ternary proof.

Quick access

Original Version DOI (at publishers web site)
BibTeX BibTeX

Contact

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

BibTeX reference

@techreport{zhou2022rainbow-preprint,
    author = {Zhou, Ziqi and G{\"{u}}nl{\"{u}}, Onur and D'Oliveira, Rafael G. L. and M{\'{e}}dard, Muriel and Sadeghi, Parastoo and Schaefer, Rafael F.},
    doi = {10.48550/arXiv.2202.03974},
    title = {{Rainbow Differential Privacy}},
    institution = {arXiv},
    month = {2},
    number = {2202.03974},
    type = {cs.CR},
    year = {2022},
   }
   
   

Copyright notice

Links to final or draft versions of papers are presented here to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted or distributed for commercial purposes without the explicit permission of the copyright holder.

The following applies to all papers listed above that have IEEE copyrights: Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

The following applies to all papers listed above that are in submission to IEEE conference/workshop proceedings or journals: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

The following applies to all papers listed above that have ACM copyrights: ACM COPYRIGHT NOTICE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or permissions@acm.org.

The following applies to all SpringerLink papers listed above that have Springer Science+Business Media copyrights: The original publication is available at www.springerlink.com.

This page was automatically generated using BibDB and bib2web.

Last modified: 2026-05-18