# Optimal Binary Differential Privacy via Graphs

Sahel Torkamani, Javad B. Ebrahimi, Parastoo Sadeghi, Rafael G. L. D’Oliveira,
and Muriel Médard Sahel Torkamani is with the Department of Mathematical
Sciences at Sharif University of Technology, Tehran, Iran, Email:
<EMAIL_ADDRESS>Javad Ebrahimi is with the Department of
Mathematical Sciences at Sharif University of Technology, Tehran, Iran, Email:
<EMAIL_ADDRESS>Parastoo Sadeghi is with the School of Engineering
and Technology, University of New South Wales, Canberra, Australia, Email:
<EMAIL_ADDRESS>Rafael G. L. D’oliveira is with the School of
Mathematical and Statistical Sciences at Clemson University, Clemson, SC,
Email<EMAIL_ADDRESS>Muriel Médard is with the Research Laboratory of
Electronics at the Massachusetts Institute of Technology, Cambridge, MA, Email
<EMAIL_ADDRESS>Preliminary results of this paper were partly presented in
[1].

###### Abstract

We present the notion of _reasonable utility_ for binary mechanisms, which
applies to all utility functions in the literature. This notion induces a
partial ordering on the performance of all binary differentially private (DP)
mechanisms. DP mechanisms that are maximal elements of this ordering are
optimal DP mechanisms for every reasonable utility. By looking at differential
privacy as a randomized graph coloring, we characterize these optimal DP in
terms of their behavior on a certain subset of the boundary datasets we call a
boundary hitting set. In the process of establishing our results, we also
introduce a useful notion that generalizes DP conditions for binary-valued
queries, which we coin as suitable pairs. Suitable pairs abstract away the
algebraic roles of $\varepsilon,\delta$ in the DP framework, making the
derivations and understanding of our proofs simpler. Additionally, the notion
of a suitable pair can potentially capture privacy conditions in frameworks
other than DP and may be of independent interest.

##  I Introduction

Differential privacy (DP) [2] has emerged as a leading standard in private
data analysis [3]. This framework has been instrumental in protecting privacy
across a multitude of applications. Most prominently, the United States Census
Bureau integrated differential privacy into its 2020 Census release [4].
Furthermore, industry leaders like Google [5], Microsoft [6], and Apple [7]
have also incorporated DP into their respective systems. DP is also heavily
studied and used in deep learning [8], [9] and federated learning [10], [11].

Differential privacy is often achieved through a randomized perturbation of
the true query outputs before sharing them with potentially untrustworthy
entities. However, such a perturbation (also known as a DP mechanism)
inevitably affects the reliability and utility of the output. Therefore, one
of the central and challenging research problems in the field is how to design
and implement DP mechanisms to best balance privacy and utility [12]. Under
certain parameter settings and assumptions, optimal DP mechanisms have been
studied in the literature for real-valued queries [13, 14, 15, 16, 17] and for
categorical or binary-valued data [18, 19, 20].

Previous works on differential privacy have considered different utility
functions to measure performance. Thus, while a certain DP mechanism might
perform well, or even optimally, for a certain utility, it might not do so for
another. In Definition 2, we present the notion of _reasonable utility_ for
binary mechanisms, which applies to all binary utility functions in the
literature. This notion induces a partial ordering on the performance of all
binary DP mechanisms. DP mechanisms which are maximal elements of this
ordering are optimal DP mechanisms for every reasonable utility. In Theorem 1,
we characterize these optimal DP mechanisms. To do so, we look at differential
privacy as a randomized graph coloring.

In our graph formulation, each vertex $v\in V$ of the graph represents a
dataset and each edge represents a neighborhood relation. The true value of
the binary query is represented by the vertex color (such as blue and red). A
DP mechanism is then a randomized coloring of the vertices subject to local
privacy constraints. We categorize datasets into boundary and non-boundary
datasets. Boundary datasets are those with at least one neighbor with a
different true query value (color), and non-boundary datasets are those in
which no single individual in the dataset can change the query.

Theorem 1 shows that optimal DP mechanisms are characterized by the values of
the DP mechanism on a certain subset of the boundary datasets we call a
_boundary hitting set_. Thus, if the values of a DP mechanism on a boundary
hitting set are defined and satisfy DP conditions among themselves, then there
exists a unique optimal DP mechanism which outperforms all others, for any
reasonable utility function.

In the process of establishing our results, we also introduce a useful notion
that generalizes DP conditions for binary-valued queries. We coin this as a
_suitable pair_ , which abstracts away the algebraic roles of
$\varepsilon,\delta$ in the DP framework and instead focuses on the following:
a randomized binary mechanism defined on a dataset $v$ imposes an upper bound
and a lower bound on the mechanism on a neighboring dataset $u$. These bounds
at $u$, in turn, impose upper and lower bounds on the mechanism in the
original dataset $v$. The strength of the notion of suitable pair is that non-
local privacy conditions between non-neighboring datasets can be easily
understood and manipulated without being entangled in algebraic DP conditions.
Thus, simplifying the derivations and understanding of our proofs.
Additionally, the notion of a suitable pair can potentially capture privacy
conditions in frameworks other than DP and may be of independent interest.

###  I-A Main Contributions

Our main contributions are as follows.

  * •

In Definition 2, we present the notion of _reasonable utility_ for binary
mechanisms, which applies to all utility functions in the literature. This
notion induces a partial ordering on the performance of all binary DP
mechanisms. DP mechanisms which are maximal elements of this ordering are
optimal DP mechanisms for every reasonable utility.

  * •

In Theorem 1 we characterize optimal DP mechanisms by their values on a
certain subset of the boundary datasets, which we call a _boundary hitting
set_.

  * •

In Definition 12 we present the notion of a _suitable pair_. This notion
generalizes DP conditions for binary-valued queries and abstracts away the
algebraic roles of $\varepsilon,\delta$, thus simplifying our proofs.

  * •

We present Algorithm 1, for finding optimal mechanisms within the suitable
pair framework, as well as a more efficient Algorithm 2 for the case where one
is solely interested in the output of a mechanism on a specific dataset. The
optimality of Algorithm 1 is stated in Theorem 2.

Theorem 1 generalizes the results in [1], which is stated as Corollaries 1 and
2 for the spcial case of boundary homogenous mechanisms and balanced
mechanisms, respectively. Definition 12, Algorithms 1 and 2, Theorem 2, and
associated intermediate results are all new in this paper with respect to [1].

###  I-B Paper Organization

Section II contains a statement of the problem and all main results of the
paper. In Section II-A, we review basic DP definitions and introduce the
notion of reasonable utility, mechanism utility dominance, and optimal
mechanism. Section II-B presents the DP mechanism as the randomized coloring
of datasets on the graph. Section II-C, highlighted in Theorem 1, presents the
main results for optimally extending the mechanism in terms of the restricted
$(\varepsilon,\delta)$-DP mechanism on a boundary hitting set. Section II-D
generalizes the results of Section II-C using the new notion of a suitable
pair and presents the necessary and sufficient condition for the existence of
the unique optimal extension of a mechanism restricted to a boundary hitting
set. It also summarizes the optimal extension in Algorithm 1. All proofs are
in Section III.

##  II Main Results

###  II-A Differential Privacy

We denote by $V$ the family of datasets. We consider a symmetric neighborhood
relationship $\sim$ on $V$ where $u,v\in V$ are said to be neighbors if $u\sim
v$. We also consider a finite output space $Q$, which corresponds to the space
over which the output of the queries lies. A randomized mechanism, which we
refer to as just a mechanism, is a random function $\mathcal{M}:V\to Q$, from
the family of datasets to the output space.

######  Definition 1 (Differential Privacy [21]).

Let $\varepsilon,\delta\in\mathbb{R}$ be such that $\varepsilon\geq 0$ and
$0\leq\delta<1$. Let $V$ be a set and $\sim$ be a symmetric relation on $V$.
Then, a mechanism $\mathcal{M}:V\to Q$ is
$(\varepsilon,\delta)$-differentially private if for any $u\sim v$ and
$S\subseteq Q$, we have $\Pr[\mathcal{M}(u)\in\mathcal{S}]\leq
e^{\varepsilon}\Pr[\mathcal{M}(v)\in\mathcal{S}]+\delta$. We denote the set of
all $(\varepsilon,\delta)$-DP mechanisms $\mathcal{M}:V\rightarrow Q$ by
$\mathfrak{M}_{\varepsilon,\delta}(V,Q)$. However, when $V$ and $Q$ are clear
from the context, we refer to $\mathfrak{M}_{\varepsilon,\delta}(V,Q)$ as
$\mathfrak{M}_{\varepsilon,\delta}$.

In this paper, we consider the case where the size of the output space is
$|Q|=2$, i.e., binary-valued queries. Without loss of generality, we set the
output space to $Q=\\{\texttt{blue},\texttt{red}\\}$. The DP conditions for
any $u\sim v$ in $V$ are then as follows.

$\displaystyle\Pr[\mathcal{M}(u)=\texttt{blue}]$ $\displaystyle\leq
e^{\varepsilon}\Pr[\mathcal{M}(v)=\texttt{blue}]+\delta,$ (1) $\displaystyle
1-\Pr[\mathcal{M}(u)=\texttt{blue}]$ $\displaystyle\leq
e^{\varepsilon}(1-\Pr[\mathcal{M}(v)=\texttt{blue}])+\delta,$ (2)
$\displaystyle\Pr[\mathcal{M}(v)=\texttt{blue}]$ $\displaystyle\leq
e^{\varepsilon}\Pr[\mathcal{M}(u)=\texttt{blue}]+\delta,$ (3) $\displaystyle
1-\Pr[\mathcal{M}(v)=\texttt{blue}]$ $\displaystyle\leq
e^{\varepsilon}(1-\Pr[\mathcal{M}(u)=\texttt{blue}])+\delta.$ (4)

Since we only consider binary-valued queries, we have that
$\Pr[\mathcal{M}(u)=\texttt{red}]=1-\Pr[\mathcal{M}(u)=\texttt{blue}]$ and
that $\Pr[\mathcal{M}(v)=\texttt{red}]=1-\Pr[\mathcal{M}(v)=\texttt{blue}]$.

We consider a function $T:V\to Q$, which we refer to as the true function. Our
goal is to approximate the true function $T$ using an
$(\varepsilon,\delta)$-differentially private mechanism $\mathcal{M}$. To
measure the performance of the mechanism, i.e., how good the approximation is,
a utility function
$\mathcal{U}_{T}:\mathfrak{M}_{\varepsilon,\delta}\rightarrow\mathbb{R}$ must
be defined, where
$\mathcal{U}_{T}[\mathcal{M}]\geq\mathcal{U}_{T}[\mathcal{M}^{\prime}]$ means
that the mechanism $\mathcal{M}$ outperforms $\mathcal{M}^{\prime}$ with
respect to the true function $T$. In this work, we do not consider a specific
utility function, but rather consider a general family of them.

######  Definition 2.

