skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Generalized Rainbow Differential Privacy
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.  more » « less
Award ID(s):
1926686
PAR ID:
10534865
Author(s) / Creator(s):
; ; ; ; ; ;
Publisher / Repository:
Society for Privacty and Confidentiality Research
Date Published:
Journal Name:
Journal of Privacy and Confidentiality
Volume:
14
Issue:
2
ISSN:
2575-8527
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Journal of graph theory)
    In this paper we study the randomly edge colored graph that is obtained by adding randomly colored random edges to an arbitrary randomly edge colored dense graph. In particular we ask how many colors and how many random edges are needed so that the resultant graph contains a fixed number of edge disjoint rainbow Hamilton cycles w.h.p. We also ask when in the resultant graph every pair of vertices is connected by a rainbow path w.h.p. 
    more » « less
  2. ; ; (, Journal of Graph Theory)
    Abstract In this note we examine the following random graph model: for an arbitrary graph , with quadratic many edges, construct a graph by randomly adding edges to and randomly coloring the edges of with colors. We show that for a large enough constant and , every pair of vertices in are joined by a rainbow path, that is, israinbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for and resolved the case when and is a function of . 
    more » « less
  3. ; (, Advances in neural information processing systems)
    Koyejo, S.; Mohamed, S.; Agarwal, A.; Belgrave, D.; Cho, K.; Oh, A. (Ed.)
    A canonical noise distribution (CND) is an additive mechanism designed to satisfy f-differential privacy (f-DP), without any wasted privacy budget. f-DP is a hypothesis testing-based formulation of privacy phrased in terms of tradeoff functions, which captures the difficulty of a hypothesis test. In this paper, we consider the existence and construction of both log-concave CNDs and multivariate CNDs. Log-concave distributions are important to ensure that higher outputs of the mechanism correspond to higher input values, whereas multivariate noise distributions are important to ensure that a joint release of multiple outputs has a tight privacy characterization. We show that the existence and construction of CNDs for both types of problems is related to whether the tradeoff function can be decomposed by functional composition (related to group privacy) or mechanism composition. In particular, we show that pure epsilon-DP cannot be decomposed in either way and that there is neither a log-concave CND nor any multivariate CND for epsilon-DP. On the other hand, we show that Gaussian-DP, (0,delta)-DP, and Laplace-DP each have both log-concave and multivariate CNDs. 
    more » « less
  4. ; (, Journal of machine learning research)
    Weller, Adrian (Ed.)
    Differential privacy (DP) offers strong theoretical privacy guarantees, though implementations of DP mechanisms may be vulnerable to side-channel attacks, such as timing attacks. When sampling methods such as MCMC or rejection sampling are used to implement a mechanism, the runtime can leak private information. We characterize the additional privacy cost due to the runtime of a rejection sampler in terms of both (epsilon,delta)-DP as well as f-DP. We also show that unless the acceptance probability is constant across databases, the runtime of a rejection sampler does not satisfy epsilon-DP for any epsilon. We show that there is a similar breakdown in privacy with adaptive rejection samplers. We propose three modifications to the rejection sampling algorithm, with varying assumptions, to protect against timing attacks by making the runtime independent of the data. The modification with the weakest assumptions is an approximate sampler, introducing a small increase in the privacy cost, whereas the other modifications give perfect samplers. We also use our techniques to develop an adaptive rejection sampler for log-Holder densities, which also has data-independent runtime. We give several examples of DP mechanisms that fit the assumptions of our methods and can thus be implemented using our samplers. 
    more » « less
  5. ; ; ; (, Random Structures & Algorithms)
    ABSTRACT DP‐coloring (also called correspondence coloring) of graphs is a generalization of list coloring that has been widely studied since its introduction by Dvořák and Postle in 2015. Intuitively, DP‐coloring generalizes list coloring by allowing the colors that are identified as the same to vary from edge to edge. Formally, DP‐coloring of a graph is equivalent to an independent transversal in an auxiliary structure called a DP‐cover of . In this paper, we introduce the notion of random DP‐covers and study the behavior of DP‐coloring from such random covers. We prove a series of results about the probability that a graph is or is not DP‐colorable from a random cover. These results support the following threshold behavior on random ‐fold DP‐covers as where is the maximum density of a graph: Graphs are non‐DP‐colorable with high‐probability when is sufficiently smaller than , and graphs are DP‐colorable with high‐probability when is sufficiently larger than . Our results depend on growing fast enough and imply a sharp threshold for dense enough graphs. For sparser graphs, we analyze DP‐colorability in terms of degeneracy. We also prove fractional DP‐coloring analogs to these results. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email