A utility function
$\mathcal{U}:\mathfrak{M}_{\varepsilon,\delta}\rightarrow\mathbb{R}$ is
reasonable if $\Pr[\mathcal{M}(u)=T(u)]\geq\Pr[\mathcal{M^{\prime}}(u)=T(u)]$
for every $u\in V$ implies
$\mathcal{U}[\mathcal{M}]\geq\mathcal{U}[\mathcal{M}^{\prime}]$. When this
condition holds, we say that the mechanism $\mathcal{M}$ dominates
$\mathcal{M}^{\prime}$.

Given the true function $T$, the notion of domination in Definition 2 induces
a partial order on the set $\mathfrak{M}_{\varepsilon,\delta}$ of all
$(\varepsilon,\delta)$-DP mechanisms. If a mechanism $\mathcal{M}$ dominates
another mechansim $\mathcal{M}^{\prime}$ then the first one outperforms the
second for every reasonable utility function. It is not always the case that
two mechanisms can be compared, even when restricted to a reasonable utility.
We give an example below.

######  Example 1.

Consider the dataset $V=\\{1,2\\}$ where $1\sim 2$ and the true function
$T:V\rightarrow Q$ is such that $T(1)=\texttt{blue}$ and $T(2)=\texttt{red}$.
Let $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ be two $(\log(2),0.1)$-DP
mechanisms111In this paper, by $\log$ we mean the natural logarithm. defined
such that $\Pr[\mathcal{M}_{1}(1)=\texttt{blue}]=0.58$,
$\Pr[\mathcal{M}_{1}(2)=\texttt{red}]=0.76$,
$\Pr[\mathcal{M}_{2}(1)=\texttt{blue}]=0.64$, and
$\Pr[\mathcal{M}_{2}(2)=\texttt{red}]=0.73$. Then, neither mechanism dominates
the other. The reason for this is that there are reasonable utility functions
which, for a mechanism $\mathcal{M}\in\mathfrak{M}_{\varepsilon,\delta}$ might
prefer a higher value for $\Pr[\mathcal{M}(1)=\texttt{blue}]$ more than a
higher value for $\Pr[\mathcal{M}(2)=\texttt{red}]$, or vice-versa. Extreme
cases of this are the reasonable utility functions
$U[\mathcal{M}]=\Pr[\mathcal{M}(1)=\texttt{blue}]$ and
$U^{\prime}[\mathcal{M}]=\Pr[\mathcal{M}(2)=\texttt{red}]$, both disagreeing
on which of $\mathcal{M}_{1}$ or $\mathcal{M}_{2}$ is better.

For more discussion and insight on the notion of reasonable utility and its
extensions, see Sections IV and V.

We are interested in characterizing the optimal $(\varepsilon,\delta)$-DP
mechanisms, i.e., the $(\varepsilon,\delta)$-DP mechanisms $\mathcal{M}$ which
are not dominated by any other mechanism. These correspond to the maximal
elements in the partial order $\mathfrak{M}_{\varepsilon,\delta}$. To find
such mechanisms, we reinterpret the problem as a randomized graph coloring
problem, which we describe in Section II-B.

This random graph coloring approach, together with the notion of suitable
pairs defined in Section II-D, allows us to abstract the problem of
characterizing optimal $(\varepsilon,\delta)$-DP mechanisms. Through such
abstraction, we show in Theorem 1 that if the mechanism is defined only on an
appropriate subset of neighboring datasets, between which the true function
changes value, then the optimal mechanism can be uniquely found for every
other dataset.

###  II-B Differential Privacy as Randomized Graph Colorings

We interpret differential privacy as a randomized graph coloring problem. The
vertices of the graph222We assume the graph is undirected and connected.
Otherwise, the results of this paper apply to any connected component of
$\mathcal{G}(V,E)$. $\mathcal{G}(V,E)$ are the datasets $u\in V$ and the edges
$E$ are the neighboring relation on the datasets, i.e. two vertices $u,v\in V$
have an edge between them if $u\sim v$. The true function $T:V\rightarrow Q$
is a graph coloring ($Q$ is the set of colors) of the vertices of
$\mathcal{G}$. For a given color $j\in Q$, the inverse image $T^{-1}(j)$ is
the set of vertices with true value $j$. Therefore, for a given vertex $u\in
V$, the inverse image $T^{-1}(T(u))$ is the set of vertices with the same true
value as $u$. Since differential privacy is a local condition, i.e., it is a
condition on the $u,v\in V$ such that $u\sim v$, the notion of a neighborhood
is essential.

$a$$b$$c$$g$$h$$k$$\ell$$d$$e$$f$$i$$j$$m$$n$$o$$p$$q$$r$$s$$t$$u$$v$ Figure
1: In this graph, the vertices are the datasets and the edges are the
neighborhood relationships, e.g., since there exists an edge between $a$ and
$b$, it follows that $a\sim b$. The true function is a graph coloring of the
vertices, e.g., $T(a)=\texttt{blue}$ and $T(d)=\texttt{red}$. The set of
vertices with true value blue is
$T^{-1}(\texttt{blue})=\\{a,b,g,h,k,\ell,n,s,t,u,v\\}$ and the ones with true
value red is $T^{-1}(\texttt{red})=\\{d,e,f,i,j,m,n,o,p,q,r\\}$. The
neighbohood of the vertex set $\\{g,h\\}$ is $N(\\{g,h\\})=\\{a,b,c,i,n\\}$.
The distance between $a$ and $b$ is $\operatorname{dist}(a,d)=5$, which is the
size of the shortest path $(a,g),(g,c),(c,h),(h,i),(i,d)$ between them. The
edges colored in green are the boundary edges
$\partial_{T}(\mathcal{G},E)=\\{(\ell,q),(h,n),(h,i),(r,s),(r,t),(f,u)\\}$.
The boundary vertices are the vertices
$\partial_{T}(\mathcal{G},V)=\\{\ell,q,h,n,i,r,s,t,f,u\\}$. The sets
$\mathcal{H}_{T}=\\{l,h,u,s,t\\}$ and
$\mathcal{H}^{\prime}_{T}=\\{a,q,n,i,s,t,u,v\\}$ are boundary-hitting sets,
because they contain at least one vertex from each boundary edge, while the
set $\\{a,\ell,n,s,t,j,u\\}$ is not a boundary-hitting set since it does not
include any vertex from the boundary edge $(h,i)$. Finally,
$\partial_{T}(\mathcal{G},\texttt{blue})=\\{h,\ell,s,t,u\\}$ and
$\partial_{T}(\mathcal{G},\texttt{red})=\\{f,i,n,q,r\\}$.

######  Definition 3 (Neighborhood).

The neighborhood of a subset $S\subseteq V$ of vertices, denoted by $N(S)$, is
the set of all vertices in $V-S$ which are neighbors to at least one element
of $S$.

######  Definition 4.

A sequence of vertices $u=u_{0},u_{1},\cdots,u_{n}=v$ is said to form a path
from $u$ to $v$, denoted by $(u,v)$-path, if
$(u_{0},u_{1}),\cdots,(u_{n-1},u_{n})\in E$. We say $n$ is the path length.
The distance between two nodes $u,v$, denoted by $\operatorname{dist}(u,v)$,
is the shortest path length from $u$ to $v$. The distance between two subsets
$A_{1},A_{2}\subset V$ is the shortest path length between any $a_{1}\in
A_{1}$ and any $a_{2}\in A_{2}$.

######  Definition 5 (Boundary Edges).

The _boundary edge_ of $\mathcal{G}$ with respect to $T$, denoted by
$\partial_{T}(\mathcal{G},E)$, is the set of the edges in $\mathcal{G}$ whose
two endpoints have different true query values.

######  Definition 6 (Boundary Vertices).

The _boundary vertices_ of $\mathcal{G}$ with respect to $T$, denoted by
$\partial_{T}(\mathcal{G},V)$, is the set of all the endpoints of the boundary
edges.

######  Definition 7 (Boundary-hitting Set).

A _boundary-hitting set_ of $\mathcal{G}$ with respect to $T$, denoted by
$\mathcal{H}_{T}$, is a subset of the vertices which contains at least one
endpoint of every edge in $\partial_{T}(\mathcal{G},E)$.

######  Definition 8 (Boundary Vertices with True Value $j$).

The boundary vertices with true value $j$ is the set of boundary vertices
whose true value is $j$. We denote this set by
$\partial_{T}(\mathcal{G},j):=\partial_{T}(\mathcal{G},V)\cap T^{-1}(j)$.

In Fig. 1 we illustrate these definitions.

In an $(\varepsilon,\delta)$-differentially private mechanism, every path
connecting two vertices $u,v\in V$ induces an upper bound on the probability
of the mechanism output, i.e., the probability $\Pr[\mathcal{M}(v)=j]$ induces
an upper bound on $\Pr[\mathcal{M}(u)=j]$ and vice versa. These upper bounds
are induced by the $(\varepsilon,\delta)$-DP conditions (inequalities (1)
through (4)). Since each upper bound that $v$ induces on $u$ is an increasing
function of $\alpha:=\Pr[\mathcal{M}(v)=j]$ and of the length of the path
between $u$ and $v$, then the shortest path induces the tightest upper bound
on $\Pr[\mathcal{M}(u)=j]$. We formalize this statement through Definition 9
and Proposition 1.

######  Definition 9.

Let $u,v$ be distinct vertices in $V$ with distance
$d=\operatorname{dist}(u,v)$ between them and $\alpha\in[0,1]$ be some fixed
value. Then, the probability induced on the vertex $u$ by the vertex $v$ with
value $\alpha$ is:

$\displaystyle
p(d,\alpha)=\begin{cases}e^{d\varepsilon}\alpha+\delta\frac{e^{d\varepsilon}-1}{e^{\varepsilon}-1},&d\leq\tau,\\\
\min\big{(}1,e^{(2\tau-d)\varepsilon}\alpha+1-\frac{1}{e^{(d-\tau)\varepsilon}}&\tau<d.\\\
\quad+\frac{\delta(e^{\tau\varepsilon}+e^{(d-\tau)\varepsilon}-2)}{e^{(d-\tau)\varepsilon}(e^{\varepsilon}-1)}\big{)},\end{cases}$
(5)

where

$\displaystyle\tau=\left\lceil\frac{1}{\varepsilon}\log{\frac{(e^{\varepsilon}+2\delta-1)}{(e^{\varepsilon}+1)(e^{\varepsilon}\alpha-\alpha+\delta)}}\right\rceil.$
(6)

Taking the minimum in the second line of (5) ensures that $p(d,\alpha)$ never
exceeds $1$. The next proposition establishes how each vertex $v$ induces an
upper bound on $\Pr[\mathcal{M}(u)=j]$ for any other vertex $u$.

######  Proposition 1.

Let $\mathcal{M}:V\rightarrow Q$ be a mechanism. Then, $\mathcal{M}$ is an
$(\varepsilon,\delta)$-DP mechanism if and only if for every
$j\in\\{\texttt{blue},\texttt{red}\\}$ and every distinct vertices $u,v\in V$
with $d=\operatorname{dist}(u,v)$ and $\Pr[\mathcal{M}(u)=j]=\alpha$, it holds
that $\Pr[\mathcal{M}(v)=j]\leq p(d,\alpha)$.

Proposition 1 presents a closed form expression for the differential privacy
condition on non-neighboring datasets, which we use, in Theorem 1, to
characterize optimal mechanisms.

###  II-C Characterizing Optimal Mechanisms

We show that optimal mechanisms are uniquely characterized by their behavior
on the boundary edges, i.e., edges connecting vertices with different true
values (see Definition 5). We do this by showing that when a mechanism has
been predefined on a boundary-hitting set (see Definition 7), then it can be
uniquely extended to an optimal mechanism over all other vertices. These
results are shown in Theorem 1 and Algorithm 1. To this end, we introduce the
notions of mechanism restriction and extension.

######  Definition 10 (Mechanism Restriction).

The restriction of a mechanism $\mathcal{M}:\mathcal{V}\rightarrow Q$ to a
subset $A\subseteq V$ is $\mathcal{M}|_{A}:A\rightarrow Q$.

We also refer to $\mathcal{M}|_{A}$ as a partial mechanism.

######  Definition 11 (Mechanism Extension).

Let $A\subseteq V$ and $\mathcal{M}^{\prime}:A\rightarrow Q$ be a mechanism.
Then, a mechanism $\mathcal{M}:V\rightarrow Q$ is an extension of
$\mathcal{M}^{\prime}$ if $\mathcal{M}|_{A}=\mathcal{M}^{\prime}$.

######  Theorem 1.

Let $\mathcal{H}_{T}$ be a boundary-hitting set with respect to the true
function $T$ and $\mathcal{M}^{\prime}:\mathcal{H}_{T}\rightarrow Q$ be a
randomized function. Then, there exists a unique optimal
$(\varepsilon,\delta)$-DP mechanism $\mathcal{M}:V\rightarrow Q$ such that
$\mathcal{M}|_{\mathcal{H}_{T}}=\mathcal{M}^{\prime}$ if and only if for every
$u,v\in\mathcal{H}_{T}$ with $d=\operatorname{dist}(u,v)$, we have
$\Pr[\mathcal{M}^{\prime}(u)=j]\leq p(d,\Pr[\mathcal{M}^{\prime}(v)=j])$ for a
fixed $j\in Q$. Moreover, for every $u\notin\mathcal{H}_{T}$, the optimal
mechanism is

$\displaystyle\Pr[\mathcal{M}(u)=T(u)]=\min\limits_{v\in\mathcal{H}_{T}}p(\operatorname{dist}(u,v),\Pr[\mathcal{M}(v)=T(u)]).$
(7)

Theorem 1 establishes that optimal mechanisms are uniquely characterized by
their values at the boundary. Moreover, the assumption that $\mathcal{H}_{T}$
is a boundary-hitting set is essential to the theorem, as the following
example shows.

$e_{1}$$e_{2}$$e_{3}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$ Figure 2:  The graph
$\mathcal{G}$ in Examples 2 and 3. In Example 2, we show that if the set on
which the restricted mechanism is defined is not a boundary hitting set, then
there might not be a unique optimal extension for the setting of Theorem 1. In
Example 3, we show how Algorithm 1 works when the restricted mechanism is
properly defined on the boundary hitting set
$\mathcal{H}_{T}=\\{v_{1},v_{4}\\}$.

######  Example 2.

Let $\mathcal{G}(V,E)$ be the graph with vertices $V=\\{v_{1},\ldots,v_{4}\\}$
and edges $E=\\{(v_{1},v_{2}),(v_{2},v_{3}),(v_{3},v_{4})\\}$, the true
function be such that $T(v_{1})=T(v_{4})=\texttt{red}$ and
$T(v_{2})=T(v_{3})=\texttt{blue}$, and $A=\\{v_{3}\\}$. We illustrate this in
Fig. 2.

Note that $A$ is not a boundary-hitting set, since it is missing a vertex from
$(v_{1},v_{2})$. We now show a $(\log(2),0)$-DP mechanism
$\mathcal{M}^{\prime}:A\rightarrow Q$ which does not have a unique optimal
$(\log(2),0)$-DP extension to all of $V$.

Let $\mathcal{M}^{\prime}$ be such that
$\Pr[\mathcal{M}^{\prime}(v_{3})=\texttt{blue}]=\frac{1}{2}$. Then, the
$(\log(2),0)$-DP mechanisms $\mathcal{M}_{1}:V\rightarrow Q$ such that

$\displaystyle\Pr[\mathcal{M}_{1}(v_{1})$
$\displaystyle=\texttt{blue}]=\frac{1}{2},$
$\displaystyle\Pr[\mathcal{M}_{1}(v_{2})$
$\displaystyle=\texttt{blue}]=\frac{3}{4},$
$\displaystyle\Pr[\mathcal{M}_{1}(v_{3})$
$\displaystyle=\texttt{blue}]=\frac{1}{2},$
$\displaystyle\Pr[\mathcal{M}_{1}(v_{4})$
$\displaystyle=\texttt{blue}]=\frac{1}{4},$

and $\mathcal{M}_{2}:V\rightarrow Q$ such that

$\displaystyle\Pr[\mathcal{M}_{1}(v_{1})$
$\displaystyle=\texttt{blue}]=\frac{1}{8},$
$\displaystyle\Pr[\mathcal{M}_{1}(v_{2})$
$\displaystyle=\texttt{blue}]=\frac{1}{4},$
$\displaystyle\Pr[\mathcal{M}_{1}(v_{3})$
$\displaystyle=\texttt{blue}]=\frac{1}{2},$
$\displaystyle\Pr[\mathcal{M}_{1}(v_{4})$
$\displaystyle=\texttt{blue}]=\frac{1}{4},$

are extensions of $\mathcal{M}^{\prime}$ which are not comparable. Indeed,
each is a maximal element in the partially ordered set of $(\log(2),0)$-DP
mechanisms on $\mathcal{G}$.

Theorem 1 generalizes the main results of [1], which we restate as corollaries
below.

######  Corollary 1.

Let $\alpha_{\texttt{blue}},\alpha_{\texttt{red}}\in[0,1]$ be fixed real
numbers. Suppose there exists an optimal $(\varepsilon,\delta)$-DP mechanism
$\mathcal{M}:V\rightarrow Q$ satisfying
$\Pr[\mathcal{M}(v)=T(v)]=\alpha_{T(v)}$, for every boundary vertex
$v\in\partial_{T}(\mathcal{G},V)$. Then for every vertex
$u\notin\partial_{T}(\mathcal{G},V)$, the optimal mechanism must satisfy
$\Pr[\mathcal{M}(u)=T(u)]=p(\operatorname{dist}(u,w),\alpha_{T(w)})$, where
$w\in\partial_{T}(\mathcal{G},T(u))$ is the closest boundary vertex to
$u$.333Due to a different labelling of vertices in [1], $\tau$ in (6) is
larger than the corresponding $\tau$ in [1, Definition 8] by one. After
appropriate transformations, they both result in the same expression for
$\Pr[\mathcal{M}(u)=T(u)]$.

Corollary 1 states that when the restricted mechanism is homogeneous on the
boundary, i.e.,
$\Pr[\mathcal{M}^{\prime}(u)=T(u)]=\Pr[\mathcal{M}^{\prime}(w)=T(w)]$ for
every $v,w\in\partial_{T}(\mathcal{G},V)$ such that $T(v)=T(w)$, finding the
optimal extension to a non-boundary vertex $u$ using (7) reduces to first
finding the closest boundary vertex to $u$, denoted by $w$. Note that by
definition of the boundary and the distance, $w$ must have the same true value
as $u$. Then, $\Pr[\mathcal{M}(u)=T(u)]$ will be given by (5) with
$\alpha=\Pr[\mathcal{M}(w)=T(w)]$ and $d=\operatorname{dist}(u,w)$. A
particularly interesting boundary homogeneous case is when the
$(\varepsilon,\delta)$-DP mechanism is balanced, i.e., when
$\alpha_{\texttt{blue}}=\alpha_{\texttt{red}}$, which is stated below.

######  Corollary 2.

In the setting of Corollary 1, suppose
$\alpha_{\texttt{blue}}=\alpha_{\texttt{red}}$. Then, there exists a unique
optimal mechanism and it is such that for every
$u\notin\partial_{T}(\mathcal{G},V)$,

$\displaystyle\Pr[\mathcal{M}(u)=T(u)]=1-\frac{e^{\varepsilon}-1-\delta(e^{\varepsilon(d+1)}+e^{d\varepsilon}-2)}{e^{d\varepsilon}(e^{\varepsilon}+1)(e^{\varepsilon}-1)},$

where $d$ is the distance of $u$ to the boundary
$\partial_{T}(\mathcal{G},V)$.

###  II-D Suitable Pairs

To prove our results, we introduce a generalized framework that captures the
key conditions of differential privacy. We note that differential privacy
imposes local constraints on neighboring vertices. Although non-neighboring
vertices ultimately constrain each other, they do so only through intermediate
neighboring vertices. These constraints are realized through upper and lower
bounds on the probability of the mechanism outputting a value, as captured in
(1)-(4). Combining (2) and (3), we obtain the upper bound

$\displaystyle
U_{\texttt{DP}}(\alpha):=\min(e^{\varepsilon}\alpha+\delta,\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}},1),$
(8)

where $\alpha=\Pr[\mathcal{M}(u)=j]$. Analogously, combining (1) and (4), we
obtain the lower bound

$\displaystyle
L_{\texttt{DP}}(\alpha):=\max(e^{\varepsilon}\alpha-\delta-e^{\varepsilon}+1,\frac{\alpha-\delta}{e^{\varepsilon}},0).$
(9)

We generalize this notion in the following definition.

######  Definition 12 (Suitable Pair).

Let $L,U:[0,1]\to[0,1]$ be two increasing functions. We call $(L,U)$ a
suitable pair if for every $\alpha\in[0,1]$ the following three properties
hold.

  1. 1.

$L(\alpha)\leq\alpha\leq U(\alpha)$,

  2. 2.

$L(U(\alpha))\leq\alpha\leq U(L(\alpha))$,

  3. 3.

$U(\alpha)\leq 1-L(1-\alpha)$.

The $(\varepsilon,\delta)$-DP lower and upper bounds in (8) and (9) are then a
special case of $(L,U)$ suitable pair.

######  Proposition 2.

The functions $U_{\texttt{DP}}$ and $L_{\texttt{DP}}$ are a suitable pair.

The notion of a suitable pair abstracts away the detailed algebraic
expressions of differential privacy, e.g., those appearing in (1)-(4).
Specifically, the composition $U^{d}$ captures the upper bound condition that
a vertex $u$ imposes on other vertices at distance $d$.444For $d\geq 1$,
$U^{d}$ denotes $d$ compositions of the function $U$. For function $L$,
$L^{d}$ is defined similarly. We now define the notion of privacy in the
suitable pair framework.

######  Definition 13 ($(L,U)$-Privacy).

Let $\mathcal{G}(V,E)$ be a graph and $(L,U)$ be a suitable pair. We say that
a randomized mechanism $\mathcal{M}:V\to Q$ is $(L,U)$-private if, for any
$u\sim v$ and $j\in Q$, it holds that
$\Pr[\mathcal{M}(v)=j]\in[L(\alpha),U(\alpha)]$, where
$\alpha=\Pr[\mathcal{M}(u)=j]$.

In Theorem 2 we generalize Theorem 1 to suitable pairs. We begin by showing an
intermediate lemma that specifies the necessary and sufficient conditions for
the existence of a mechanism extension.

######  Lemma 1.

Let $(L,U)$ be a suitable pair and
$\mathcal{M}^{\prime}:\mathcal{H}_{T}\rightarrow Q$ be a randomized function
on a boundary-hitting set $\mathcal{H}_{T}$. Then, there exists an
$(L,U)$-private mechanism $\mathcal{M}:V\to Q$, extending
$\mathcal{M}^{\prime}$, if and only if, for every $u,v\in\mathcal{H}_{T}$ and
$d=\operatorname{dist}(u,v)$, we have $\alpha\leq U^{d}(\beta)$ and $\beta\leq
U^{d}(\alpha)$, where $\alpha=\Pr[\mathcal{M^{\prime}}(u)=j]$ and
$\beta=\Pr[\mathcal{M^{\prime}}(v)=j]$ for an arbitrarily chosen $j$ from $Q$.

######  Theorem 2.

Let $(L,U)$ be a suitable pair and
$\mathcal{M}^{\prime}:\mathcal{H}_{T}\rightarrow Q$ be a randomized function
on a boundary-hitting set $\mathcal{H}_{T}$. Then, Algorithm 1 either outputs
the optimal $(L,U)$-private extension of $\mathcal{M}^{\prime}$ or no
$(L,U)$-private extension $\mathcal{M}:V\rightarrow Q$ of
$\mathcal{M}^{\prime}$ exists.

Input: Graph $\mathcal{G}(V,E)$, true function $T$, suitable pair functions
$(L,U)$, boundary-hitting set $\mathcal{H}_{T}\subseteq V$, randomized
function $\mathcal{M}^{\prime}:\mathcal{H}_{T}\rightarrow Q$.

Output: Optimal $(L,U)$-private extension $\mathcal{M}:V\rightarrow Q$ of
$\mathcal{M}^{\prime}$ if one exists.

Choose $j\in Q$

for  _$w,v\in\mathcal{H}_{T}$_ do

$d=\operatorname{dist}(w,v).$

_ _if  _
$\Pr[\mathcal{M}^{\prime}(w)=j]>U^{d}(\Pr[\mathcal{M}^{\prime}(v)=j])$ _

 __ or $\Pr[\mathcal{M}^{\prime}(v)=j]>U^{d}(\Pr[\mathcal{M}^{\prime}(w)=j])$
then

return _“No $(L,U)$-private extension exists.”_

end if

end for

for  _$w\in V-\mathcal{H}_{T}$_ do

$\Pr[\mathcal{M}(w)=T(w)]=\min\limits_{u\in\mathcal{H}_{T}}U^{\operatorname{dist}(w,u)}(\Pr[\mathcal{M}^{\prime}(u)=T(w)])$.

end for

return Optimal extension $\mathcal{M}:V\rightarrow Q$ of
$\mathcal{M}^{\prime}$.

Algorithm 1 The Optimal $(L,U)$-Private Extension

Algorithm 1 works as follows. First, it checks whether the randomized function
$\mathcal{M}^{\prime}$ is extensible at all. If there exists a vertex
$w\in\mathcal{H}_{T}$ such that the probability of outputting the true value
$T(w)$ exceeds the $(L,U)$ bounds imposed by all other vertices in
$\mathcal{H}_{T}$, then an extension is not possible.555In Algorithm 1, we
have fixed $j\in Q$ at the beginning of the algorithm. However, this is not
necessary. Based on Lemma 9, it is possible to select a different $j$ in each
iteration of the for-loop. Otherwise, for each $u$ not in $\mathcal{H}_{T}$
the algorithm assigns $\Pr[\mathcal{M}(u)=T(u)]$ to be the minimum upper bound
imposed by the vertices in $\mathcal{H}_{T}$. In this way, it obtains the
unique optimal $(L,U)$-private extension of $\mathcal{M}^{\prime}$. Theorem 1
follows from Algorithm 1 by setting the upper and lower bound functions for DP
according to (8) and (9).

From a computational complexity point of view, the significance of Algorithm 1
is as follows. For a given vertex $u$, a naive approach would consider every
possible path between $u$ and all other vertices in the graph to determine if
it satisfies the privacy constraints. Whereas Algorithm 1 shows that as long
as $\mathcal{H}_{T}$ is a boundary-hitting set, it is sufficient to consider
paths between $u$ and $\mathcal{H}_{T}$, thus reducing computational
complexity. Moreover, one does not need to consider all paths, but only the
shortest path between $u$ and each $w\in\mathcal{H}_{T}$.

However, in many applications, one might not necessarily be interested in
retrieving the whole optimal mechanism but instead in evaluating it on a
particular dataset $u\in V$, reducing complexity even further. For this, we
present Algorithm 2.

Input: Graph $\mathcal{G}(V,E)$, true function $T$, suitable pair functions
$(L,U)$, boundary-hitting set $\mathcal{H}_{T}\subseteq V$, randomized
function $\mathcal{M}^{\prime}:\mathcal{H}_{T}\rightarrow Q$, a vertex $u\in
V-\mathcal{H}_{T}$.

Output: Optimal $(L,U)$-private extension $\mathcal{M}(u)$.

Choose $j\in Q$

for  _$w,v\in\mathcal{H}_{T}$_ do

$d=\operatorname{dist}(w,v).$

_ _if  _
$\Pr[\mathcal{M}^{\prime}(w)=j]>U^{d}(\Pr[\mathcal{M}^{\prime}(v)=j])$ _

 __ or $\Pr[\mathcal{M}^{\prime}(v)=j]>U^{d}(\Pr[\mathcal{M}^{\prime}(w)=j])$
then

return _“No $(L,U)$-private extension exists.”_

end if

end for

return
$\Pr[\mathcal{M}(u)=T(u)]=\min\limits_{w\in\mathcal{H}_{T}}U^{\operatorname{dist}(w,u)}(\Pr[\mathcal{M}^{\prime}(w)=T(u)])$.

Algorithm 2 The Optimal $(L,U)$-Private Extension Evaluated at on Particular
Dataset

Whereas in Algorithm 1 we must compute all shortest paths between vertices in
$V-\mathcal{H}_{T}$ and those in $\mathcal{H}_{T}$, in Algorithm 2 we need
only to compute the shortest path between $u$ and $\mathcal{H}_{T}$. If we
denote the ball centered at the vertex $u$ with radius at maximum distance to
$\mathcal{H}_{T}$ by B, then the complexity of finding the shortest path
between $u$ and $\mathcal{H}_{T}$ using the Dijkstra Algorithm [22] is
$\Theta(|E(\texttt{B})|+|V(\texttt{B})|\log|V(\texttt{B})|)$, where
$E(\texttt{B})$ and $V(\texttt{B})$ are the edges and vertices included in the
ball, respectively. The complexity of checking for the existence of an
extension is $\mathcal{O}(|\mathcal{H}_{T}|^{2})$. Thus, the time complexity
of Algorithm 2 is
$\Theta(|E(\texttt{B})|+|V(\texttt{B})|\log|V(\texttt{B})|)+\mathcal{O}(|\mathcal{H}_{T}|^{2})$.

In Proposition 1, we show that when the $(L,U)$ suitable pair in Algorithm 1
comes from the differential privacy framework, $U^{d}(\alpha)=p(d,\alpha)$
where $p(d,\alpha)$ was defined in Definition 9. The following example shows
how Algorithm 1 works.

######  Example 3.

Consider the graph in Fig. 2 again and let the boundary hitting set be
$\mathcal{H}_{T}=\\{v_{1},v_{4}\\}$. Let $\epsilon=\log(2)$, $\delta=0$ and
fix the mechanism on $\mathcal{H}_{T}$ as
$\alpha=\Pr[\mathcal{M}(v_{1})=\texttt{blue}]=1-\Pr[\mathcal{M}(v_{1})=\texttt{red}]=0.3$
and
$\beta=\Pr[\mathcal{M}(v_{4})=\texttt{blue}]=1-\Pr[\mathcal{M}(v_{4})=\texttt{red}]=0.1$.
Note that $\operatorname{dist}(v_{1},v_{4})=3$.

Algorithm 1 we first checks that the mechanism can be extended. Let
$j=\texttt{blue}$. Algorithm 1 checks that $0.3\leq U^{3}(0.1)=p(3,0.1)=0.7$
and $0.1\leq U^{3}(0.3)=p(3,0.3)=0.9$. Therefore, the partial mechanism can be
extended.666For $\epsilon=\log(2)$ and $\delta=0$, (6) gives $\tau=2$ for
$\alpha=0.1$ and $\tau=1$ for $\alpha=0.3$. Therefore, $p(3,0.1)=0.7$ and
$p(3,0.3)=0.9$.

Next, Algorithm 1 assigns optimal values to
$\Pr[\mathcal{M}(v_{2})=\texttt{blue}]$, and
$\Pr[\mathcal{M}(v_{3})=\texttt{blue}]$. Let us first consider $v_{2}$ and the
upper bound that each vertex $v_{1}$ and $v_{4}$ impose on $v_{2}$. From
Definition 9, we have $U^{\operatorname{dist}(v_{1},v_{2})}(0.3)=p(1,0.3)=0.6$
and $U^{\operatorname{dist}(v_{2},v_{4})}(0.1)=p(2,0.1)=0.4$. Therefore,
$\Pr[\mathcal{M}(v_{2})=\texttt{blue}]=0.4$. This is remarkable in the sense
that $v_{1}$ which is the closest vertex to $v_{2}$ in the boundary hitting
set is not the one that imposes the tightest upper bound on
$\Pr[\mathcal{M}(v_{2})=\texttt{blue}]$. Instead, $v_{4}$ which is farther
from $v_{2}$, has a more restrictive effect on $v_{4}$ for taking its true
value blue. Finally, consider $v_{3}$. We have
$U^{\operatorname{dist}(v_{1},v_{3})}(0.3)=p(2,0.3)=0.8$ and
$U^{\operatorname{dist}(v_{3},v_{4})}(0.1)=p(1,0.1)=0.2$. Therefore,
$\Pr[\mathcal{M}(v_{3})=\texttt{blue}]=0.2$.

##  III Proofs

In this section, we prove all our results. We start by showing some
intermediate lemmas that we use.

###  III-A Intermediate Lemmas

This lemma states a graph-theoretic result that we use in various proofs.

######  Lemma 2.

Let $\mathcal{G}(V,E)$ be a graph and $u\sim v\in V$. Then for every vertex
$w\in V$, we have $\operatorname{dist}(u,w)\leq\operatorname{dist}(v,w)+1$.

###### Proof.

Consider a shortest path $w=w_{0},w_{1},\ldots,w_{\operatorname{dist}(w,v)}=v$
connecting $w$ to $v$. Since $u$ is a neighbor of $v$, then
$w=w_{0},w_{1},\ldots,w_{\operatorname{dist}(w,v)}=v,u$ is a path connecting
$w$ to $u$ with length $\operatorname{dist}(w,v)+1$. Thus,
$d(w,u)\leq\operatorname{dist}(w,v)+1$. ∎

The triangular inequality follows as an extension, where for any $u,v,w\in V$,
$\operatorname{dist}(u,w)\leq\operatorname{dist}(u,v)+\operatorname{dist}(v,w)$.

In the next two lemmas, we provide explicit forms for the upper bound function
$U_{\texttt{DP}}$ and the lower bound function $L_{\texttt{DP}}$ in the
suitable pair, corresponding to the $(\varepsilon,\delta)$-DP mechanism.

######  Lemma 3.

The upper bound function in (8) can be rewritten as follows.

$U_{\texttt{DP}}(\alpha)=\left\\{\begin{aligned}
&e^{\varepsilon}\alpha+\delta&{\text{ if
}}&\alpha\leq\frac{1-\delta}{e^{\varepsilon}+1},\\\
&\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}&{\text{ if
}}&\frac{1-\delta}{e^{\varepsilon}+1}\leq\alpha\leq 1-\delta,\\\ &1&\text{ if
}&1-\delta\leq\alpha.\end{aligned}\right.$

###### Proof.

In the first case,

$\displaystyle\alpha\leq\frac{1-\delta}{e^{\varepsilon}+1}$
$\displaystyle\Leftrightarrow(e^{2\varepsilon}-1)\alpha\leq(e^{\varepsilon}-1)(1-\delta)$
$\displaystyle\Leftrightarrow e^{2\varepsilon}\alpha-\alpha\leq
e^{\varepsilon}-1+\delta-e^{\varepsilon}\delta$ $\displaystyle\Leftrightarrow
e^{2\varepsilon}\alpha+e^{\varepsilon}\delta\leq\alpha-1+e^{\varepsilon}+\delta$
$\displaystyle\Leftrightarrow
e^{\varepsilon}\alpha+\delta\leq\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}},$

where the first equivalence holds if $e^{\varepsilon}-1>0$; if
$e^{\varepsilon}-1=0$ the last inequality also holds. Also,

$\displaystyle\alpha\leq\frac{1-\delta}{e^{\varepsilon}+1}$
$\displaystyle\Leftrightarrow\alpha e^{\varepsilon}+\alpha\leq 1-\delta$
$\displaystyle\Leftrightarrow\alpha e^{\varepsilon}+\delta\leq 1-\alpha$
$\displaystyle\Rightarrow\alpha e^{\varepsilon}+\delta\leq 1.$

In the second case,

$\displaystyle\alpha\leq 1-\delta$
$\displaystyle\Leftrightarrow\alpha-1+e^{\varepsilon}+\delta\leq
e^{\varepsilon}$
$\displaystyle\Leftrightarrow\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}\leq
1.$

Finally,

$\displaystyle 1-\delta\leq\alpha$ $\displaystyle\Leftrightarrow
e^{\varepsilon}\leq e^{\varepsilon}+\delta-1+\alpha$
$\displaystyle\Leftrightarrow
1\leq\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}.$

∎

######  Lemma 4.

The lower bound function in (9) can be rewritten as follows.

$L_{\texttt{DP}}(\alpha)=\left\\{\begin{aligned} &0&{\text{ if
}}&\alpha\leq\delta,\\\ &\frac{\alpha-\delta}{e^{\varepsilon}}&{\text{ if
}}&\delta\leq\alpha\leq\frac{\delta+e^{\varepsilon}}{e^{\varepsilon}+1},\\\
&e^{\varepsilon}\alpha-\delta-e^{\varepsilon}+1&{\text{ if
}}&\alpha\geq\frac{\delta+e^{\varepsilon}}{e^{\varepsilon}+1}.\end{aligned}\right.$

###### Proof.

Note that $L_{\texttt{DP}}(\alpha)=0$ if and only if
$e^{\varepsilon}\alpha-\delta-e^{\varepsilon}+1\leq 0$ and
$\frac{\alpha-\delta}{e^{\varepsilon}}\leq 0$. This will happen if and only if
$\alpha\leq\frac{e^{\varepsilon}-1+\delta}{e^{\varepsilon}}$ and
$\alpha\leq\delta$, respectively. Since
$\delta\leq\frac{e^{\varepsilon}-1+\delta}{e^{\varepsilon}}$, the first case
follows.

For the second and third cases,

$\displaystyle\alpha\leq\frac{\delta+e^{\varepsilon}}{e^{\varepsilon}+1}$
$\displaystyle\Leftrightarrow(e^{\varepsilon}+1)\alpha\leq(\delta+e^{\varepsilon})$
$\displaystyle\Leftrightarrow(e^{2\varepsilon}-1)\alpha\leq\delta(e^{\varepsilon}-1)+e^{\varepsilon}(e^{\varepsilon}-1)$
$\displaystyle\Leftrightarrow
e^{2\varepsilon}\alpha-e^{\varepsilon}\delta-e^{2\varepsilon}+e^{\varepsilon}\leq\alpha-\delta$
$\displaystyle\Leftrightarrow
e^{\varepsilon}\alpha-\delta-e^{\varepsilon}+1\leq\frac{\alpha-\delta}{e^{\varepsilon}}.$

∎

The next lemma establishes the symmetric nature of suitable pair functions.

######  Lemma 5.

Let $\alpha_{1},\alpha_{2}\in[0,1]$ and $(L,U)$ be a suitable pair. Then,
$\alpha_{2}\in[L(\alpha_{1}),U(\alpha_{1})]$ if and only if
$\alpha_{1}\in[L(\alpha_{2}),U(\alpha_{2})]$.

###### Proof.

Let $(L,U)$ be a suitable pair and suppose that
$L(\alpha_{1})\leq\alpha_{2}\leq U(\alpha_{1})$. In particular, we have
$L(\alpha_{1})\leq\alpha_{2}$. Since by definition, $U$ is an increasing
function, it follows that $U(L(\alpha_{1}))\leq U(\alpha_{2})$. On the other
hand, according to the definition of $(L,U)$ suitable pair, $\alpha_{1}\leq
U(L(\alpha_{1}))$. Therefore, $\alpha_{1}\leq U(L(\alpha_{1}))\leq
U(\alpha_{2})$.

Similarly, we have $\alpha_{2}\leq U(\alpha_{1})$. Since $L$ is also an
increasing function, we have $L(\alpha_{2})\leq L(U(\alpha_{1}))$. According
to the definition of $(L,U)$ suitable pair, $L(U(\alpha_{1}))\leq\alpha_{1}$.
Therefore, $L(\alpha_{2})\leq L(U(\alpha_{1}))\leq\alpha_{1}$. Thus,
$\alpha_{1}\in[L(\alpha_{2}),U(\alpha_{2})]$.

The reverse implication follows analogously. ∎

######  Lemma 6.

Mechanism $\mathcal{M}:V\to Q$ is $(L,U)$-private if and only if for every
color $j\in Q$ and every two datasets $u,v\in V$ we have:

$\beta\in[L^{d}(\alpha),U^{d}(\alpha)],$

where $\alpha:=\Pr[\mathcal{M}(u)=j]$, $\beta:=\Pr[\mathcal{M}(v)=j]$ and
$d=\operatorname{dist}(u,v)$ is the distance between them.

###### Proof.

We first prove the forward direction through induction. For the case $d=1$,
the claim follows directly from Definition 13. Suppose that the claim holds
for $d$. Let $u,v\in V$ such that $\operatorname{dist}(u,v)=d+1$. Consider a
path of length $d+1$ from $u$ to $v$. Let $w$ be the one-before-the-last
vertex in the path, where $\operatorname{dist}(u,w)=d$. Denote
$\gamma:=\Pr[\mathcal{M}(w)=j]$. By the induction hypothesis for the vertices
$u,w$ we have $\gamma\in[L^{d}(\alpha),U^{d}(\alpha)]$. Also, since $L,U$ are
increasing functions, we have

$\gamma\geq L^{d}(\alpha)\Rightarrow L(\gamma)\geq L^{d+1}(\alpha)$
$\gamma\leq U^{d}(\alpha)\Rightarrow U(\gamma)\leq U^{d+1}(\alpha)$

Thus, $L^{d+1}(\alpha)\leq L(\gamma)\leq U(\gamma)\leq U^{d+1}(\alpha)$.
Since, $w$ and $v$ are adjacent, we have $\beta\in[L(\gamma),U(\gamma)]$.
Therefore,

$L^{d+1}(\alpha)\leq L(\gamma)\leq\beta\leq U(\gamma)\leq U^{d+1}(\alpha).$

Also, the backward can be proved by only considering neighbor vertices. This
completes the proof. ∎

The next lemma extends the third condition of the suitable pair in Definition
12.

######  Lemma 7.

Let $d$ be a positive integer and $(L,U)$ be a suitable pair. Then for every
$\alpha\in[0,1]$ we have:

$\displaystyle U^{d}(\alpha)$ $\displaystyle\leq 1-L^{d}(1-\alpha).$

###### Proof.

We prove this by induction on $d$ and the proof only uses the monotonicity of
the upper bound function $U$. For a fixed $\alpha\in[0,1]$ and $d=1$, we have
the following equations directly from the third condition in Definition 12:

$\displaystyle U(\alpha)+L(1-\alpha)\leq 1\iff U(\alpha)\leq 1-L(1-\alpha).$

Assume that the condition in the lemma is satisfied for $d$. Then, we have:

$\displaystyle U^{d}(\alpha)$ $\displaystyle\leq 1-L^{d}(1-\alpha),$
$\displaystyle\Rightarrow U\big{(}U^{d}(\alpha)\big{)}$ $\displaystyle\leq
U\big{(}1-L^{d}(1-\alpha)\big{)}$ $\displaystyle\leq
1-L\Big{(}1-\big{(}1-L^{d}(1-\alpha)\big{)})\Big{)}$
$\displaystyle=1-L\big{(}L^{d}(1-\alpha)\big{)}$
$\displaystyle=1-L^{d+1}(1-\alpha),$

which completes the proof. ∎

The following Lemma is a simple extension of the second property of an $(L,U)$
suitable pair, which we will use.

######  Lemma 8.

For every $\alpha\in[0,1]$ the following holds:

$\alpha\leq U^{d}(L^{d}(\alpha)).$

###### Proof.

We prove this by iteratively applying the definition of $(L,U)$ suitable pair
as follows:

$\displaystyle U^{d}(L^{d}(\alpha))$
$\displaystyle=U^{d-1}\Big{(}U\big{(}L(L^{d-1}(\alpha)\big{)}\Big{)}\geq\
U^{d-1}(L^{d-1}(\alpha))$ $\displaystyle\geq\ldots\geq
U(L(\alpha))\geq\alpha.$

∎

######  Lemma 9.

Let $\alpha,\beta\in[0,1]$ and $d\geq 1$ be given and assume that the
following two relations hold: $\alpha\leq U^{d}(\beta)$ and $\beta\leq
U^{d}(\alpha)$. Then, we have:

$\displaystyle 1-\beta$ $\displaystyle\geq L^{d}(1-\alpha),$ (10)
$\displaystyle 1-\alpha$ $\displaystyle\leq U^{d}(1-\beta),$ (11)
$\displaystyle 1-\alpha$ $\displaystyle\geq L^{d}(1-\alpha),$ (12)
$\displaystyle 1-\beta$ $\displaystyle\leq U^{d}(1-\alpha),$ (13)
$\displaystyle\alpha$ $\displaystyle\leq L^{d}(\beta),$ (14)
$\displaystyle\beta$ $\displaystyle\leq L^{d}(\alpha).$ (15)

###### Proof.

$\displaystyle\beta\leq U^{d}(\alpha)\Rightarrow 1-\beta\geq
1-U^{d}(\alpha)\underset{(a)}{\geq}L^{d}(1-\alpha),$ (16)

where $(a)$ follows from Lemma 7. Similarly, we have $1-\alpha\geq
L^{d}(1-\beta)$.

Now, we apply $U^{d}$ to the derived relation in (16) to write

$\displaystyle U^{d}(1-\beta)\geq
U^{d}(L^{d}(1-\alpha))\underset{(a)}{\geq}1-\alpha,$ (17)

where $(a)$ follows from Lemma 8. Similarly, we have $U^{d}(1-\alpha)\geq
1-\beta$.

The one before last inequality follows from (17) and the fact that
$U^{d}(1-\beta)\leq 1-L^{d}(\beta)$ according to Lemma 7. Similarly, we have
$L^{d}(\alpha)\leq\beta$. ∎

The above lemma gives a sufficient condition for checking the feasibility of
mechanism extension only based on the upper bound function $U$ (instead of
both $L$ and $U$) and for one mechanism value, say $j\in Q$ (instead of both
values in $Q$).

###  III-B Proof of Lemma 1

We first prove the forward direction. Assume that there exists an
$(L,U)$-private mechanism $\mathcal{M}:V\to Q$, extending
$\mathcal{M}^{\prime}$. By the definition of mechanism extension
$\mathcal{M}|_{\mathcal{H}_{T}}=\mathcal{M^{\prime}}$. Therefore, for any
$u,v\in\mathcal{H}_{T}$,
$\Pr[\mathcal{M}(u)=j]=\Pr[\mathcal{M^{\prime}}(u)=j]$ and
$\Pr[\mathcal{M}(v)=j]=\Pr[\mathcal{M^{\prime}}(v)=j]$. The result then
follows directly from Lemma 6.

Now we prove the reverse direction by an explicit construction of
$\mathcal{M}$. Fix $j\in Q$. Assume that for every $u,v\in\mathcal{H}_{T}$ and
$d=\operatorname{dist}(u,v)$, we have $\alpha\leq U^{d}(\beta)$ and $\beta\leq
U^{d}(\alpha)$, where $\alpha=\Pr[\mathcal{M^{\prime}}(u)=j]$ and
$\beta=\Pr[\mathcal{M^{\prime}}(v)=j]$. We show how to construct a valid
$(L,U)$-private extension $\mathcal{M}$ from $\mathcal{M^{\prime}}$. First,
set $\mathcal{M}|_{\mathcal{H}_{T}}=\mathcal{M^{\prime}}$. If
$\mathcal{H}_{T}=V$, we are done. Otherwise, for every
$w\notin\mathcal{H}_{T}$ assign

$\displaystyle\Pr[\mathcal{M}(w)=T(w)]=\min\limits_{u\in\mathcal{H}_{T}}U^{\operatorname{dist}(w,u)}(\Pr[\mathcal{M}^{\prime}(u)=T(w)]).$
(18)

For $w\notin\mathcal{H}_{T}$, let $u_{w}\in\mathcal{H}_{T}$ be a minimizer of
(18) and let $\alpha_{u_{w}}:=\Pr[\mathcal{M^{\prime}}(u_{w})=T(w)]$. That is,
$U^{\operatorname{dist}(w,u_{w})}(\alpha_{u_{w}})\leq
U^{\operatorname{dist}(w,u)}(\Pr[\mathcal{M}^{\prime}(u)=T(w)])$ for any
$u\in\mathcal{H}_{T}$. We must prove that this mechanism is $(L,U)$-private
according to Defintion 13. However, it suffices to fix a $j\in Q$ a priori and
for every $v\sim w\in V$ only prove $\alpha_{w}\leq U(\alpha_{v})$ and
$\alpha_{v}\leq U(\alpha_{w})$, where $\alpha_{v}=\Pr[\mathcal{M}(v)=j]$ and
$\alpha_{w}=\Pr[\mathcal{M}(w)=j]$. The reminaing $(L,U)$ relations follow
from Lemmas 6 and 9. We need to consider three cases.

Case 1 ($v,w\in\mathcal{H}_{T}$): This is automatically satisfied by the
assumption in the reverse direction of the Lemma (for
$d=\operatorname{dist}(v,w)=1$).

Case 2 ($w\notin\mathcal{H}_{T}$, $v\in\mathcal{H}_{T}$): We consider two
subcases depending on the true value of dataset $w$.

Subcase 2.1 ($j=T(w)$): We have

$\displaystyle\alpha_{w}$
$\displaystyle=\Pr[\mathcal{M}(w)=T(w)]=U^{\operatorname{dist}(w,u_{w})}(\alpha_{u_{w}})$
$\displaystyle\underset{(a)}{\leq}U^{\operatorname{dist}(w,v)}(\Pr[\mathcal{M}^{\prime}(v)=T(w)])$
$\displaystyle\underset{(b)}{=}U(\Pr[\mathcal{M}(v)=T(w)]):=U(\alpha_{v}),$

where $(a)$ follows because $v\in\mathcal{H}_{T}$ and hence is part of the
mininimization in (18). In $(b)$ we used the fact that $v,w$ are neighbours
and $\mathcal{M}|_{\mathcal{H}_{T}}=\mathcal{M^{\prime}}$. Furthermore,

$\displaystyle\alpha_{v}$
$\displaystyle=\Pr[\mathcal{M}(v)=T(w)]\underset{(a)}{\leq}U^{\operatorname{dist}(v,u_{w})}(\alpha_{u_{w}})$
$\displaystyle\underset{(b)}{\leq}U^{\operatorname{dist}(v,w)}(U^{\operatorname{dist}(w,u_{w})}(\alpha_{u_{w}})):=U(\alpha_{w}),$

where $(a)$ follows the assumption of reverse part of lemma for
$v,u_{w}\in\mathcal{H}_{T}$. Inequality $(b)$ follows from triangular
inequality and the propoerty of $(L,U)$ pair that for $d_{1}\geq d_{2}$ and
any $\alpha\in[0,1]$, we have $U^{d_{1}}(\alpha)\geq U^{d_{2}}(\alpha)$. The
last equality follows from construction (18) and the fact that $v\sim w$.

Subcase 2.2 ($j\neq T(w)$): This subcase can be proved by using the results we
just proved for $j=T(w)$ and invoking Lemma 9. Since we now have
$1-\alpha_{w}\leq U(1-\alpha_{v})$ and $1-\alpha_{v}\leq U(1-\alpha_{w})$.

Case 3 ($v,w\notin\mathcal{H}_{T}$): Note that we must have $T(v)=T(w)$.
Otherwise, $T(v)\neq T(w)$ means that two neighbors $v\sim w$ with different
true values are both outside of $\mathcal{H}_{T}$, which contradicts the
definition of a boundary-hitting set. We consider two subcases depending on
the true value of these vertices.

Subcase 3.1: ($j=T(w)=T(v)$) We have

$\displaystyle\alpha_{w}$
$\displaystyle:=U^{\operatorname{dist}(w,u_{w})}(\alpha_{u_{w}})$
$\displaystyle\underset{(a)}{\leq}U^{\operatorname{dist}(w,u_{v})}(\alpha_{u_{v}})\underset{(b)}{\leq}U^{\operatorname{dist}(w,v)+\operatorname{dist}(v,u_{v})}(\alpha_{u_{v}})$
(19)
$\displaystyle=U^{\operatorname{dist}(w,v)}(U^{\operatorname{dist}(v,u_{v})}(\alpha_{u_{v}})):=U(\alpha_{v}),$

where $(a)$ follows because $j=T(v)=T(w)$ and hence, according to construction
(18) there must exist $u_{v}\in\mathcal{H}_{T}$ such that
$\alpha_{v}:=U^{\operatorname{dist}(v,u_{v})}(\alpha_{u_{v}})$. Inequality
$(b)$ follows from applying the triangular inequality.

By swapping the roles of $\alpha_{v}$ and $\alpha_{w}$ in the above, we obtain
$\alpha_{v}\leq U(\alpha_{w})$.

Subcase 3.2 ($j\neq T(w)=T(v)$): This follows directly from case 3.1 just
proved and Lemma 9.

###  III-C Proof of Theorem 2

We note that the value assigned to $\Pr[\mathcal{M}(w)=T(w)]$ in Algorithm 1
is the same as in (18). Thus, by Lemma 1 the algorithm finds an
$(L,U)$-private extension if it exists.

We now show that the private mechanism is the unique optimal mechanism.

Suppose there exists another $(L,U)$-private mechanism $\mathcal{M}_{2}$ which
extends $\mathcal{M}^{\prime}$. Let $w\in V$ be a vertex with $T(w)=j$. Then,
by Lemma 6, for every $u\in\mathcal{H}_{T}$, it follows that
$\Pr[\mathcal{M}_{2}(w)=j]\leq
U^{\operatorname{dist}(w,u)}\left(\Pr[\mathcal{M}^{\prime}(u)=j]\right)$.
Thus,
$\Pr[\mathcal{M}_{2}(w)=j]\leq\min\limits_{u\in\mathcal{H}_{T}}U^{\operatorname{dist}(w,u)}(\Pr[\mathcal{M}^{\prime}(u)=j])=\Pr[\mathcal{M}(w)=j]$.
Thus, $\Pr[\mathcal{M}_{2}(w)=T(w)]\leq\Pr[\mathcal{M}(w)=T(w)]$ for every
$w\in V$. Thus, $\mathcal{M}$ dominates every other $\mathcal{M}_{2}$ and is
therefore the unique optimal.

###  III-D Proof of Proposition 2

The functions $U_{\texttt{DP}}$ and $L_{\texttt{DP}}$ are a suitable pair if
they are increasing functions and, for every $\alpha\in[0,1]$ they satisfy the
following conditions:

  1. 1.

$L_{\texttt{DP}}(\alpha)\leq\alpha\leq U_{\texttt{DP}}(\alpha)$,

  2. 2.

$L_{\texttt{DP}}(U_{\texttt{DP}}(\alpha))\leq\alpha\leq
U_{\texttt{DP}}(L_{\texttt{DP}}(\alpha))$,

  3. 3.

$U_{\texttt{DP}}(\alpha)\leq 1-L_{\texttt{DP}}(1-\alpha)$.

We prove each condition as its own Lemma. We first prove the third condition
as it will be used in proving the first condition.

######  Lemma 10.

$U_{\texttt{DP}}(\alpha)=1-L_{\texttt{DP}}(1-\alpha)$.

###### Proof.

Assume $L_{\texttt{DP}}(1-\alpha)>0$ and $U_{\texttt{DP}}(\alpha)<1$. Then,

$\displaystyle
U_{\texttt{DP}}(\alpha):=\min(e^{\varepsilon}\alpha+\delta,\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}).$
(20)

And,

$\displaystyle
L_{\texttt{DP}}(1-\alpha):=\max(1-e^{\varepsilon}\alpha-\delta,\frac{1-\alpha-\delta}{e^{\varepsilon}}).$
(21)

Therefore, we have:

$\displaystyle U_{\texttt{DP}}(\alpha)+L_{\texttt{DP}}(1-\alpha)$
$\displaystyle=\min(e^{\varepsilon}\alpha+\delta,\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}})$
$\displaystyle\quad+\max(1-e^{\varepsilon}\alpha-\delta,\frac{1-\alpha-\delta}{e^{\varepsilon}}).$

Then, we have:

$\displaystyle U_{\texttt{DP}}(\alpha)=e^{\varepsilon}\alpha+\delta$
$\displaystyle\iff$ $\displaystyle
e^{\varepsilon}\alpha+\delta\leq\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}$
$\displaystyle\iff$ $\displaystyle e^{\varepsilon}\alpha+\delta\leq
1+\frac{\delta-1+\alpha}{e^{\varepsilon}}$ $\displaystyle\iff$
$\displaystyle\frac{1-\delta-\alpha}{e^{\varepsilon}}\leq
1-e^{\varepsilon}\alpha-\delta$ $\displaystyle\iff$ $\displaystyle
L_{\texttt{DP}}(1-\alpha)=1-e^{\varepsilon}\alpha-\delta.$

Therefore, $U_{\texttt{DP}}(\alpha)+L_{\texttt{DP}}(1-\alpha)=1$ whenever
$U_{\texttt{DP}}(\alpha)=e^{\varepsilon}\alpha+\delta$. Similarly,

$\displaystyle
U_{\texttt{DP}}(\alpha)=\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}$
$\displaystyle\iff$ $\displaystyle
e^{\varepsilon}\alpha+\delta\geq\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}$
$\displaystyle\iff$ $\displaystyle e^{\varepsilon}\alpha+\delta\geq
1+\frac{\delta-1+\alpha}{e^{\varepsilon}}$ $\displaystyle\iff$
$\displaystyle\frac{1-\delta-\alpha}{e^{\varepsilon}}\geq
1-e^{\varepsilon}\alpha-\delta$ $\displaystyle\iff$ $\displaystyle
L_{\texttt{DP}}(1-\alpha)=\frac{1-\delta-\alpha}{e^{\varepsilon}}.$

Therefore, $U_{\texttt{DP}}(\alpha)+L_{\texttt{DP}}(1-\alpha)=1$ again.
Finally, Lemma 3 implies that:

$\displaystyle U_{\texttt{DP}}(\alpha)=1\iff 1-\delta\leq\alpha\iff$ (22)
$\displaystyle 1-\delta-\alpha\leq
0\iff\frac{1-\delta-\alpha}{e^{\varepsilon}}\leq 0,$ (23)

and

$\displaystyle U_{\texttt{DP}}(\alpha)=1\iff 1-\delta\leq\alpha\iff$ (24)
$\displaystyle 1-\delta-\alpha\leq 0\Rightarrow
1-\delta-e^{\varepsilon}\alpha\leq 0.$ (25)

Therefore, $L_{\texttt{DP}}(1-\alpha)=0$ and
$U_{\texttt{DP}}(\alpha)+L_{\texttt{DP}}(1-\alpha)=1.$ ∎

######  Lemma 11.

$L_{\texttt{DP}}(\alpha)\leq\alpha\leq U_{\texttt{DP}}(\alpha)$.

###### Proof.

We first prove $U_{\texttt{DP}}(\alpha)\geq\alpha$. We have 3 cases based on
the value of $U_{\texttt{DP}}(\alpha)$ following from Lemma 3.

Case 1 (when $U_{\texttt{DP}}(\alpha)=e^{\varepsilon}\alpha+\delta$): Since
$e^{\varepsilon}\geq 1$ and $\delta\geq 0$ it holds that
$U_{\texttt{DP}}(\alpha)=e^{\varepsilon}\alpha+\delta\geq\alpha$.

Case 2 (when
$U_{\texttt{DP}}(\alpha)=\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}$):
Since $e^{\varepsilon}\geq 1$, $\alpha\leq 1$ and $\delta\geq 0$ we have

$\displaystyle 1+\frac{\delta}{(e^{\varepsilon}-1)}\geq 1\geq\alpha$
$\displaystyle\iff$ $\displaystyle
1+\frac{\delta}{(e^{\varepsilon}-1)}\geq\alpha$ $\displaystyle\iff$
$\displaystyle(e^{\varepsilon}-1)+\delta\geq(e^{\varepsilon}-1)\alpha$
$\displaystyle\iff$ $\displaystyle e^{\varepsilon}+\delta-1\geq
e^{\varepsilon}\alpha-\alpha$ $\displaystyle\iff$ $\displaystyle
e^{\varepsilon}+\delta-1+\alpha\geq e^{\varepsilon}\alpha$ $\displaystyle\iff$
$\displaystyle\frac{e^{\varepsilon}+\delta-1+\alpha}{e^{\varepsilon}}\geq\alpha.$

Case 3 (when $U_{\texttt{DP}}(\alpha)=1$): Follows from $\alpha\leq 1$.

We now show that $L_{\texttt{DP}}(\alpha)\leq\alpha$. It follows from Lemma 10
and what we just proved that
$1-L_{\texttt{DP}}(\alpha)=U_{\texttt{DP}}(1-\alpha)\geq 1-\alpha$. Therefore,
$\alpha\geq L_{\texttt{DP}}(\alpha)$.

∎

######  Lemma 12.

$L_{\texttt{DP}}(U_{\texttt{DP}}(\alpha))\leq\alpha\leq
U_{\texttt{DP}}(L_{\texttt{DP}}(\alpha))$.

###### Proof.

First, we prove the first inequality. We write
$L_{\texttt{DP}}(U_{\texttt{DP}}(\alpha))$ as follows:

$\displaystyle
L_{\texttt{DP}}(U_{\texttt{DP}}(\alpha))=\max(0,e^{\varepsilon}U_{\texttt{DP}}(\alpha)-\delta-e^{\varepsilon}+1,\frac{U_{\texttt{DP}}(\alpha)-\delta}{e^{\varepsilon}}).$
(26)

We will have $L_{\texttt{DP}}(U_{\texttt{DP}}(\alpha))\leq\alpha$ if and only
if each expression in the $\max$ expression above is less than $\alpha$.
Obviously $0\leq\alpha$ is true. The other conditions are equivalently written
below:

$\displaystyle
e^{\varepsilon}U_{\texttt{DP}}(\alpha)-\delta-e^{\varepsilon}+1\leq\alpha$
$\displaystyle\iff
U_{\texttt{DP}}(\alpha)\leq\frac{\alpha+\delta+e^{\varepsilon}-1}{e^{\varepsilon}},$
$\displaystyle\frac{U_{\texttt{DP}}(\alpha)-\delta}{e^{\varepsilon}}\leq\alpha$
$\displaystyle\iff U_{\texttt{DP}}(\alpha)\leq e^{\varepsilon}\alpha+\delta,$

where the inequalities are true according to the definion of $U_{\texttt{DP}}$
in (8). Similarly, we have $\alpha\leq
U_{\texttt{DP}}(L_{\texttt{DP}}(\alpha))$. ∎

The last step of completing the proof of Proposition 2 is to prove that both
functions $U_{\texttt{DP}}$ and $L_{\texttt{DP}}$ are increasing. However,
this can be done by using the equivalent definition of
$U_{\texttt{DP}}(\alpha)$ in Lemma 3. In the first two cases, this function is
linear and in the third case, it is a constant. Also, this function is
continuous. For proving the same for $L_{\texttt{DP}}(\alpha)$, we use the
fact that $U_{\texttt{DP}}(1-\alpha)=1-L_{\texttt{DP}}(\alpha)$. Therefore
$L_{\texttt{DP}}(\alpha)=1-U_{\texttt{DP}}(1-\alpha)$ is an increasing
function.

###  III-E Proof of Proposition 1

Via Proposition 2, $(L_{\texttt{DP}},U_{\texttt{DP}})$ are $(L,U)$ suitable
pairs. Therefore, by Lemma 6, $\mathcal{M}$ will be $(\varepsilon,\delta)$-DP
if an only if for every color $j\in Q$ and every $u,v\in V$ we have:

$\beta\in[L^{d}(\alpha),U^{d}(\alpha)],$

where $\alpha:=\Pr[\mathcal{M}(u)=j]$, $\beta:=\Pr[\mathcal{M}(v)=j]$ and
$d=\operatorname{dist}(u,v)$ is the distance between them. Therefore, we first
compute and simplify $U_{\texttt{DP}}^{d}(\alpha)$. We use Lemma 3 for this.

Part 1 (Showing that $\beta\leq U_{\texttt{DP}}^{d}(\alpha)$): First assume
that there exists some $\tau$ such that for all $1\leq d\leq\tau$, we have
$\min(e^{\varepsilon}U_{\texttt{DP}}^{d-1}(\alpha)+\delta,\frac{U_{\texttt{DP}}^{d-1}(\alpha)-1+e^{\varepsilon}+\delta}{e^{\varepsilon}},1)=e^{\varepsilon}U_{\texttt{DP}}^{d-1}(\alpha)+\delta$.
That is, the first case in Lemma 3 is the tightest upper bound on
$U_{\texttt{DP}}^{d}(\alpha)=U(U_{\texttt{DP}}^{d-1}(\alpha))$. We will soon
find the largest $\tau$ for which this can happen. Iterating over
$d=\tau,\tau-1,\cdots,1$, we will calculate the closed-form expression through
induction as follows.

$\displaystyle\mathllap{U}_{\texttt{DP}}^{d}(\alpha)$
$\displaystyle=e^{\varepsilon}U_{\texttt{DP}}^{d-1}(\alpha)+\delta$
$\displaystyle=e^{\varepsilon}\big{(}e^{\varepsilon}U_{\texttt{DP}}^{d-2}(\alpha)+\delta\big{)}+\delta$
$\displaystyle\cdots$
$\displaystyle=e^{\varepsilon}\Bigg{(}e^{\varepsilon}\Big{(}\cdots\big{(}e^{\varepsilon}U_{\texttt{DP}}(\alpha)+\delta\big{)}\cdots+\delta\Big{)}+\delta\Bigg{)}+\delta$
$\displaystyle=e^{\varepsilon}\Bigg{(}e^{\varepsilon}\Big{(}\cdots\big{(}e^{\varepsilon}(e^{\varepsilon}\alpha+\delta)+\delta\big{)}\cdots+\delta\Big{)}+\delta\Bigg{)}+\delta$
$\displaystyle=e^{d\varepsilon}\alpha+\delta\frac{e^{d\varepsilon}-1}{e^{\varepsilon}-1}.$
(27)

We want to find the last index for which the iterations (27) hold. First, on
the one hand, $\tau$ satisfies

$\displaystyle U_{\texttt{DP}}^{\tau}(\alpha)$
$\displaystyle=e^{\tau\varepsilon}\alpha+\delta\frac{e^{\tau\varepsilon}-1}{e^{\varepsilon}-1}.$
(28)

On the other hand, by the definition of $\tau$, for $d=\tau+1$, the second
case in Lemma 3 will give the tightest upper bound on
$U_{\texttt{DP}}^{\tau+1}(\alpha)$. That is,

$\displaystyle\min(e^{\varepsilon}U_{\texttt{DP}}^{\tau}(\alpha)+\delta,\frac{U_{\texttt{DP}}^{\tau}(\alpha)-1+e^{\varepsilon}+\delta}{e^{\varepsilon}},1)$
$\displaystyle=\frac{U_{\texttt{DP}}^{\tau}(\alpha)-1+e^{\varepsilon_{\tau}}+\delta}{e^{\varepsilon}}.$

Therefore, from Lemma 3, we must have

$\displaystyle
U_{\texttt{DP}}^{\tau}(\alpha)\geq\frac{1-\delta}{e^{\varepsilon}+1}.$ (29)

Combining (29) and (28) gives the $\tau$ as defined in (6).

Now, note that the terms in the three conditions of Lemma 3 are all
monotonically non-decreasing. Also, the rate of increase with respect to
$\alpha$ for the conditions of Lemma 3 is respectively, $e^{\varepsilon}$,
$1/e^{\varepsilon}$ and $0$. Therefore, once the second case in Lemma 3
becomes the tightest, it will remain so. So is for the third case. In summary,
the cases in Lemma 3 do not “toggle” or “alternate” in providing the tightest
upper bound for $d>\tau$.

The last step is to provide a closed-form expression for the iterations
$\tau<d$, where the second case of Lemma 3 is active. Starting with
$d=\tau+1$, we will have

$\displaystyle U_{\texttt{DP}}^{\tau+1}(\alpha)$
$\displaystyle=\frac{U_{\texttt{DP}}^{\tau}(\alpha)-1+e^{\varepsilon}+\delta}{e^{\varepsilon}}$
$\displaystyle=\frac{\big{(}e^{\tau\varepsilon}\alpha+\delta\frac{e^{\tau\varepsilon}-1}{e^{\varepsilon}-1}\big{)}-1+e^{\varepsilon}+\delta}{e^{\varepsilon}}$
$\displaystyle=e^{(\tau-1)\varepsilon}\alpha+1-\frac{1}{e^{\varepsilon}}+\frac{\delta(e^{\tau\varepsilon}+e^{\varepsilon}-2)}{e^{\varepsilon}(e^{\varepsilon}-1)},$
(30)

which matches the second case in (5) for $d=\tau+1$. One can use (30) to
continue with $d>\tau+1$.

Part 2 (Showing that $\beta\geq L_{\texttt{DP}}^{d}(\alpha)$): From Lemma 7,
we have that $U_{\texttt{DP}}^{d}(1-\alpha)\leq 1-L_{\texttt{DP}}^{d}(\alpha)$
or $L_{\texttt{DP}}^{d}(\alpha)\leq 1-U_{\texttt{DP}}^{d}(1-\alpha)$. From
Lemma 9, we have that $\beta\leq U_{\texttt{DP}}^{d}(\alpha)$ implies
$\beta\geq 1-U_{\texttt{DP}}^{d}(1-\alpha)$. The result follows immediately.

###  III-F Proof of Theorem 1

By Proposition 2, $(L_{\texttt{DP}},U_{\texttt{DP}})$ is a suitable pair.
Thus, Algorithm 1 can be utilized to find the unique optimal
$(\epsilon,\delta)$-DP mechanism. Then, according to the proof of Proposition
1, the expression for $U_{\texttt{DP}}^{d}$ is equal to $p(d,\alpha)$ in
Definition 9.

##  IV On the Generality of Reasonable Utility

One of our main contributions is the notion of reasonable utility that we
present in Definition 2 for binary DP mechanisms. To the best of our
knowledge, when restricted to binary mechanisms, all utilities previously
suggested in the literature conform to this concept, including those in [13,
14, 15, 16, 17, 18, 19, 20]. Another general notion of utility for binary DP
mechanisms is the following.

######  Definition 14.

(Strong reasonable utility). Let $T$ be the true function and
$\mathfrak{M}_{\epsilon,\delta}$ the family of $(\epsilon,\delta)$-DP
mechanisms. Let $\mathcal{U}:\mathfrak{M}_{\epsilon,\delta}\to\mathbb{R}^{\geq
0}$ be a utility function that assigns non-negative real numbers to the
mechanisms in $\mathfrak{M}_{\epsilon,\delta}$. We say $\mathcal{U}$ is a
strong reasonable utility function if the following conditions hold.

  * 1)

If $\mathcal{M}_{1},\mathcal{M}_{2}\in\mathfrak{M}_{\epsilon,\delta}$ and for
all $v\in V$, $\Pr[\mathcal{M}_{1}(v)=T(v)]\geq\Pr[\mathcal{M}_{2}(v)=T(v)]$
then $\mathcal{U}(\mathcal{M}_{1})\geq\mathcal{U}(\mathcal{M}_{2})$.

  * 2)

If $\mathcal{M}_{1},\mathcal{M}_{2}\in\mathfrak{M}_{\epsilon,\delta}$ and for
all $v\in V$, $\Pr[\mathcal{M}_{1}(v)=T(v)]\geq\Pr[\mathcal{M}_{2}(v)=T(v)]$
and for at least one $x$, the inequality is strict, then
$\mathcal{U}(\mathcal{M}_{1})>\mathcal{U}(\mathcal{M}_{2})$.

Similar to the proof of Theorem 2, one can argue that for any partial
mechanism and any strong reasonable utility function $\mathcal{U}$, if an
$(\varepsilon,\delta)$ differentially private extension exists, then there
exists a unique optimal extension with respect to $\mathcal{U}$. This optimal
extension is independent of the actual utility function, and, moreover,
Algorithm 1 outputs this unique optimum extension mechanism.

##  V Extending to Non-Binary Mechanisms

It is not clear how to extend the notion of reasonable utility to non-binary
DP mechanisms. The difficulty arises because, in binary mechanisms (e.g.,
$Q=\\{\texttt{blue},\texttt{red}\\}$), optimizing the output probability for
the true value (e.g., blue) is straightforward and is equivalent to minimizing
its incorrect outcome (e.g., red). In contrast, with more options (e.g.,
$Q=\\{\texttt{blue},\texttt{red},\texttt{green}\\}$), it is clear that the
probability of the true outcome (blue) should be optimized, but the treatment
of other outcomes (red, green) lacks clarity without further assumptions. This
issue has been explored using a lexicographical ordering [23] and a dominance
ordering [24] based assumption. Optimal mechanisms for these cases have been
proposed for the special boundary homogeneous case.

## References

  * [1] R. G. L. D’Oliveira, M. Médard, and P. Sadeghi, “Differential privacy for binary functions via randomized graph colorings,” in _IEEE Int. Symp. Inf. Theory_ , Melbourne, Victoria, Australia, July 2021, pp. 473–478.
  * [2] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Proc. Theory Cryptography Conf._ , New York, NY, Mar. 2006, pp. 265–284.
  * [3] T. Zhu, G. Li, W. Zhou, and P. S. Yu, “Differentially private data publishing and analysis: A survey,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 29, no. 8, pp. 1619–1638, 2017.
  * [4] J. M. Abowd, “The us census bureau adopts differential privacy,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018, pp. 2867–2867.
  * [5] Ú. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in _Proceedings of the 2014 ACM SIGSAC conference on computer and communications security_ , 2014, pp. 1054–1067.
  * [6] B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” _arXiv preprint arXiv:1712.01524_ , 2017.
  * [7] D. P. Team, _Learning with Privacy at Scale_ , 2017 (last accessed May 2021). [Online]. Available: https://machinelearning.apple.com/2017/12/06/learning-with-privacy-at-scale.html
  * [8] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , 2016, pp. 308–318.
  * [9] C. Xu, J. Ren, D. Zhang, Y. Zhang, Z. Qin, and K. Ren, “Ganobfuscator: Mitigating information leakage under GAN via differential privacy,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 9, pp. 2358–2371, 2019.
  * [10] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1–2, pp. 1–210, 2021\.
  * [11] K. Wei, J. Li, M. Ding, C. Ma, H. H. Yang, F. Farokhi, S. Jin, T. Q. S. Quek, and H. V. Poor, “Federated learning with differential privacy: Algorithms and performance analysis,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, pp. 3454–3469, 2020.
  * [12] S. L. Garfinkel, J. M. Abowd, and S. Powazek, “Issues encountered deploying differential privacy,” in _Proceedings of the 2018 Workshop on Privacy in the Electronic Society_ , 2018, pp. 133–137.
  * [13] N. Fernandes, A. McIver, and C. Morgan, “The Laplace mechanism is optimal for differential privacy over continuous queries.” in _ACM/IEEE Symposium on Logic in Computer Science (LICS) (to appear)_ , 2021.
  * [14] A. Ghosh, T. Roughgarden, and M. Sundararajan, “Universally utility-maximizing privacy mechanisms,” _SIAM Journal on Computing_ , vol. 41, no. 6, pp. 1673–1693, 2012.
  * [15] Q. Geng, P. Kairouz, S. Oh, and P. Viswanath, “The staircase mechanism in differential privacy,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 9, no. 7, pp. 1176–1184, 2015.
  * [16] G. Quan and P. Viswanath, “The optimal noise-adding mechanism in differential privacy,” _IEEE T. Inform. Theory_ , vol. 62, no. 2, pp. 925–951, 2016.
  * [17] Q. Geng and P. Viswanath, “Optimal noise adding mechanisms for approximate differential privacy,” _IEEE Transactions on Information Theory_ , vol. 62, no. 2, pp. 952–969, 2015.
  * [18] N. Holohan, D. J. Leith, and O. Mason, “Optimal differentially private mechanisms for randomised response,” _IEEE Transactions on Information Forensics and Security_ , vol. 12, no. 11, pp. 2726–2735, 2017.
  * [19] P. Kairouz, S. Oh, and P. Viswanath, “Differentially private multi-party computation,” in _Annual Conference on Information Science and Systems (CISS)_ , 2016, pp. 128–132.
  * [20] K. Kalantari, L. Sankar, and A. D. Sarwate, “Robust privacy-utility tradeoffs under differential privacy and hamming distortion,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 11, pp. 2816–2830, 2018.
  * [21] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [22] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to algorithms_. MIT press, 2022.
  * [23] Z. Zhou, O. Günlü, R. G. L. D’Oliveira, M. Médard, P. Sadeghi, and R. F. Schaefer, “Rainbow differential privacy,” in _2022 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2022, pp. 614–619.
  * [24] Y. Gu, Z. Zhou, O. Günlü, R. G. L. D’Oliveira, P. Sadeghi, M. Médard, and R. F. Schaefer, “Generalized rainbow differential privacy,” _arXiv preprint arXiv:2309.05871_ , 2023.