
\section{Conclusion}\label{sec:conc}


We proposed a classification of DP variants and extensions using the concept of
dimensions. When possible, we compared definitions from the same dimension, and
we showed that definitions from the different dimensions can be combined to form
new, meaningful definitions. In theory, it means that even if there were only
three possible ways to change a dimension, this would result in $3^7=2187$
possible definitions: the $\approx200$ existing definitions shown in
Figure~\ref{fig:timeline} are only scratching the surface of the space of
possible notions. Using these dimensions, we unified and simplified the
different notions proposed in the literature. We highlighted their properties
such as composability and whether they satisfy the privacy axioms by either
collecting the existing results or creating new proofs, and whenever possible,
we showed their relative relations to one another. We hope that this work will
make the field of data privacy more organized and easier to navigate, especially
for new practitioners.

\section{Acknowledgments}

The authors would like to thank Alex Kulesza, Esfandiar Mohammadi, David Basin,
and the anonymous reviewers for their helpful comments. This work was partially
funded by Google, and done while Bal\'azs Pej\'o was at University of
Luxembourg.

\section{Quantification of privacy loss (Q)}\label{sec:q}

DP and its associated risk model is a \emph{worst-case} property: it quantifies
not only over all possible neighboring datasets but also over all possible
outputs. However, in a typical real-life risk assessment, events with
vanishingly small probability are ignored, or their risk is weighted according
to their probability. It is natural to consider analogous relaxations,
especially since these relaxations often have better composition properties, and
enable natural mechanisms like the Gaussian mechanism to be considered
private~\cite{dwork2014algorithmic}.

Most of the definitions within this section can be expressed using the
\emph{privacy loss random variable}\footnote{First defined
in~\cite{dinur2003revealing} as the \emph{adversary's confidence gain}.}, so we
first introduce this concept. Roughly speaking, it measures how much
information is revealed by the output of a mechanism.

\begin{definition}[Privacy loss random variable~\cite{dinur2003revealing}]
    Let $\mathcal{M}$ be a mechanism, and $D_1$ and $D_2$ two datasets. The
    \emph{privacy loss random variable between $\mech{D_1}$ and $\mech{D_2}$} is
    defined as:
    \begin{equation*}
        \privloss{D_1}{D_2}(O)=\ln\left(\frac{\proba{\mech{D_1}=O}}{\proba{\mech{D_2}=O}}\right)
    \end{equation*}
    if neither $\proba{\mech{D_1}=O}$ nor $\proba{\mech{D_2}=O}$ is 0; in case
    only $\proba{\mech{D_2}=O}$ is zero then
    $\privloss{D_1}{D_2}(O)=\infty$, otherwise
    $\privloss{D_1}{D_2}(O)=-\infty$.
\end{definition}

\vspace{-0.25cm}\subsection{Allowing a small probability of error}\label{subsec:small-error}

The first option, whose introduction is commonly attributed
to~\cite{dwork2006our}, relaxes the definition of $\varepsilon$-indistinguishability by
allowing an additional small density of probability on which the upper $\varepsilon$
bound does not hold. This small density $\delta$ can be used to
compensate for outputs for which the privacy loss is larger than $e^\varepsilon$. This
led to the definition of \emph{approximate DP}~\cite{dwork2006our}, also called
$\left(\eps,\del\right)$-DP\@. As of today, this is the most commonly used relaxation in the
literature.

The $\delta$ in $\left(\eps,\del\right)$-DP is sometimes explained as the probability that the
privacy loss of the output is larger than $e^\varepsilon$. However, this intuition
corresponds to a different definition, called \emph{probabilistic
DP}~\cite{machanavajjhala2008privacy,canard2015differential,meiser2018approximate}.
These two definitions can be combined to form \emph{relaxed
DP}~\cite{zhang2015toward}, requiring approximate DP with probability $<1$.

\vspace{-0.25cm}\subsection{Averaging the privacy loss}

As $\varepsilon$-DP corresponds to a \emph{worst-case} risk model, it is natural to
consider relaxations to allow for larger privacy loss for some outputs. It is
also natural to consider \emph{average-case} risk models: allowing larger
privacy loss values only if lower values compensate it in other cases.
One such relaxation is called \emph{Kullback-Leibler
privacy}~\cite{barber2014privacy,cuff2016differential}: it considers the
\emph{arithmetic} mean of the privacy loss random variable, which measures how
much information is revealed when the output of a private algorithm is observed.

\emph{R\'enyi DP}~\cite{mironov2017renyi} extends this idea by adding a
parameter $\alpha\ge1$ which allows controlling the choice of averaging function.

\begin{definition}[$(\alpha,\varepsilon)$-R\'enyi DP~\cite{mironov2017renyi}]
    Given $\alpha>1$, a privacy mechanism $\mathcal{M}$ is $(\alpha,\varepsilon)$-R\'enyi
    DP if for all pairs of neighboring datasets $D_1$ and $D_2$:
    \begin{equation*}
      \expects{O\sim\mech{D_1}}{e^{(\alpha-1)\privloss{D_1}{D_2}(O)}} \le e^{(\alpha-1)\varepsilon}
    \end{equation*}
\end{definition}

The property required by R\'enyi DP can be reformulated as
$D_\alpha\left(\mech{D_1}\|\mech{D_2}\right)\le\varepsilon$, where $D_\alpha$ is the
R\'enyi divergence. It is possible to use other divergence functions to obtain
other relaxations, such as \emph{binary-$|\chi|^{\alpha}$-} and
\emph{tenary-$|\chi|^{\alpha}$ DP}~\cite{wang2018subsampled}, \emph{total
variation privacy}~\cite{barber2014privacy} or \emph{quantum
DP}~\cite{colisson2016l3}.

Another possibility to average the privacy loss is to use \emph{mutual
information} to formalize the intuition that any individual record should not
``give out too much information'' on the output of the mechanism (or
vice-versa). This is captured by \emph{mutual-information
DP}~\cite{cuff2016differential}, which guarantees that the mutual information
between $\mech{D}$ and $D(i)$ conditioned on $D_{-i}$ is under a certain
threshold. The bound is taken over all possible priors on $D$, which avoids
having to reason about the attacker's background knowledge.

\vspace{-0.25cm}\subsection{Controlling the tail distribution of the privacy loss}

Some definitions go further than simply considering a worst-case bound on the
privacy loss, or averaging it across the distribution. They try to obtain the
benefits of $\left(\eps,\del\right)$-DP with a smaller $\varepsilon$ which holds in most cases, but
control the behavior of the bad cases better than $\left(\eps,\del\right)$-DP, which allows for
catastrophic privacy loss in rare cases.

The first attempt to formalize this idea was proposed
in~\cite{dwork2016concentrated}, where authors introduce \emph{mean concentrated DP}.
In this definition, a parameter controls the privacy loss variable globally, and
another parameter allows for some outputs to have a greater privacy loss; while
still requiring that the difference is smaller than a Gaussian distribution.
In~\cite{bun2016concentrated} the authors show that it does not verify the
post-processing axiom, and proposed
another formalization of this idea called \emph{zero-concentrated DP}, which
requires that the privacy loss random variable is concentrated around zero.

\begin{definition}[$(\xi,\rho)$-zero-concentrated DP~\cite{bun2016concentrated}]
    A mechanism $\mathcal{M}$ is $(\xi,\rho)$-zero-concentrated DP if for all pairs
    of neighboring datasets $D_1$ and $D_2$ and all $\alpha>1$:
    \begin{equation*}
    \mathbb{E}_{O\sim\mech{D_1}}\left[e^{(\alpha-1)\privloss{D_1}{D_2}(O)}\right]\le e^{(\alpha-1)(\xi+\rho\alpha)}
    \end{equation*}
\end{definition}

Four more variants of concentrated DP exist: \emph{approximate zero concentrated
DP}~\cite{bun2016concentrated}, \emph{Collinson-concentrated
DP}\footnote{Originally called truncated concentrated DP, we rename it here to
avoid a name collision.}~\cite{colisson2016l3}, \emph{bounded zero concentrated
DP}~\cite{bun2016concentrated} and \emph{truncated concentrated
DP}~\cite{bun2018composable}. The first takes the R\'enyi divergence on events
with high enough probability instead of on the full distributions, the second
requires all the R\'enyi divergences to be smaller than a threshold, while the
last two requires this only for some R\'enyi divergences. While we present the connections
between the most widely used relaxations in Table~4, we list the exact connection between
all these notions in the full version of this work.

\vspace{-0.25cm}\subsection{Extensions}

Most definitions of this section can be seen as bounding the divergence between
$\mech{D_1}$ and $\mech{D_2}$, for different possible divergence functions.
In~\cite{barber2014privacy}, the authors use this fact to generalize them and
define \emph{divergence DP}, which takes an $f$-divergence as a parameter.
Note that~\cite{duchi2018right} also defined divergence DP, using a special set
of $f$-divergences. A similar idea was explored in~\cite{chaudhuri2019dcapacity}
as \emph{capacity bounded DP} which uses ``restricted divergences''.

Finally, approximate DP, probabilistic DP and R\'enyi DP can be extended to use
a \emph{family} of parameters rather than a single pair. As shown
in~\cite{sommer2018privacy} (Theorem~2), finding the tightest possible family of
parameters (for either definition) for a given mechanism is equivalent to
specifying the behavior of its privacy loss random variable entirely.

\vspace{-0.25cm}\subsection{Multidimensional definitions}

Allowing a small probability of error $\delta$ by using the same concept as in
$\left(\eps,\del\right)$-DP is very common; a lot of new DP definitions were proposed in the
literature with such a parameter. Unless it creates a particularly notable
effect, we do not mention it explicitly and present the definitions without this
parameter.

Definitions in this section can be used as standalone concepts:
$\left(\eps,\del\right)$-DP is omnipresent in the literature, and the principle of averaging
risk is natural enough for R\'enyi privacy to be used in practical settings,
like posterior sampling~\cite{geumlek2017renyi} or resistance to adversarial
inputs in machine learning~\cite{pinot2019unified}. Most variants in this
section, however, are only used as technical tools to get better results on
composition or privacy
amplification~\cite{dwork2014algorithmic,wang2018subsampled,feldman2018privacy,lee2018concentrated}.


\section*{Appendix}
\section{Proofs for the axioms}\label{app:ax}

Many variants in \textbf{Q} satisfy both axioms, as shown by the following
generic result.

\begin{prop}\label{prop:a-div}
	All instantiations of Div DP satisfy both privacy axioms.
	\begin{proof}
		The post-processing axiom follows directly from the monotonicity property of
		the $f$-divergence. The convexity axiom follows directly from the joint
		convexity property of the $f$-divergence.
	\end{proof}
\end{prop}

As a direct corollary, approximate DP, MI Pr, KL Pr,
R\'enyi Pr, and zCo DP satisfy both axioms.

\begin{prop}[Th.~1\&2 in~\cite{meiser2018approximate}, App.~A in~\cite{bun2016concentrated}]\label{prop:a-p-prob}
	Pro DP and mCo DP do not satisfy the post-processing axiom.

\end{prop}

\begin{prop}\label{prop:a-c-prob}
	Pro DP do not satisfy the convexity axiom.
	\begin{proof}
		Consider the following mechanisms $\mathcal{M}_1$ and $\mathcal{M}_2$, with input and
		output in $\{0,1\}$.
		\begin{itemize}
			\item $\mechone{0}=0$, $\mechone{1}=1$ with probability $\delta$, and
			$\mechone{1}=0$ with probability $1-\delta$.
			\item $\mechtwo{0}=\mechtwo{1}=1$.
		\end{itemize}
		Both mechanisms are $\left(\frac{1}{1-\delta},\delta\right)$-Pro DP\@. Now,
		consider the mechanism $\mathcal{M}$ which applies $\mathcal{M}_1$ with probability
		$1-2\delta$ and $\mathcal{M}_2$ with probability $2\delta$. $\mathcal{M}$ is a convex
		combination of $\mathcal{M}_1$ and $\mathcal{M}_2$, but the reader can verify that it
		is not $\left(\frac{1}{1-\delta},\delta\right)$-Pro DP\@. 
	
	
	
	\end{proof}
\end{prop}

To show that definitions in \textbf{N}, \textbf{B} and \textbf{R} satisfy
privacy axioms, we use a few generic results.

\begin{prop}[Th.~5.1 in~\cite{kifer2012rigorous}]\label{prop:a-puff}
  All instantiations of PF Pr satisfy both privacy axioms. As
  an immediate corollary, all definitions which combine notions in \textbf{N}
  and N Pr also satisfy both axioms.
\end{prop}

\begin{prop}[Sec. 2.1~\cite{kifer2010towards}]\label{prop:a-gen}
  All instantiations of Gl DP satisfy both privacy axioms.
\end{prop}

\begin{prop}[Th.~3\&4 in~\cite{bassily2013coupled}]\label{prop:a-cw}
  All instantiations of CW Pr satisfy both privacy axioms. As
  an immediate corollary, Dist DP and ZK Pr also satisfy both axioms.
\end{prop}

\begin{prop}[Prop.~5 in~\cite{desfontaines2019differential}]\label{prop:a-pk}
  PPK-DP and APK-DP satisfy both privacy axioms.
\end{prop}

We can extend this result to definitions in \textbf{V} which simply vary the
privacy parameters across inputs.

\begin{prop}\label{prop:a-d}
  $d_\mathcal{D}$-Pr satisfies both privacy axioms. Further, EDiv DP also satisfies both privacy axioms.
  \begin{proof}
    The proof of Proposition~\ref{prop:a-puff} (Appendix~B
    in~\cite{kifer2012rigorous}) is a proof by case analysis on every possible
    protected property. The fact that $\varepsilon$ is the same for every protected
    property has no influence on the proof, so we can directly adapt the proof
    to $d_\mathcal{D}$-Pr, and its combination with PF Pr.
    Similarly, the proof can be extended to arbitrary divergence functions, like
    in Proposition~\ref{prop:a-div}.
  \end{proof}
\end{prop}

However, for the definitions in \textbf{V} which only consider a random subset
of dataset pairs, the post-processing axiom is satisfied but not the convexity
axiom.

\begin{prop}[Lemma~2.4 in~\cite{bassily2016typicality}]\label{prop:a-p-rand}
  Ran DP satisfies the post-processing axiom.
\end{prop}

\begin{prop}\label{prop:a-c-rand}
  Ran DP does not satisfy the convexity axiom.
  \begin{proof}
    Let $\pi$ be the uniform distribution on $\{0,1\}$, let $D_1$ be generated
    by picking $10$ records according to $\pi$, and $D_2$ by flipping one record
    at random. Let $\mathcal{M}_0$ return $0$ if all records are $0$, and $\bot$
    otherwise. Let $\mathcal{M}_1$ return $1$ if all records are $1$, and $\bot$
    otherwise. Both mechanisms are $(\pi,2^{-9},0)$-Ran DP\@: with
    probability $>2\cdot2^{-10}$, neither $D_1$ nor $D_2$ have all their records
    set to $0$ or $1$, so the mechanism returns $\bot$, which does not leak
    anything. However, the mechanism $\mathcal{M}$ obtained by
    applying either $\mathcal{M}_1$ or $\mathcal{M}_2$ uniformly randomly does not satisfy
    $(\pi,2^{-9},0)$-Ran DP\@: the $\varepsilon$-indistinguishability property does not hold
    if $D_1$ or $D_2$ have all their records set to \emph{either} $0$ or $1$,
    which happens twice as often as either option alone.
  \end{proof}
\end{prop}

The definitions in~\textbf{F} which change the shape of the 
prior-posterior bounds also satisfy both axioms.

\begin{prop}\label{prop:a-def}
  All variants of M Pr, Adv Pr, and AN Pr satisfy both axioms. 
 
  \begin{proof}
    We prove it for PM Pr. A mechanism $\mathcal{M}$
    satisfies $\left(\Theta,\eps\right)$-PM Pr if for all $t\in\mathcal{T}$,
    $\theta\in\Theta$, and $S\subseteq\mathcal{O}$,
    $\probasc{D\sim\theta}{t\in D}{\mech{D}\in S}\le e^\varepsilon\cdot\probas{D\sim\theta}{t\in D}$.
    We first prove that it satisfies the convexity axiom. Suppose $\mathcal{M}$ is a
    convex combination of $\mathcal{M}_1$ and $\mathcal{M}_2$. 
   
    Simplifying $\probas{D\sim\theta}{\dots}$ into $\proba{\dots}$, we have the following 
    where $X_i=\proba{\mech{D}\in S\text{ and }\mathcal{M}=\mathcal{M}_i}$ for $i\in\{1,2\}$:
    \begin{align*}
      & \probac{t\in D}{\mech{D}\in S} \\
      & \; = \frac{\proba{t\in D\text{ and }\mech{D}\in S\text{ and }\mathcal{M}=\mathcal{M}_1}}{\proba{\mech{D}\in S}} \\
        & \qquad + \frac{\proba{t\in D\text{ and }\mech{D}\in S\text{ and }\mathcal{M}=\mathcal{M}_2}}{\proba{\mech{D}\in S}} =\\
      & \; \frac{X_1\cdot\probac{t\in D}{\mechone{D}\in S}}{X_1+X_2} +\frac{X_2\cdot\probac{t\in D}{\mechtwo{D}\in S}}{X_1+X_2} \\
      & \; \le \frac{X_1\left(e^\varepsilon\cdot\proba{t\in D}\right)}{X_1+X_2}
               + \frac{X_2\left(e^\varepsilon\cdot\proba{t\in D}\right)}{X_1+X_2} \le e^\varepsilon\cdot\proba{t\in D}
    \end{align*}
    The proof for the post-processing axiom is similar, summing over all
    possible outputs $\mech{D}$. It is straightforward to adapt the proof to
    all other definitions which change the shape of the prior-posterior bounds.
  \end{proof}
\end{prop}

Finally, CDP also satisfies both axioms.

\begin{prop}\label{prop:a-comp}
  Both versions of CDP satisfy both privacy axioms; where the post-processing
  axiom is modified to only allow post-processing with functions computable on a
  probabilistic polynomial time Turing machine. As a direct corollary of
  Proposition~\ref{prop:a-cw}, CZK Pr also satisfies both privacy axioms.
  \begin{proof}
    For Ind-CDP and the post-processing axiom, the proof is straightforward: if
    post-processing the output could break the $\varepsilon$-indistinguishability
    property, the attacker could do this on the original output and break the
    $\varepsilon$-indistinguishability property of the original definition.
    
    For Ind-CDP and the convexity axiom, without loss of generality, we can
    assume that the sets of possible outputs of both mechanisms are disjoint
    (otherwise, this give strictly less information to the attacker). The proof
    is then the same as for the post-processing axiom.
    
    For Sim-CDP applying the same post-processing function to the ``true''
    differentially private mechanism immediately leads to the result, since DP
    satisfies post-processing. The same reasoning holds for convexity.
  \end{proof}
\end{prop}

\section{Proofs for composition}\label{app:comp}

In this section, if $\mathcal{M}_1$ and $\mathcal{M}_2$ are two mechanisms, we denote
$\mathcal{M}_{1+2}$ the mechanism defined by
$\mathcal{M}_{1+2}(D)=\left(\mathcal{M}_1(D),\mathcal{M}_2(D)\right)$.

Almost all definitions in \textbf{Q} are composable; the only one for which we
could not find any result in the literature is $(f,\varepsilon)$-Div DP\@.

\begin{prop}\label{prop:c-q}
If $\mathcal{M}_1$ and $\mathcal{M}_2$ are respectively\ldots
  \begin{enumerate}
    \item $\left(\varepsilon_1,\delta_1\right)$-DP and $\left(\varepsilon_2,\delta_2\right)$-DP 
      then $\mathcal{M}_{1+2}$ is $\left(\varepsilon_1+\varepsilon_2,\delta_1+\delta_2\right)$-DP\@.
    \item $\left(\varepsilon_1,\delta_1\right)$-Pro DP and $\left(\varepsilon_2,\delta_2\right)$-Pro DP 
      then $\mathcal{M}_{1+2}$ is $\left(\varepsilon_1+\varepsilon_2,\delta_1+\delta_2\right)$-Pro DP\@.
    \item $\varepsilon_1$-MI DP and $\varepsilon_2$-MI DP then $\mathcal{M}_{1+2}$ is
      $\left(\varepsilon_1+\varepsilon_2\right)$-MI DP\@.
    \item $\varepsilon_1$-KL DP and $\varepsilon_2$-KL DP then $\mathcal{M}_{1+2}$ is
      $\left(\varepsilon_1+\varepsilon_2\right)$-KL DP\@.
    \item $\left(\alpha_1,\varepsilon_1\right)$-R\'enyi DP and 
    $\left(\alpha_2,\varepsilon_2\right)$-R\'enyi DP 
      then $\mathcal{M}_{1+2}$ is
      $\left(\max\left(\alpha_1,\alpha_2\right),\varepsilon_1+\varepsilon_2\right)$-R\'enyi
      DP\@.
    \item $\left(\mu_1,\tau_1\right)$-mCo DP and
      $\left(\mu_2,\tau_2\right)$-mCo DP then $\mathcal{M}_{1+2}$ is
      $\left(\mu_1+\mu_2,\sqrt{{\mu_1}^2+{\mu_2}^2}\right)$-mCo DP\@.
    \item $\left(\xi_1,\rho_1\right)$-zCo DP and
      $\left(\xi_2,\rho_2\right)$-zCo DP then $\mathcal{M}_{1+2}$ is
      $\left(\xi_1+\xi_2,\xi_1+\xi_2\right)$-zCo DP\@.
  \end{enumerate}
\end{prop}


Further, all definitions that are combinations of definitions 
in \textbf{N} and \textbf{V} are composable.

\begin{prop}\label{prop:c-d}
  If $\mathcal{M}_1$ is $d^1_\mathcal{D}$-Pr and $\mathcal{M}_2$ is
  $d^2_\mathcal{D}$-Pr, then $\mathcal{M}_{1+2}$ is $d^{1+2}_\mathcal{D}$-Pr,
  where
  $d^{1+2}_\mathcal{D}\left(D_1,D_2\right)=d^1_\mathcal{D}\left(D_1,D_2\right)+d^2_\mathcal{D}\left(D_1,D_2\right)$.
  \begin{proof}
    The proof is essentially the same as for $\varepsilon$-DP\@. $\mathcal{M}_1$'s
    randomness is independent from $\mathcal{M}_2$'s, so:
    \begin{align*}
      & \proba{\mechone{D_1}=O_1~\text{and}~\mechtwo{D_1}=O_2} \\
        & \; = \proba{\mechone{D_1}=O_1}\cdot\proba{\mechtwo{D_1}=O_2} \\
        & \; \le e^{d^1_\mathcal{D}\left(D_1,D_2\right)}\cdot\proba{\mechtwo{D_2}=O_1} \\
          & \qquad \cdot e^{d^2_\mathcal{D}\left(D_1,D_2\right)}\cdot\proba{\mechtwo{D_2}=O_2} \\
        & \; \le e^{d^{1+2}_\mathcal{D}\left(D_1,D_2\right)}
                    \cdot\proba{\mechone{D_2}=O_1~\text{and}~\mechtwo{D_2}=O_2}.
    \end{align*}
    Each definition listed in Proposition~\ref{prop:c-q} can also be combined
    with $d_\mathcal{D}$-Pr, and the composition proofs can be similarly
    adapted.
  \end{proof}
\end{prop}

\begin{prop}[Th.~4 in~\cite{dimitrakakis2013bayesian}]\label{prop:c-pm}
    If $\mathcal{M}_1$ is $(d_\mathcal{D},\varepsilon_1,\delta_1)$-PsM DP and $\mathcal{M}_2$ 
    is $(d_\mathcal{D},\varepsilon_2,\delta_2)$-PsM DP then $\mathcal{M}_{1+2}$ is 
    $(d_\mathcal{D},\varepsilon_1+\varepsilon_2,\delta_1+\delta_2)$-PsM DP\@.
\end{prop}

\begin{prop}[Prop.~5.1.2 in~\cite{hall2012new}]\label{prop:c-rand}
  If $\mathcal{M}_1$ satisfies $(\pi,\gamma_1,\varepsilon_1)$-Ran DP and $\mathcal{M}_2$
  satisfies $(\pi,\gamma_2,\varepsilon_2)$-Ran DP then $\mathcal{M}_{1+2}$ satisfies
  $(\pi,\gamma_1+\gamma_2,\varepsilon_1+\varepsilon_2)$-Ran DP\@.
\end{prop}

This can be also extended to variants in \textbf{Q}, see for example Lemma~2.5
in~\cite{bassily2016typicality}.

\begin{prop}\label{prop:c-b}
  In general, definitions which assume limited background knowledge from the
  adversary do not compose.
  \begin{proof}
    The proof of Proposition~\ref{prop:c-d} cannot be adapted to a context in
    which the attacker has limited background knowledge: as the randomness
    partially comes from the data-generating distribution, the two probabilities
    are no longer independent. A typical example considers two mechanisms which
    answer e.g., queries ``how many records satisfy property $P$'' and ``how many
    records satisfy property $P$ and have an ID different from 4217'': the
    randomness in the data might make each query private, but the combination of
    two queries trivially reveals something about a particular user. Variants of
    this proof can easily be obtained for all definitions with limited
    background knowledge.
  \end{proof}
\end{prop}


\section{Change in formalism (F)}\label{sec:f}

$\varepsilon$-indistinguishability compares the
distribution of outputs given two neighboring inputs. This is not the only way
to encompass the idea that a Bayesian attacker should not be able to gain too
much information on the dataset. One such a formalism reformulates DP in terms of hypothesis 
testing~\cite{wasserman2010statistical,kairouz2017composition} by limiting the type I and the 
type II error of the hypothesis that the output $O$ of a mechanism originates from $D_1$ 
(instead of $D_2$). This interpretation was also used in~\cite{dong2019gaussian} 
in \emph{$f$-DP} (a reformulation of generic DP) and in 
\emph{Gaussian DP} (a specific instance of $f$-DP), which can capture both 
$\left(\eps,\del\right)$-DP and R\'enyi DP.

Other formalisms model the attacker \emph{explicitly}, by formalizing their prior
belief as a probability distribution over all possible datasets. This 
can be done in two distinct ways. Some variants
consider a specific prior (or family of possible priors) of the attacker,
implicitly assuming a limited background knowledge, like in Section~\ref{sec:b}.
We show that these variants can be interpreted as changing the prior-posterior
bounds of the attacker. Another possibility compares two posteriors, quantifying
over all possible priors. In practice, these definitions are mostly useful in
that comparing them to DP leads to a better understanding of the guarantees that
DP provides.

\vspace{-0.25cm}\subsection{Changing the shape of the prior-posterior bounds}\label{subsec:shape}

DP can be interpreted as giving a bound on the posterior of a Bayesian attacker
as a function of their prior. This is exactly the case in \emph{indistinguishable 
privacy}, an equivalent reformulation of DP defined in~\cite{liu2013semantic}: 
suppose that the attacker is trying to
distinguish between two options $D=D_1$ and $D=D_2$, where $D_1$
corresponds to the option ``$t\in D$'' and $D_2$ to ``$t\notin D$''. Initially,
they associate a certain prior probability $\proba{t\in D}$ to the first option.
When they observe the output of the algorithm, this becomes the posterior
probability $\proba{t\in D|\mech{D}=O}$. From Definition~\ref{def:DP}, we
have:

\begin{align*}
    \frac{\proba{t\in D|\mech{D}=O}}{\proba{t\notin D|\mech{D}=O}} \le e^\varepsilon\cdot\frac{\proba{t\in D}}{\proba{t\notin D}}\Rightarrow\\
    \proba{t\in D|\mech{D}=O} \le \frac{e^\varepsilon\cdot\proba{t\in D}}{1+\left(e^\varepsilon-1\right)\proba{t\in D}}
\end{align*}

A similar, symmetric lower bound can be obtained. Hence, DP can
be interpreted as bounding the posterior level of certainty of a Bayesian
attacker as a function of its prior. We visualize these bounds in the top left side
of Figure~\ref{fig:bounds}.

\begin{figure}[h!]
    \centering
    \includegraphics[width=4cm]{pics/dp-bounds}
    \includegraphics[width=4cm]{pics/pmp-bounds}
    \includegraphics[width=4cm]{pics/advp-bounds}
    \includegraphics[width=4cm]{pics/apnp-bounds}
    \caption{From top left to bottom right, using $\varepsilon=\ln{3}$: posterior-prior
    bounds in the original DP, positive membership privacy, adversarial privacy
    (with $\delta=0.05$) and aposteriori noiseless privacy.}\label{fig:bounds}
\end{figure}

Some variants of DP use this idea in their formalism, rather than obtaining the posterior 
bound as a corollary to the classical DP definition. For example, \emph{positive
membership privacy}~\cite{li2013membership} requires that the posterior does not
increase too much compared to the prior. Like noiseless
privacy~\cite{bhaskar2011noiseless}, it assumes an attacker with limited
background knowledge.

\begin{definition}[$\left(\Theta,\eps\right)$-positive membership privacy~\cite{li2013membership}]
  A privacy mechanism $\mathcal{M}$ provides $(\Theta,\varepsilon)$-positive membership
  privacy if for any distribution $\theta\in\Theta$, any record $t\in\mathcal{D}$
  and any $S\subseteq\mathcal{O}$:
  \begin{align*}
    \probas{D\sim\theta}{t\in D|\mech{D}\in S} & \leq e^\varepsilon\probas{D\sim\theta}{t\in D}\text{ and}\\
    \probas{D\sim\theta}{t\notin D|\mech{D}\in S} & \geq e^{-\varepsilon}\probas{D\sim\theta}{t\notin D}
  \end{align*}
\end{definition}

Note that this definition is \emph{asymmetric}: the posterior is bounded from
above, but not from below. It is visualized the top right part of 
Figure~\ref{fig:bounds}. In
the same paper, the authors also define \emph{negative membership
privacy}, which provides the symmetric lower bound, and
\emph{membership privacy}, which is the conjunction of the two. 
Additionally, the same idea is captured in \emph{$\varepsilon$-DP location 
    obfuscation}~\cite{dong2018limitations} in the context of location privacy.

A previous attempt at formalizing the same idea was presented
in~\cite{rastogi2009relationship} as \emph{adversarial privacy}. This definition
is similar to positive membership privacy, except only the first relation is
used, and there is a small additive $\delta$ as in approximate DP\@. We visualize
the corresponding bounds on the bottom left of Figure~\ref{fig:bounds}. Moreover, 
in~\cite{bhaskar2011noiseless} \emph{aposteriori noiseless privacy} is introduced with the 
corresponding bounds seen in the bottom right side of Figure~\ref{fig:bounds}.

Further relaxations from~\cite{rastogi2009relationship} are \emph{tuple indistinguishability}, \emph{relaxed indistinguishability} and 
\emph{bounded adversarial privacy}. Finally, the idea behind distribution privacy is 
reformulated in Bayesian terms in~\cite{jelasity2014distributional}.

\vspace{-0.25cm}\subsection{Comparing two posteriors}

In~\cite{kasiviswanathan2014semantics}, the authors propose an approach that
captures an intuitive idea proposed by Dwork in~\cite{dwork2006differential}:
``any conclusions drawn from the output of a private algorithm must be
similar whether or not an individual's data is present in the input or not''.
They define \emph{semantic privacy}: instead of comparing the posterior with the
prior belief like in DP, this bounds the difference between two posterior belief
distributions, depending on which database was secretly chosen. The distance
chosen to represent the idea that those two posterior belief distributions are
close is the statistical distance. One important difference between the definitions
in the previous subsection is that semantic privacy quantifies over all
possible priors: like in DP, the attacker is assumed to have arbitrary
background knowledge.

\begin{definition}[$\varepsilon$-semantic
    privacy~\cite{ganta2008composition,kasiviswanathan2014semantics}]
    A mechanism $\mathcal{M}$ is $\varepsilon$-semantically private if for any distribution over
    datasets $\theta$, any index $i$, any $S\subseteq\mathcal{O}$, and any set of
    datasets $X\subseteq\mathcal{D}$:
    \begin{align*}
   
   
    \left|\probac{D\in X}{\mech{D}\in S}-\probac{D\in X}{\mech{D_{-i}}\in S}\right|\le\varepsilon
    \end{align*}
    where $D$ is chosen randomly from $\theta$.
\end{definition}

Other definitions comparing posteriors directly are \emph{posteriori
DP}~\cite{wang2014tradeoff} (although the prior is not made explicit),
\emph{inferential privacy}~\cite{ghosh2016inferential} (a reformulation of
noiseless privacy), and \emph{range-bounded privacy}~\cite{durfee2019practical}
(a technical definition, equivalent to DP up to a change in parameters). 

\vspace{-0.25cm}\subsection{Multidimensional definitions}\label{sec:f-multi}

Definitions that limit the background knowledge of the adversary explicitly
formulate it as a probability distribution. As such, they are natural candidates
for Bayesian reformulations. In~\cite{wu2017extending}, the authors introduce
\emph{identity DP}, which is an equivalent Bayesian reformulation of noiseless
privacy. 

Another example is \emph{inference-based distributional
DP}~\cite{bassily2013coupled}, which relates to distributional DP the same way
as noiseless privacy and its aposteriori version: they are equivalent, however,
when a small additive error is introduced to the definitions, the inference and
aposteriori based versions become weaker~\cite{bassily2013coupled}.

Further, it is possible to modify the neighborhood definition.
In~\cite{du2012privacy}, the authors introduce \emph{information privacy}, which can
be seen as a posteriori noiseless privacy combined with free lunch privacy:
rather than considering the knowledge gain of the adversary on one particular
user, it considers its knowledge gain about any possible value of the database.

Definitions in this section mostly appear in theoretical
research papers, to provide a deeper understanding of guarantees offered by DP
and its alternatives. They do not seem to be used in practical applications.

\section{Computational power (C)}\label{sec:c}

The $\varepsilon$-indistinguishability property in DP is \emph{information-theoretic}:
the attacker is implicitly assumed to have infinite computing power. This is
unrealistic in practice, so it is natural to consider definitions where the
attacker only has polynomial computing power. Changing this assumption leads to
weaker data privacy definitions. In~\cite{mironov2009computational}, two
approaches have been proposed to formalize this idea.

The first approach is to model the distinguisher explicitly as a polynomial
Turing machine: this is \emph{indistinguishability-based computational DP}.

\begin{definition}[$\varepsilon_\kappa$-IndCDP~\cite{mironov2009computational}]
    A family ${\left(\mathcal{M}_{\kappa}\right)}_{\kappa\in\mathbb{N}}$ of privacy mechanisms
    $\mathcal{M}_{\kappa}$ provides $\varepsilon_{\kappa}$-IndCDP if there exists a
    negligible function $\textsf{neg}$ such that for all non-uniform probabilistic
    polynomial-time Turing machines $\Omega$ (the distinguisher), all
    polynomials $p(\cdot)$, all sufficiently large $\kappa\in\mathbb{N}$, and
    all datasets $D_1,D_2\in\mathcal{D}$ of size at most $p(\kappa)$ that differ
    only one one record:
    \begin{equation*}
    \proba{\Omega(\mech{D_1})=1}\leq e^{\varepsilon_{\kappa}}\cdot\proba{\Omega(\mech{D_2})=1}+\textsf{neg}(\kappa)
    \end{equation*}
    where $\textsf{neg}$ is a function that converges to zero asymptotically faster
    than the reciprocal of any polynomial.
\end{definition}

One instantiation of this is \emph{output-constrained DP}, presented
in~\cite{he2017composing}: the definition is adapted to a two-party computation
setting, where each party has their own set of privacy parameters.

The second approach is to require that the mechanism ``looks like'' a truly
differentially private mechanism, at least to a computationally bounded
distinguisher. In~\cite{mironov2009computational}, the authors introduce SimCDP,
short for \emph{simulation-based computational DP}.

\begin{definition}[$\varepsilon_{\kappa}$-SimCDP~\cite{mironov2009computational}]
    A family ${\left(\mathcal{M}_{\kappa}\right)}_{\kappa\in\mathbb{N}}$ of privacy
    mechanisms $\mathcal{M}_{\kappa}$ provides $\varepsilon_{\kappa}$-SimCDP if there exists
    a family ${\left(\mathcal{M}'_{\kappa}\right)}_{\kappa\in\mathbb{N}}$ of
    $\varepsilon_{\kappa}$-DP and a negligible function $\textsf{neg}$ such that for all
    non-uniform probabilistic polynomial-time Turing machines $\Omega$, all
    polynomials $p(\cdot)$, all sufficiently large $\kappa\in\mathbb{N}$, and
    all datasets $D\in\mathcal{D}$ of size at most $p(\kappa)$:
    \begin{equation*}
        \proba{\Omega(\mech{D})=1}-\proba{\Omega(\mathcal{M}'(D))=1}\leq \textsf{neg}(\kappa)
    \end{equation*}
    where $\textsf{neg}$ is a function that converges to zero asymptotically faster
    than the reciprocal of any polynomial.
\end{definition}

In~\cite{mironov2009computational}, the authors show that $\varepsilon_{\kappa}$-SimCDP
implies $\varepsilon_{\kappa}$-IndCDP\@.


\vspace{-0.25cm}\subsection{Multidimensional Definitions}

Some DP variants which explicitly model an adversary with a simulator can
relatively easily be adapted to model a computationally bounded adversary,
simply by imposing that the simulator must be polynomial. This is done
explicitly in~\cite{gehrke2011towards}, where the authors define
\emph{computational zero-knowledge privacy}, which could also be adapted to
e.g., the two coupled-worlds privacy definitions.

Modeling a computationally bounded adversary is orthogonal to changing the type
of input data, as well as considering an adversary with limited background
knowledge: in~\cite{backes2014differential}, the authors define \emph{differential
indistinguishability}, which prevents a polynomial adversary from distinguishing
between two Turing machines with random input.

Limiting the computational power of the attacker is a
reasonable assumption, but for a large class of queries, it cannot provide
significant benefits over classical DP in the typical client-server
setting~\cite{groce2011limits}. Thus, existing work using it focuses on
multi-party settings~\cite{bater2018shrinkwrap}.

\section{Background knowledge (B)}\label{sec:b}

In DP, the attacker is implicitly assumed to have full knowledge of the dataset:
their only uncertainty is whether the target belongs in the dataset or not. This
implicit assumption is also present for the definitions of the previous
dimensions: indeed, the attacker has to distinguish between two \emph{fixed}
datasets $D_1$ and $D_2$. The only source of randomness in
$\varepsilon$-indistinguishability comes from the mechanism itself. In many cases, this
assumption is unrealistic, and it is natural to consider weaker adversaries, who
do not have full background knowledge. One of the main motivations to do so is
to use significantly less noise in the mechanism~\cite{duan2009privacy}.

The typical way to represent this uncertainty formally is to assume that the
input data comes from a certain probability distribution (named ``data evolution
scenario'' in~\cite{kifer2012rigorous}): the randomness of this distribution
models the attacker's uncertainty. Using a probability distribution to generate
the input data means that the $\varepsilon$-indistinguishability property cannot be
expressed between two fixed datasets. Instead, one natural way to express it is
to condition this distribution on some sensitive property such as in
\emph{noiseless
privacy}~\cite{duan2009privacy,bhaskar2011noiseless}\footnote{Not
to be confused with the definition with the same name introduced
in~\cite{farokhi2019noiseless}, mentioned in Section~\ref{sec:out}.}

\begin{definition}[$\left(\Theta,\eps\right)$-noiseless privacy~\cite{duan2009privacy,bhaskar2011noiseless}]
    Given a family $\Theta$ of probability distribution on $\mathcal{D}$, a mechanism
    $\mathcal{M}$ is $\left(\Theta,\eps\right)$-noiseless private if for all $\theta\in\Theta$, all $i$ and
    all $t,t'\in\mathcal{T}$:
    \begin{equation*}
    \mech{D}_{|D\sim\theta,D(i)=t}\approx_\varepsilon\mech{D}_{|D\sim\theta,D(i)=t'}
    \end{equation*}
\end{definition}

This definition follows naturally from considering the associative view of DP
with the strong adversary assumption, and attempting to relax this assumption.
The exact way to model the adversary's uncertainty can be changed; for example
\emph{DP under sampling}~\cite{li2011provably}, an instance of noiseless
privacy, models it using random sampling.

In~\cite{bassily2013coupled} however, the authors argue that in the presence of
correlations in the data, noiseless privacy can be too strong.
Indeed, if one record can have an arbitrarily large influence
on the rest of the data, conditioning on the value of this record can lead to
very distinguishable outputs even if the mechanism only depends on global
properties of the data. To fix this problem, they propose \emph{distributional
DP}, an alternative definition that only considers the influence of one user
once the database has already been randomly picked from the data-generating
distribution. In this definition, one record is changed \emph{after} the dataset
has been generated, an approach closer to the causal interpretation of DP\@.

\vspace{-0.25cm}\subsection{Multidimensional definitions}

Modifying the risk model while limiting the attacker's background knowledge has
interesting consequences. In~\cite{desfontaines2019differential}, the authors
show that two options are possible: either consider the background knowledge as
additional information given to the attacker or let the attacker
\emph{influence} the background knowledge. This distinction between an
\emph{active} and a \emph{passive} attacker does not matter if only the
worst-case scenario is considered, like in noiseless privacy. However, under
different risk models, such as allowing a small probability of error, they lead
to two different definitions.

The first, \emph{active partial knowledge DP}, quantifies over all possible
values of the background knowledge. It was introduced
in~\cite{bhaskar2011noiseless,bassily2013coupled} and reformulated
in~\cite{desfontaines2019differential} to clarify that it implicitly assumes an
active attacker.

The second definition, \emph{passive partial knowledge
DP}~\cite{desfontaines2019differential}, is strictly weaker: it models a passive
attacker, who cannot choose their background knowledge, and thus cannot
influence the data. In this context, $\delta$ does not only apply to the output of
the mechanism, but also to the value of the background knowledge.

Modifying the neighborhood definition is simpler: it is clearly orthogonal to
the dimensions introduced in this section. In both noiseless privacy and
distributional DP, the two possibilities between which the adversary must
distinguish are similar to bounded DP\@. This can easily be changed to choose
other properties to protect from the attacker. This is done in \emph{pufferfish
privacy}~\cite{kifer2012rigorous}, which extends the concept of neighboring
datasets to neighboring \emph{distributions} of datasets.

\begin{definition}[$(\Theta,\Phi,\varepsilon)$-pufferfish privacy~\cite{kifer2012rigorous}]
    Given a family of probability distributions $\Theta$ on $\mathcal{D}$, and a
    family of pairs of predicates $\Phi$ on datasets, a mechanism $\mathcal{M}$ verifies
    $(\Theta,\Phi,\varepsilon)$-pufferfish privacy if for all distributions
    $\theta\in\Theta$ and all pairs of predicates
    $\left(\phi_1,\phi_2\right)\in\Phi$:
    \begin{equation*}
    \mech{D}_{|D\sim\theta,\phi_1(D)}\approx_\varepsilon\mech{D}_{|D\sim\theta,\phi_2(D)}
    \end{equation*}
\end{definition}

Pufferfish privacy starts with a set of data-generating distributions, then
conditions them on sensitive attributes. This notion extends noiseless privacy,
as well as other definitions like \emph{bayesian DP}~\cite{leung2012bayesian},
in which neighboring records only have a fraction of elements in common, and
some are generated randomly.

The same idea can be formalized by comparing pairs of distributions directly.
This is done in~\cite{kawamoto2019esorics} via \emph{distribution privacy},
instantiated in~\cite{geumlek2019profile} via \emph{profile-based DP}, in
which the attacker tries to distinguish between different probabilistic user
profiles. 

Further relaxations encompassing the introduced dimensions are
\emph{probabilistic distribution privacy}\footnote{Appears in
the extended \href{https://arxiv.org/abs/1812.00939}{ArXiv version} of~\cite{kawamoto2019esorics}.}
(combination of distribution privacy and probabilistic DP), \emph{extended
distribution privacy}~\cite{kawamoto2019esorics} (combination of distribution
privacy and $d_\mathcal{D}$-privacy), \emph{divergence distribution
privacy}~\cite{kawamoto2019allerton} (combination of distribution privacy and
divergence DP), \emph{extended divergence distribution
privacy}~\cite{kawamoto2019allerton} (combination of the latter two options),
and \emph{divergence distribution privacy with auxiliary
inputs}~\cite{kawamoto2019allerton} which considers the setting where the
attacker uses full or approximate knowledge rather than perfect knowledge on the
input probability distributions (as in profile-based privacy).

Definitions of this section are an active area of research; a
typical question is to quantify in which conditions deterministic mechanisms can
provide some level privacy. However, they are not used a lot in practice, likely
because of their fragility: if the assumptions about the attacker's limited
background knowledge are wrong in practice, then the definitions do not provide
any guarantee of protection.

\section{Differential Privacy}\label{sec:pre}

In this section, we recall the original definition of DP and we introduce our
seven dimensions. We also enlist desirable properties of data privacy
definitions, and define how two definitions can relate to each other.
Table~\ref{tab:notions} summarizes the notations used throughout the paper.

\vspace{-0.25cm}\scriptsize
\begin{table}[h!]
    \centering
    \begin{tabular}{ll}
        Notation & Description \\
        \midrule
        $\mathcal{T}$ & Set of possible records\\
        $t\in\mathcal{T}$ & A possible record\\
        $\mathcal{D}=\mathcal{T}^*$ & Set of possible datasets (sequences of records)\\
        $D\in\mathcal{D}$ & Dataset (we also use $D', D_1$, $D_2$, \ldots) \\
        $D(i)$ & $i$-th record of the dataset ($i\le|D|$) \\
        $D_{-i}$ & Dataset $D$, with its $i$-th record removed\\
        \midrule
        $\mathcal{M}$ & Privacy mechanism (probabilistic) \\
        $\mech{D}$ & The distribution (or an instance of this distribution) \\
        & of the outputs of $\mathcal{M}$ given input $D$ \\
        \midrule
        $\mathcal{O}$ & Set of possible outputs of the mechanism \\
        $S\subseteq\mathcal{O}$ & Subset of possible outputs \\
        $O\in\mathcal{O}$ & Output of the privacy mechanism \\
        \midrule
        $\pi$ & Probability distribution on $\mathcal{T}$ \\
        $\Theta$ & Family of probability distributions on $\mathcal{D}$ \\
        $\theta\in\Theta$ & Probability distribution on $\mathcal{D}$ \\
    \end{tabular}
    \caption{Notations used through the paper.}\label{tab:notions}
\end{table}
\vspace{-0.5cm}\normalsize

The first DP mechanism was proposed in 1965~\cite{warner1965randomized}, and
data privacy definitions that are a property of a mechanism and not of the
output dataset were proposed as early as 2003~\cite{evfimievski2003limiting}.
However, DP and the related notion of
\emph{$\varepsilon$-indistinguishability}\footnote{This notion originates from the
cryptographic notion of indistinguishability~\cite{goldwasser1984probabilistic}.
A similar notion, \emph{$(1,\varepsilon)$-privacy}, is defined
in~\cite{chaudhuri2006random}, where $(1+\varepsilon)$ used in place of $e^{\varepsilon}$.}
were first formally defined in
2006~\cite{dwork2006differential,dwork2006calibrating,dppatent}.

\begin{definition}[$\varepsilon$-indistinguishability~\cite{dwork2006calibrating}]
    Two random variables $A$ and $B$ are $\varepsilon$-indistinguishable,
    denoted $A\approx_\varepsilon B$, if for all measurable sets $X$ of possible events,
    $\proba{A\in X} \le e^{\varepsilon}\cdot\proba{B\in X}$ and
    $\proba{B\in X} \le e^{\varepsilon}\cdot\proba{A\in X}$.
\end{definition}

Informally, $A$ and $B$ are $\varepsilon$-indistinguishable if their distributions are
``close''. This notion is used to define DP\@.

\begin{table*}[b!]
    \centering
    \resizebox{17cm}{!}{
        \begin{tabular}{lll}
            \toprule
            Dimension & Description & Usual Motivations \\
            \midrule
            \midrule
            \textbf{Q}uantification of Privacy Loss
            & How is the privacy loss quantified across outputs?
            & Averaging risk, having  better composition properties \\
            \midrule
            \textbf{N}eighborhood Definition
            & Which properties are protected from the attacker?
            & Protecting specific values or multiple individuals\\
            \midrule
            \textbf{V}ariation of Privacy Loss
            & Can the privacy loss vary across inputs?
            & Modeling users with different privacy requirements \\
            \midrule
            \textbf{B}ackground Knowledge
            & How much prior knowledge does the attacker have?
            & Using less noise in the mechanism \\
            \midrule
            \textbf{F}ormalism change
            & How to formalize the attacker's knowledge gain?
            & Exploring other intuitive notions of privacy \\
            \midrule
            \textbf{R}elativization of Knowledge Gain
            & What is the knowledge gain relative to?
            & Guaranteeing privacy for correlated data \\
            \midrule
            \textbf{C}omputational Power
            & How much computational power can the attacker use?
            & Combining cryptography techniques with DP \\
            \bottomrule
    \end{tabular}}
    \caption{The seven dimensions and their usual motivation.}\label{tab:dimensions_list}
\end{table*}

\begin{definition}[$\varepsilon$-differential privacy~\cite{dwork2006differential}]\label{def:DP}
    A privacy mechanism $\mathcal{M}$ is $\varepsilon$-differential private (or $\varepsilon$-DP) if for all
    datasets $D_1$ and $D_2$ that differ only in one record,
    $\mech{D_1}\approx_\varepsilon\mech{D_2}$.
\end{definition}

\vspace{-0.25cm}\subsection{Dimensions}

Variants and extensions of DP modify the original definition in various ways. To
establish a comprehensive taxonomy, a natural approach is to partition them into
\emph{categories}, depending on which aspect of the definition they change.
Unfortunately, this approach fails for privacy definitions: many of them modify
several aspects at once, so it is impossible to have a categorization such that
every definition falls neatly into only one category.

The approach we take is to define \emph{dimensions} along which the original
definition can be modified. Each variant or extension of DP can be seen as a
point in a multidimensional space, where each coordinate corresponds to one
possible way of changing the definition along a particular dimension. To make
this representation possible, our dimensions need to satisfy two properties:

\begin{itemize}
    \item \textbf{Mutual compatibility}: definitions that vary along different
    dimensions can be combined to form a new, meaningful definition.
    \item \textbf{Inner exclusivity}: definitions in the same dimension cannot
    be combined to form a new, meaningful definition (but they can be pairwise
    comparable).
\end{itemize}

In addition, each dimension should be \emph{motivatable}: there should be an
intuitive explanation of what it means to modify DP along each dimension.
Moreover, each possible choice within a dimension should be similarly
understandable, to allow new practitioners to determine quickly which kind of
definition they should use or study, depending on their use case.

We introduce our dimensions by reformulating the guarantee offered by
DP, highlighting aspects that have been modified by its
variants or extensions. Each dimension is attributed a letter, and we note the
dimension letter corresponding to each highlight. This formulation considers the
point of view of an attacker, trying to find out some sensitive information
about some input data using the output of a mechanism.

\begin{center}
    An attacker with \textbf{perfect background knowledge} (\textbf{B}) and \textbf{unbounded computation power} (\textbf{C}) is \textbf{unable} (\textbf{R}) to \textbf{distinguish} (\textbf{F}) \textbf{anything about an individual} (\textbf{N}), \textbf{uniformly across users} (\textbf{V})  even in the \textbf{worst-case scenario} (\textbf{Q}).
\end{center}

This informal definition of DP with the seven highlighted aspects give us seven
distinct dimensions. We denote each one by a letter and summarize them in
Table~\ref{tab:dimensions_list}; each is introduced in its corresponding
section.

Note that the interpretation of DP is subject to some debate.
In~\cite{tschantz2017differential}, the authors summarize this debate, and
show that DP can be interpreted under two possible lenses: it can be seen as an
\emph{associative} property, or as a \emph{causal} property. The difference
between the two interpretations is particularly clear when one supposes that the
input dataset is modeled as being generated by a probability distribution.

\begin{itemize}
\item In the associative view, this probability distribution is
  \emph{conditioned} upon the value of one record. If the distribution has
  correlations, this change can affect other records as well.
\item In the causal view, the dataset is first generated, and the value of 
	one record is then \emph{changed} before computing the result of the mechanism.
\end{itemize}

While the causal view does not require any additional 
assumption to capture the intuition behind DP, the associative view
requires that either all records are independent in
the original probability distribution (the \emph{independence assumption}),
or the adversary must know all data points except one (the \emph{strong
adversary assumption}, which we picked in the reformulation above).

These considerations can have a significant impact on DP
variants and extensions, either leading to distinct variants that attempt to
capture the same intuition, or to the same variant being interpreted in
different ways.

\vspace{-0.25cm}\subsection{Properties}\label{sec:sum}

Two important properties of data privacy notions are called \emph{privacy
axioms}. They were proposed in~\cite{kifer2010towards,kifer2012axiomatic}. These
are not ``axioms'' in a sense that they are assumed to be true, but rather, they
are consistency checks: properties that, if not satisfied by a data privacy
definition, indicate a flaw in the definition.

\begin{definition}[Privacy axioms~\cite{kifer2010towards,kifer2012axiomatic}]\hspace{0cm}\\
    \begin{enumerate}
      \item \textbf{Post-processing}\footnote{This definition must be slightly
        adapted for some variants, see for example
        Proposition~\ref{prop:a-comp} in Appendix~\ref{app:ax}.} (or \emph{transformation invariance}): A
        privacy definition $\mathrm{Def}$ satisfies the post-processing axiom if, for
        any mechanism $\mathcal{M}$ satisfying $\mathrm{Def}$ and any probabilistic function
        $f$, the mechanism $D\rightarrow f(\mech{D})$ also satisfies $\mathrm{Def}$.
      \item \textbf{Convexity} (or \emph{privacy axiom of choice}): A privacy
        definition $\mathrm{Def}$ satisfies the convexity axiom if, for any two
        mechanisms $\mathcal{M}_1$ and $\mathcal{M}_2$ satisfying $\mathrm{Def}$, the mechanism
        $\mathcal{M}$ defined by $\mech{D}=\mathcal{M}_1(D)$ with fixed probability $p$
        and $\mech{D}=\mathcal{M}_2(D)$ with probability $1-p$ also satisfies $\mathrm{Def}$.
    \end{enumerate}
\end{definition}

A third important property is \emph{composability}. It guarantees that the
output of two mechanisms satisfying a privacy definition still satisfies the
definition, typically with a change in parameters. There are several types of
composition: \emph{parallel composition} (the mechanisms are applied to disjoint
subsets of a larger dataset), \emph{sequential composition} (the mechanisms are
applied on the entire dataset), and \emph{adaptive composition} (each mechanism
can access dataset and the output of the previous mechanisms). In this work, we
only consider sequential composition.

\begin{definition}[Composability]
    A privacy definition $\mathrm{Def}$ with parameter $\alpha$ is \emph{composable} if
    for any two mechanisms $\mathcal{M}_1$ and $\mathcal{M}_2$ satisfying respectively
    $\alpha_1$-$\mathrm{Def}$ and $\alpha_2$-$\mathrm{Def}$, the mechanism
    $\mech{D}=\left(\mathcal{M}_1(D),\mathcal{M}_2(D)\right)$ satisfies $\alpha$-$\mathrm{Def}$
    for some (non-trivial) $\alpha$.
\end{definition}

\vspace{-0.25cm}\subsection{Relations}

When learning about a new data privacy notion, it is often useful to know what are
the known relations between this notion and other definitions. However,
definitions have parameters that often have different meanings, and whose value
is not directly comparable. To claim that a definition is stronger than another,
we utilize the concept of ordering established in~\cite{cuff2016differential} using
$\alpha$ and $\beta$ as tuples, encoding multiple parameters.

\begin{definition}[Relative strength]
    Let $\alpha\text{-}\Def_1$ and $\beta\text{-}\Def_2$ be privacy
    definitions. We say that $\Def_1$ is \emph{stronger than} $\Def_2$, and
    denote it $\Def_1\ensuremath{\succ}\Def_2$, if:
    \begin{enumerate}
      \item for all $\alpha$, there is a $\beta$ such that
        $\alpha\text{-}\Def_1\implies\beta\text{-}\Def_2$;
        \item for all $\beta$, there is an $\alpha$ such that
        $\alpha\text{-}\Def_1\implies\beta\text{-}\Def_2$.
    \end{enumerate}
    If $\Def_1\ensuremath{\succ}\Def_2$ and $\Def_2\ensuremath{\succ}\Def_1$, we say
    that the two definitions are \emph{equivalent}, and denote it
    $\Def_1\sim\Def_2$.
\end{definition}

Relative strength implies a partial ordering on the space of possible definitions.
It is useful to classify variants but does not capture extensions well.
Thus, we introduce a second notion to represent when a definition can be seen as
a special case of another.

\begin{definition}[Extensions]
    Let $\Def_1$ and $\Def_2$ be privacy definitions with respective
    parameters $\alpha$ and $\beta$. We say that $\Def_1$ is \emph{extended by}
    $\Def_2$, and denote is as $\Def_1\ensuremath{\subset}\Def_2$, if for all
    $\alpha$, there is a $\beta$ such that $\alpha$-$\Def_1$ is identical (i.e., provides the same privacy guarantee) to $\beta$-$\Def_2$.
\end{definition}

Note that the original definition of relative strength only required the second
condition to hold; which would classify any extension as a stronger variant.

Both relations are reflexive and transitive; and we define the
symmetric counterpart of these relations as well (i.e., $\ensuremath{\prec}$ and
$\ensuremath{\supset}$). Moreover, for brevity, we combine these two concepts in a single
notation: if $\Def_1\ensuremath{\subset}\Def_2$ and $\Def_1\ensuremath{\succ}\Def_2$, we
say that $\Def_2$ is a weaker extension of $\Def_1$, and denote it
$\Def_1\ensuremath{\subset^\succ}\Def_2$.

In the following sections, we detail the different ways in which researchers
changed the original DP definition. Due to space constrains, only a handful of
definitions are formally defined while the majority of the definitions are
presented with greater detail in the full version of this work. A summarizing
table is presented at the end of this work, where for each definition, we also
highlight its dimensions and its relation to other notions. In Table~4 we also
specify whether these notions satisfy the privacy axioms and the composability
property (\ensuremath{\checkmark}: yes, \ensuremath{\text{\ding{55}}}: no, ?: currently unknown); in Appendix~\ref{app:ax}
and~\ref{app:comp} we either provide a reference or a novel proof for each of
these claims.

\section{Scope and related work}\label{sec:related}

In this section, we list related works and existing surveys in the field of data
privacy, we detail our criteria for excluding particular data privacy
definition from our work, and we list some relevant definitions that were excluded
by this criteria.

\vspace{-0.25cm}\subsection{Methodology}\label{sec:scope}

Whether a data privacy definition fits our description is not always obvious, so we use
the following criterion: the attacker's capabilities must be clearly defined, and the
definition must prevent this attacker from learning about a protected property.
Consequently, we do not consider definitions which are a property of the output
data and not of the mechanism, variants of technical notions that are not data
privacy properties (like different types of sensitivity), nor definitions whose
only difference with DP is in the context and not in the formal property (like
the distinction between local and global models).

To find a comprehensive list of DP notions, besides the definitions we were
aware of or suggested by experts, we conducted a wide literature review using
two research datasets: BASE\footnote{\url{https://www.base-search.net/}} and
Google Scholar\footnote{\url{https://scholar.google.com/}}. The exact queries
were run twice: first on October 31th, 2018, and second on August 1st, 2019. The
corresponding result counts are summarized in Table~\ref{tab:queries}; the
number in parentheses corresponds to the first run.

\vspace{-0.25cm}\scriptsize
\begin{table}[h!]
    \centering
    \begin{tabular}{cc}
        \toprule
        Query (BASE) & Hits \\
        \midrule
        ``differential privacy'' relax year:[2000 to *] & 115 (99) \\
        ``differential privacy'' variant -relax year:[2000 to *] & 110 (87) \\
        \midrule
        \midrule
        Query (Google Scholar) & Hits \\
        \midrule
        ``differential privacy'' ``new notion'' & 206 (162) \\
        ``differential privacy'' ``new definition'' -``new notion'' & 171 (129) \\
        \bottomrule
    \end{tabular}
    \caption{Queries for the literature review.}\label{tab:queries}
\end{table}
\vspace{-0.5cm}\normalsize

First, we manually reviewed each abstract and filter out papers until we had
only papers which either contained a new definition or were applying DP in a new
setting. All papers which defined a variant or extension of DP are cited in this
work.

\vspace{-0.25cm}\subsection{Out of scope definitions}\label{sec:out}

Besides syntactic DP definitions, some definitions 1) do not
provide a clear privacy guarantee or 2) are only used as a
tool in order to prove links between existing definitions. As such, we did not
include them in our survey (more details can be found in the
full version of this work).

Examples for the former include
\emph{$\varepsilon$-privacy}~\cite{machanavajjhala2009data} (the first attempt at
formalizing an adversary with restricted background knowledge, whose formulation
did not have the same interpretation as noiseless privacy), \emph{differential
identifiability}~\cite{lee2012differential} (bounds the probability that a given
individual's information is included in the input datasets, \emph{noiseless
privacy}~\cite{farokhi2019noiseless} but does not measure
the \emph{change} in probabilities between the two alternatives),
\emph{crowd-blending privacy}~\cite{gehrke2012crowd} (combines DP with
$k$-anonymity), and \emph{$(k,\varepsilon)$-anonymity}~\cite{holohan2017k}
(performs $k$-anonymisation on a subset of the quasi identifiers and then
$\varepsilon$-DP on the remaining quasi-identifiers with different settings for each
equivalence class).

Examples for the latter include further DP relaxations were created by changing 
the \emph{sensitivity} of the function what 
the mechanism protects. There are many variants to the initial concept of global
sensitivity~\cite{dwork2006calibrating}:
local sensitivity~\cite{nissim2007smooth},
smooth sensitivity~\cite{nissim2007smooth},
restricted sensitivity~\cite{blocki2013differentially},
empirical sensitivity~\cite{chen2013recursive},
recommendation-aware sensitivity~\cite{zhu2013differential},
record and correlated sensitivity~\cite{zhu2015correlated},
dependence sensitivity~\cite{liu2016dependence},
per-instance sensitivity~\cite{wang2017per},
individual sensitivity~\cite{cummings2018individual},
elastic sensitivity~\cite{johnson2018towards} and
derivative sensitivity~\cite{laud2018achieving}.
We did not consider these notions as these do not modify the actual definition
of DP\@.

\vspace{-0.25cm}\subsection{Local model}\label{sec:local}

In this work we focused on DP variants/extensions typically used in the
\emph{global model}, in which a central entity has access to the whole dataset.
It is also possible to use DP in other contexts, without formally changing the
definition. The main alternative is the \emph{local model},
where each individual randomizes their own data before sending it to an
aggregator. This model is used e.g.\ by Google~\cite{erlingsson2014rappor},
Apple~\cite{apple2017dp}, or Microsoft~\cite{ding2017collecting}. Another option
is the \emph{shuffled model}~\cite{bittau2017prochlo}, which falls in-between
the local and global models.

Some definitions we listed actually were presented in the
local model, such as 
$d_\mathcal{D}$-privacy~\cite{chatzikokolakis2013broadening}, 
geo-indistinguishability~\cite{andres2013geo},
earth mover's Pr~\cite{fernandes2018generalized}, 
location Pr~\cite{elsalamouny2016differential}, 
profile-based DP~\cite{geumlek2019profile}, 
divergence DP and smooth DP from~\cite{barber2014privacy},
utility-optimized DP~\cite{kawamoto2019allerton},  
and extended DP, distribution Pr, and extended distribution Pr from~\cite{kawamoto2019esorics}. 
Besides these, a handful of other local DP definitions are mentioned below; a longer
discussion can be found in the full version of this work (soon to be uploaded to ArXiv\footnote{\url{https://arxiv.org/abs/1906.01337}}). 

The idea behind \emph{local DP}~\cite{duchi2013local} was proposed
in~\cite{shi2011privacy} as \emph{distributed DP}, where authors additionally
assume that only a portion of participants is honest. \emph{Joint
DP}~\cite{kearns2014mechanism} models a game in which each player cannot learn
the data from other players. In \emph{multiparty DP}~\cite{wu2016inherit}, the
view of each subgroup of players is differentially private with respect to other
players. Some variants introduced in this work were also considered in the local
setting; examples include \emph{localized information
privacy}~\cite{jiang2018context}, \emph{one-sided local
DP}~\cite{murakami2018restricted}, \emph{personalized local
DP}~\cite{nie2018utility}, and \emph{$d_{\mathcal{D}}$-local
DP}~\cite{alvim2018metric,gursoy2019secure} (called \emph{condensed local
DP} in~\cite{gursoy2019secure}).

\vspace{-0.25cm}\subsection{Related work}

The relation between the main syntactic models of anonymity and DP was studied
in~\cite{clifton2013syntactic}, in which the authors claim that the former is
designed for privacy-preserving data publishing (PPDP), while DP is more
suitable for privacy preserving data mining (PPDM). 

In~\cite{wang2016relation},
authors establish connections between differential privacy (seen as the
additional disclosure of an individual's information due to the release of the
data), \emph{identifiability} (seen as the posteriors of recovering the original
data from the released data), and \emph{mutual-information privacy} (which
measures the average amount of information about the original dataset contained
in the released data).

Some of the earliest surveys focusing on DP were written by
Dwork~\cite{dwork2008differential,dwork2009differential}, and summarize
algorithms achieving DP and applications. The more detailed ``privacy
book''~\cite{dwork2014algorithmic} presents an in-depth discussion about the
fundamentals of DP, techniques for achieving it, and applications to
query-release mechanisms, distributed computations or data streams. Another
recent survey focuses on the release of histograms and synthetic data with
DP~\cite{nelson2019chasing}.

In~\cite{heurix2015taxonomy}, the authors classify different enhancing
technologies (PETs) into 7 complementary dimensions. Indistinguishability falls
into the \emph{Aim} dimension, but within this category, only $k$-anonymity and
oblivious transfer are considered. In~\cite{aghasian2018user}, the authors
survey privacy concerns, measurements and techniques used in online social
networks and recommender systems. They classify privacy into 5 categories; DP
falls into \emph{Privacy-preserving models}. In~\cite{wagner2018technical}, the
authors classify 80+ privacy metrics into 8 categories based on the output of
the privacy mechanism. One of their classes is \emph{Indistinguishability},
which contains DP as well as several variants. Some variants are classified into
other categories; e.g., R\'enyi DP is classified into \emph{Uncertainty} and
mutual-information DP into \emph{Information gain/loss}. The authors list 8 DP
definitions; our taxonomy can be seen as an extension of the contents of their
work (and in particular of the \emph{Indistinguishability} category).

Finally, some surveys focus on location privacy.
In~\cite{machanavajjhala2018analyzing}, authors highlight privacy concerns in
this context and list mechanisms with formal provable privacy guarantees, while
in~\cite{chatzikokolakis2017methods}, authors analyze different kinds of privacy
breaches and compare metrics that have been proposed to protect location data.

\section{Relativization of the knowledge gain (R)}\label{sec:r}

When using the associative interpretation with the independence assumption, it
is unclear how to adapt DP to correlated datasets like social networks: data
about someone's friends might reveal sensitive information about this person.
The causal interpretation of DP does not suffer from this problem, but how to
adapt the associative view to such correlated contexts? Changing the definition
of the neighborhood is one possibility (see Section~\ref{sec:n-changing}), but
it requires knowing in advance the exact impact of someone on other records. A
more robust option is to impose that the information released does not contain
more information than the result of some predefined algorithms on the data,
without the individual in question. The method for formalizing this intuition
borrows ideas from \emph{zero-knowledge proofs}~\cite{goldwasser1989knowledge}.

In a data privacy context, instead of imposing that the result of the mechanism is
roughly \emph{the same} on neighboring datasets $D_1$ and $D_2$, it is possible
to impose that the result of the mechanism on $D_1$ can be \emph{simulated}
using only some information about $D_2$. The corresponding definition, called
\emph{zero-knowledge privacy} and introduced in~\cite{gehrke2011towards},
captures the idea that the mechanism does not leak more information on a given
target than a certain class of aggregate metrics (called \emph{model of
aggregate information}).

\begin{definition}[$\left(\Agg,\eps\right)$-zero-knowledge privacy~\cite{gehrke2011towards}]
    Let $\textsf{Agg}$ be a family of (possibly randomized) algorithms $\textsf{agg}$. A privacy
    mechanism $\mathcal{M}$ is $\left(\Agg,\eps\right)$-zero-knowledge private if there exists an
    algorithm $\textsf{agg}\in\textsf{Agg}$ and a simulator $\textsf{Sim}$ such as for all pairs of
    neighboring datasets $D_1$ and $D_2$,
    $\mech{D_1}\approx_\varepsilon\textsf{Sim}\left(\textsf{agg}(D_2)\right)$.
\end{definition}

\vspace{-0.25cm}\subsection{Multidimensional definitions}

Using a simulator allows making statements of the type ``this mechanism does
not leak more information on a given target than a certain class of aggregate
metrics''. Similarly to pufferfish privacy, we can vary the neighborhood
definitions (to protect other types of information than the presence and
characteristics of individuals), and explicitly limit the attacker's background
knowledge using a probability distribution. This is done in~\cite{bassily2013coupled} 
as \emph{coupled-worlds privacy}, a generalization of distributional privacy, 
where a family of functions $\textsf{priv}$ represents the protected attribute.

\begin{definition}[$(\Theta,\Gamma,\varepsilon)$-coupled-worlds privacy~\cite{bassily2013coupled}]
    Let $\Gamma$ be a family of pairs of functions $(\textsf{agg},\textsf{priv})$. A mechanism
    $\mathcal{M}$ satisfies $(\Theta,\Gamma,\varepsilon)$-coupled-worlds privacy if there is a
    simulator $\textsf{Sim}$ such that for all distributions $\theta\in\Theta$, all
    $(\textsf{agg},\textsf{priv})\in\Gamma$, and all possible values $p$:
    \begin{equation*}
      \mech{D}_{|D\sim\theta,\textsf{priv}(D)=p}\approx_{\varepsilon}\textsf{Sim}{\left(\textsf{agg}(D)\right)}_{|D\sim\theta,\textsf{priv}(D)=p}
    \end{equation*}
\end{definition}

This definition is a good example of combining different dimensions: it changes
several aspects of the original definition according to \textbf{N}, \textbf{B}
and \textbf{R}. Moreover, \textbf{Q} and \textbf{F} can easily be integrated
with this definition by using $\left(\eps,\del\right)$-indistinguishability with a Bayesian
reformulation. This is done explicitly in \emph{inference-based coupled-worlds
privacy}~\cite{bassily2013coupled}.

We did not find any evidence that these variants and extensions
are used in practice.

\section{Variation of privacy loss (V)}\label{sec:v}

In DP, the privacy parameter $\varepsilon$ is \emph{uniform}: the level of protection
is the same for all protected users or attributes, or equivalently, only the
level of risk for the most at-risk user is considered. In practice, some users
might require a higher level of protection than others or a data custodian might
want to consider the level of risk across all users, rather than only
considering the worst case. Some definitions take this into account by allowing
the privacy loss to vary across inputs, either explicitly (by associating each
user to an acceptable level of risk), or implicitly (by allowing some users to
be at risk, or averaging the risk across users).

\vspace{-0.25cm}\subsection{Varying the privacy level across inputs}\label{subsec:varying}

In Section~\ref{sec:n}, we show how changing the definition of the neighborhood
allows us to adapt the definition of DP to protect different aspects of the
input data. However, the privacy protection in those variants is binary: either
a given property is protected, or it is not. A possible option to generalize
this idea further is to allow the privacy level to vary across inputs.

One natural example is to consider that some users might have higher privacy
requirements than others, and make the $\varepsilon$ vary according to which user
differs between the two datasets. This is done
in~\cite{niknami2014spatialpdp,jorgensen2015conservative,ebadi2015differential,ghosh2015selling,liu2015fast}
via \emph{personalized DP}, also defined in~\cite{alaggan2015heterogeneous} as
\emph{heterogeneous DP} and in~\cite{deldar2018pldp} as \emph{personalized
location DP}.

\begin{definition}[$\Psi$-personalized DP~\cite{jorgensen2015conservative}]
    A privacy mechanism $\mathcal{M}$ provides $\Psi$-personalized DP if for every
    pair of neighboring datasets $\left(D,D_{-i}\right)$ and for all sets of
    outputs $S\subseteq\mathcal{O}$:
    \begin{equation*}
    \proba{\mech{D_{-i}}\in S}\leq e^{\Psi\left(D(i)\right)}\proba{\mech{D}\in S}
    \end{equation*}
    where $\Psi$ is a privacy specification:
    $\Psi:\mathcal{T}\rightarrow\mathbb{R}^+$ maps the records to personal privacy
    preferences and $\Psi\left(D(i)\right)$ denotes the privacy preference of
    the $i$-th record.
\end{definition}

This definition can be seen as a refinement of the intuition behind one-sided
DP, which separated records into sensitive and non-sensitive ones.
In~\cite{lui2015outlier}, the authors define \emph{tailored DP}, which generalizes
this further: the privacy level depends on the entire database, not only in the
differing record.

This concept can be applied to strengthen or weaken the privacy requirement for
a record depending on whether they are an outlier in the database.
In~\cite{lui2015outlier}, the authors formalize this idea and introduce
\emph{outlier privacy}, which tailors an individual's protection level to their
``outlierness''. Other refinements (instances of tailored DP) include \emph{simple 
outlier privacy}, \emph{simple outlier DP}, and \emph{staircase outlier privacy}. 

Finally, varying the privacy level across inputs also makes sense in
\emph{continuous} scenarios, where the neighborhood relationship between two
datasets is not binary, but quantified, like
\emph{$\varepsilon$-geo-indistinguishability}~\cite{andres2013geo}.

\vspace{-0.25cm}\subsection{Randomizing the variation of privacy levels}\label{subsec:scope}

Varying the privacy level across inputs can also be done in a randomized way, by
guaranteeing that some random fraction of users have a certain privacy level.
One example is proposed in~\cite{hall2011random} as \emph{random DP}: the
authors note that rather than requiring DP to hold for any possible datasets, it
is natural to only consider \emph{realistic datasets}, and allow ``edge-case''
datasets to not be protected. This is captured by generating the data randomly,
and allowing a small proportion $\gamma$ of cases not to satisfy the
$\varepsilon$-indistinguishability property.

\begin{definition}[$(\pi,\gamma,\varepsilon)$-random DP~\cite{hall2011random}]
    Let $\pi$ be a probability distribution on $\mathcal{T}$, $D_1$ a dataset
    generated by drawing $n$ i.i.d.\ elements in $\pi$, and $D_2$ the same
    dataset as $D_1$, except one element was changed to a new element drawn
    from $\pi$. A mechanism $\mathcal{M}$ is $(\pi,\gamma,\varepsilon)$-random DP if
    $\mech{D_1}\approx_\varepsilon\mech{D_2}$, with probability at least $1-\gamma$
    \emph{on the choice of $D_1$ and $D_2$}.
\end{definition}

This definition was also introduced as \emph{predictive DP}
in~\cite{hall2012new} and as \emph{model-specific DP}
in~\cite{mcclure2015relaxations}, with slightly different ways of defining the
randomness which models this notion of ``realistic'' datasets.

This relaxation looks similar to probabilistic DP, but is
actually different: both have a small probability that the risk is
unbounded, but while random DP this probability is computed across inputs of the mechanism 
(i.e., users or datasets), for probabilistic DP it is computed across mechanism outputs. 
Also similarly to probabilistic DP, excluding some cases altogether creates
definitional issues: random DP does not satisfy the convexity axiom (see
Proposition~\ref{prop:a-c-rand} in Appendix~\ref{app:ax}). We postulate that
using a different mechanism to allow some inputs to not satisfy the mechanism,
similar to R\'enyi DP, could solve this problem.

Usually, data-generating distributions are used for other purposes: they
typically model an adversary with partial knowledge. However, definitions in
this section still compare the outputs of the mechanisms given fixed neighboring
datasets: the only randomness in the indistinguishability property comes from
the mechanism. By contrast, definitions of Section~\ref{sec:b} compare the
output of the mechanism on a random dataset, so the randomness comes both from
the data-generating distribution and the mechanism.

\vspace{-0.25cm}\subsection{Multidimensional definitions}

The definitions described in Section~\ref{sec:n} (e.g., generic DP or blowfish
privacy), have the same privacy constraint for all neighboring datasets. Thus,
they cannot capture definitions that vary the privacy level across inputs.
\emph{$d_\mathcal{D}$-privacy} is introduced
in~\cite{chatzikokolakis2013broadening} to capture both ideas of varying the
neighborhood definition and varying the privacy levels across inputs: the
function $d_\mathcal{D}$ takes both databases as input, so it can both capture
arbitrary neighborhood definitions and return different values depending on the
difference between the two.

\begin{definition}[$d_{\mathcal{D}}$-privacy~\cite{chatzikokolakis2013broadening}]
    Let $d_{\mathcal{D}}:\mathcal{D}^2\rightarrow\mathbb{R}_\infty$. A
    privacy mechanism $\mathcal{M}$ satisfies $d_{\mathcal{D}}$-privacy if for all
    pairs of datasets $D_1$, $D_2$ and all sets of outputs $S\subseteq\mathcal{O}$:
    \begin{equation*}
    \proba{\mech{D_1}\in S} \leq
    e^{d_{\mathcal{D}}\left(D_1,D_2\right)} \cdot\proba{\mech{D_2}\in S}
    \end{equation*}
\end{definition}

Equivalent definitions appeared in~\cite{elsalamouny2016differential} as
\emph{$l$-privacy}, and in~\cite{kawamoto2019esorics} as \emph{extended DP}.
Several other definitions, such as \emph{weighted
DP}~\cite{proserpio2014calibrating}, \emph{smooth
DP}~\cite{barber2014privacy} and \emph{earth mover's
privacy}~\cite{fernandes2018generalized} can be seen as instantiations of
\emph{$d_\mathcal{D}$-privacy} for some distance functions $d$.

Random DP can also be combined with changing the neighborhood definition:
in~\cite{xiao2015protecting}, the authors define \emph{DP on a $\delta$-location
set}, for which the neighborhood is defined by a set of ``plausible'' locations
around the true location of a user. In~\cite{zhou2009differential}, the authors
define \emph{constrained DP}, in which two neighboring datasets are also
required to satisfy a utility related metric constraint. Furthermore, this idea
was combined with only imposing the privacy property on a large density of
datasets in \emph{distributional
privacy}~\cite{zhou2009differential,roth2010new}.

Different risk models, like the definitions in Section~\ref{sec:q}, are also
compatible with varying the privacy parameters across inputs. For example,
in~\cite{krehbiel2019choosing}, the author proposes \emph{endogeneous DP}, which
is a combination of $\left(\eps,\del\right)$-DP and personalized DP. Similarly,
\emph{pseudo-metric DP}, defined in~\cite{dimitrakakis2013bayesian}, is a
combination of $d_{\mathcal{D}}$-privacy and $\left(\eps,\del\right)$-DP; while
\emph{extended divergence DP}~\cite{kawamoto2019allerton} combines
$d_\mathcal{D}$-privacy with divergence DP\@.

Randomly limiting the scope of the definition can also be combined with ideas
from the previous sections. For example, in~\cite{bassily2016typicality},
authors introduce \emph{typical privacy}, which combines random DP with
approximate DP\@. In~\cite{wang2016average}, the authors introduce \emph{on
average KL privacy}, which uses KL-divergence as quantification metric, but only
requires the property to hold for an ``average dataset'', like random DP\@. A
similar notion appears in~\cite{feldman2017calibrating} as \emph{average
leave-one-out KL stability}.

In~\cite{kifer2010towards}, the authors introduce \emph{general
DP}\footnote{Originally called generic DP\@; we rename it here to avoid a name
collision.}, which goes further and generalizes the intuition from generic DP, by
abstracting the indistinguishability condition entirely: the privacy relation
$\mathcal{R}$ is still the generalization of the neighborhood and the privacy
predicate is the generalization of $\varepsilon$-indistinguishability to arbitrary
functions. This definition was further extended via \emph{abstract DP}, however,
that definition does not satisfy the privacy axioms in general.

Definitions in this section are particularly used in the
context of local DP\footnote{For details, see Section~\ref{sec:local}.} 
and in particular for applications to location privacy:
various metrics have been discussed to quantify how indistinguishable different
places should be to provide users of a local DP mechanism with meaningful
privacy protection~\cite{chatzikokolakis2017methods}.

\section{Neighborhood definition (N)}\label{sec:n}

The original DP definition considers datasets differing in one record. Thus, the
datasets can differ in two possible ways: either they have the same size and
differ only on one record, or one is a copy of the other with one extra record.
These two options do not protect the same thing: the former protects the
\emph{value} of the records while the latter also protects their \emph{presence}
in the data: together, they protect any property about a single individual.

In many scenarios, it makes sense to protect a different property about their
dataset, e.g., the value of a specific sensitive field, or entire groups of
individuals. It is straightforward to adapt DP to protect
different sensitive properties: all one has to do is change the definition of
neighborhood in the original definition.

\vspace{-0.25cm}\subsection{Changing the sensitive property}\label{sec:n-changing}

The original definition states that DP should hold for ``any datasets
$D_1$ and $D_2$ that differ only in one record''. Modifying the set of pairs
$\left(D_1,D_2\right)$ such that $\mech{D_1}\approx_\varepsilon\mech{D_2}$ is equivalent
to changing the protected sensitive property.

In DP, the difference between $D_1$ and $D_2$ is sometimes interpreted as ``one
record value is different'', or ``one record has been added or removed''.
In~\cite{kifer2011no}, the authors formalize these two options as \emph{bounded
DP}\footnote{Called \emph{Per-Person DP} in~\cite{feldman2018privacy}.} and
\emph{unbounded DP}. They also introduced \emph{attribute DP} and \emph{bit DP},
for smaller changes within the differing record.

More restrictive definitions are also possible:
in~\cite{mcmahan2017learning} the authors defined \emph{client/participant
DP} which covers the case when the same person can contribute multiple times to
a dataset. \emph{$(c,\varepsilon)$-group privacy}~\cite{dwork2008differential}
considers datasets that do not differ in one record, but possibly several, to
protect multiple individuals. This can also be interpreted as taking
correlations into account when using DP\@: \emph{DP under
correlation}~\cite{chen2014correlated} uses an extra parameter to describe the
maximum number of records that the change of one individual can influence.

These two definitions are formally equivalent; but the implicit interpretation
of DP behind them is different. $(c,\varepsilon)$-group privacy is compatible with the
associative view under the strong adversary assumption (the adversary knows all
records except $c$) or the causal view ($c$ records are changed after the data
is generated). Meanwhile, DP under correlation implicitly considers the
associative view with the independence assumption; and tries to relax that
assumption. This last approach was further developed via \emph{dependent
DP}~\cite{liu2016dependence}, which uses ``dependence relationships'' to
describe how much the variation in one record can influence the other records.
Equivalents to this definition also appear in~\cite{wu2017game1,wu2017game2} as
\emph{correlated DP}, and in~\cite{yang2015bayesian} as \emph{bayesian DP}.
\footnote{Note that another notion with the same name was
defined in~\cite{leung2012bayesian}, which we introduce in
Section~\ref{sec:b}.}

The strongest possible variant is considered
in~\cite{kifer2011no} where the authors define \emph{free lunch privacy} in
which the attacker must be unable to distinguish between any two datasets, even
if they are completely different. This guarantee is a reformulation of Dalenius'
privacy goal~\cite{dalenius1977towards}; as such, all mechanisms that satisfy
free lunch privacy have a near-total lack of utility.

Another way to modify the neighborhood definition in DP is to consider that only
certain types of information are sensitive. For example, if the attacker learns
that their target has cancer, this is more problematic than if they learn that
their target does \emph{not} have cancer. This idea is captured in
\emph{one-sided DP}~\cite{doudalis2017one}: the neighbors of a dataset $D$ are
obtained by replacing a single sensitive record with any other record (sensitive
or not). The idea of sensitivity is formalized by a ``policy'', which
specifies which records are sensitive.

\begin{definition}[$(P,\varepsilon)$-one-sided differential privacy~\cite{doudalis2017one}]
    Given a policy $P\subseteq\mathcal{T}$, a privacy mechanism $\mathcal{M}$ is
    $(P,\varepsilon)$-one-sided DP iff for all datasets $D_1$ and $D_2$, where
    $D_2$ has been obtained by replacing a record $t\in D_1\cap P$ by any other
    record and for all $S\subseteq\mathcal{O}$:
    \begin{equation*}
        \proba{\mech{D_1}\in S}\leq e^{\varepsilon}\cdot\proba{\mech{D_2}\in S}
    \end{equation*}
\end{definition}

A similar ideas were proposed in~\cite{kearns2016private} as \emph{protected
DP}, which adopts DP for graphs and guarantees that no observer can
learn much about the set of edges corresponding to any protected node while
offering no guarantees for the rest. Another similar definitions is \emph{sensitive 
	privacy}~\cite{asif2019accurately}, which determines sensitive records after quantifying the 
database (instead of assuming that being an outlier/inlier is independent of the database). 
Another close definition was introduced in~\cite{bittner2018using} as 
\emph{anomaly-restricted DP}, which assumes that
there is only one outlier (which is not protected). Finally, 
in~\cite{murakami2018restricted} a more sophisticated formalization of these ideas was 
presented as \emph{utility-optimized DP}.

\vspace{-0.25cm}\subsection{Limiting the scope of the definition}\label{sec:n-scope}

Redefining the neighborhood property can also be used to reduce the scope of the
definitions. In~\cite{soria2017individual}, the authors note that DP requires
$\varepsilon$-indistinguishability of results between any pair of neighboring data sets, but
in practice, the data custodian has only \emph{one} data set $D$ they want to
protect. Thus, they only require $\varepsilon$-indistinguishability between this data set $D$
and all its neighbors, calling the resulting definition \emph{individual
DP}~\cite{soria2017individual}.

\begin{definition}[$(D,\varepsilon)$-individual differential privacy~\cite{soria2017individual}]
  Given a dataset $D\in\mathcal{D}$, a privacy mechanism $\mathcal{M}$ satisfies
  $(D,\varepsilon)$-individual DP if for any data set $D'$ that differs in at most one
  record from $D$, $\mech{D}\approx_\varepsilon\mech{D'}$.
\end{definition}

This was further restricted in \emph{per-instance DP}~\cite{wang2017per},
where besides fixing a dataset $D$, a record $t$ was also fixed.

\vspace{-0.25cm}\subsection{Applying the definition to other types of input}\label{sec:n-other}

Many adaptations of DP simply change the neighborhood definition to protect
different types of input data than datasets.

DP was adopted to graph-structured data
in~\cite{hay2009accurate,task2012guide,ding2013seamless,sealfon2016shortest,reuben2018towards,pinot2018minimum,sun2019analyzing},
to streaming data
in~\cite{dwork2010differential,dwork2010pan,dwork2010new,kellaris2014differentially,farokhi2019descount},
to symbolic control systems in~\cite{jones2018towards}, to text vectors
in~\cite{zhang2018private}, to set operations in~\cite{yan2017privmin}, to
images in~\cite{ying2013linear}, to genomic data in~\cite{simmons2016enabling},
to recommendation systems in~\cite{guerraoui2015d}, to machine learning in~\cite{long2017towards}, to location data
in~\cite{chen2018differentially}, to outsourced database systems
in~\cite{kellaris2017accessing}, to bandit algorithms
in~\cite{tossou2016algorithms,basu2019differential}, to RAMs
in~\cite{wagh2016differentially,chan2018foundations,allen2018algorithmic} and to
Private Information Retrieval in~\cite{toledo2016lower,patel2019storage}. We detail
the corresponding definitions in the full version of this work.

\vspace{-0.25cm}\subsection{Extensions}\label{sec:n-ext}

It is natural to generalize the variants of this section to arbitrary
neighboring relationships. One example is mentioned in~\cite{kifer2011no}, under
the name \emph{generic DP}, where the neighboring relation is entirely captured
by a \emph{relation} $\mathcal{R}$ between datasets.

Other definitions use different formalizations to also generalize the concept of
changing the neighborhood relationship. For example pufferfish privacy\footnote{\label{foot:later}Introduced later.} uses ``pairs of predicate''
$\left(\phi_1,\phi_2\right)$ that $D_1$ and $D_2$ must respectively satisfy to
be neighbors~\cite{kifer2012rigorous} while coupled-worlds privacy$^{\ref{foot:later}}$ use ``private functions'',
denoted $\textsf{priv}$, and define neighbors to be datasets $D_1$ and $D_2$ such as
$\textsf{priv}\left(D_1\right)\neq\textsf{priv}\left(D_2\right)$~\cite{bassily2013coupled}. 

Finally, \emph{blowfish privacy}~\cite{he2014blowfish,haney2015design}, use
a ``policy graph'' specifying which pairs of tuple values must be protected.
Others use a ``distance function'' between datasets, and neighbors are
defined as datasets a distance lower than a given threshold; this is the case
for \emph{DP under a $\Delta$-neighborhood}, introduced
in~\cite{fang2014differential} and \emph{adjacent DP}, introduced
in~\cite{krishnan2018distributional}. This distance can also be defined as the
sensitivity of the mechanism, like in \emph{sensitivity induced
DP}~\cite{rubinstein2017pain}, or implicitly defined by a set of constraints, like
in \emph{induced DP}~\cite{kifer2011no}.

\vspace{-0.25cm}\subsection{Multidimensional definitions}

Modifying the protected property is orthogonal to modifying the risk model
implied by the quantification of privacy loss: it is straightforward to combine
these two dimensions. Indeed, many definitions mentioned in this section were
actually introduced with a $\delta$ parameter allowing for a small probability of
error. One particularly general example is \emph{adjacency relation divergence
DP}~\cite{kawamoto2019allerton}, which combines an arbitrary neighborhood
definition (like in generic DP) with an arbitrary divergence function (like in
divergence DP).

As the examples in Section~\ref{sec:n-other} show, it is very common to change
the definition of neighborhood in practical contexts to adapt what aspect of the
data is protected. Further, local DP mechanisms like
RAPPOR~\cite{erlingsson2014rappor} implicitly use bounded DP\@: the
participation of one individual is not secret, only the value of their record is
protected. Variants that limit the scope of the definition to one particular
database or user, however, provide few formal guarantees and do not seem to be
used in practice.

\section{Introduction}\label{sec:intro}

What does it mean for data to be anonymized? Samarati and Sweeney
discovered that removing explicit identifiers from dataset records was not
enough to prevent information from being
re-identified~\cite{samarati2001protecting,sweeney2002kanonymity}, and they
proposed the first definition of anonymization. This notion, called
\emph{$k$-anonymity}, is a property of a dataset: each combination of
re-identifying fields must be present at least $k$ times. In the following
decade, further research showed that sensitive information about individuals
could still be leaked when releasing $k$-anonymous datasets, and many variants
and definitions were proposed such as
\emph{$l$-diversity}~\cite{machanavajjhala2006ldiversity},
\emph{$t$-closeness}~\cite{li2007tcloseness}, and
\emph{$n$-confusion}~\cite{stokes2012n}.

A shortcoming of these approaches is that they define anonymity as a property of
the \emph{dataset}: without knowing how the dataset is generated, arbitrary
information can be leaked. This approach was changed with the introduction of
\emph{differential privacy}
(DP)~\cite{dwork2006calibrating,dppatent,dwork2006differential}: rather than
being a property of the sanitized dataset, anonymity was defined as a property
of the \emph{process}. It was inspired by Dalenius' privacy goal that ``Anything
about an individual that can be learned from the dataset can also be learned
without access to the dataset''~\cite{dalenius1977towards}, a goal similar to
one already used in probabilistic encryption~\cite{shafi1984probabilistic}.

Thanks to its useful properties, DP quickly became the flagship of data privacy
definitions. Many algorithms and statistical processes were adapted to satisfy
DP and were adopted by organizations like the US Census
Bureau~\cite{abowd2010formal,garfinkel2018issues},
Google~\cite{erlingsson2014rappor}, Apple~\cite{apple2017dp}, and
Microsoft~\cite{ding2017collecting}.

Since the original introduction of DP, many relaxations
have been proposed to adapt it to different contexts or assumptions. These new
definitions enable practitioners to get privacy guarantees, even in cases that
the original DP definition does not cover well. This happens in a variety of
scenarios, e.g., the noise mandated by DP can be too large and force the data
custodian to consider a weaker alternative or the attacker model might require the
data owner to consider correlations in the data explicitly to make stronger
statements on what information the privacy mechanism reveals.

Figure~\ref{fig:timeline} shows the prevalence of this phenomenon: approximately
\emph{200} different notions, inspired by DP, were defined in the last 15 years.\footnote{
    We count all the definitions which are presented as ``new'',
    e.g., definitions which may appeared earlier, but are not cited.}
These DP definitions can be \emph{extensions} or \emph{variants} of DP\@.
An extension encompasses the original DP notion as a special case, while a
variant changes some aspect, typically to weaken or strengthen the original
definition.

\begin{figure}[h!]
    \centering
    \includegraphics[width=8cm]{pics/timeline}
    \caption{Accumulated number of papers which are introducing new DP notions
      (line) and the exact number of these definitions
      (bar).}\label{fig:timeline}
\end{figure}

With so many definitions, it is difficult for new practitioners to get an
overview of this research area. Many definitions have similar goals, so it is
also challenging to understand which it is appropriate to use in which context.
These difficulties also affect experts: several definitions listed in this work
have been defined independently multiple times (occasionally with identical 
meaning but different names or identical names but different meanings). Finally, 
variants are often introduced without a comparison to related notions.

This work attempts to solve these problems. It is a taxonomy
of various and extensions of DP, providing short explanations of the intuition,
use cases and basic properties of each. By categorizing these definitions, we
also hope to simplify the understanding of existing variants and extensions, and
of the relations between them.

\vspace{-0.25cm}\subsection*{Contributions and organization}

We systematize the scientific literature on variants and extensions of DP, and
propose a unified and comprehensive taxonomy of these definitions. We define
seven \emph{dimensions}: these are ways in which the original definition of DP
can be modified. Moreover, we highlight representative definitions for each
dimension, and we enlist whether they satisfy
Kifer et al.'s \emph{privacy axioms}~\cite{kifer2010towards,kifer2012axiomatic},
(post-processing and convexity), and whether they are composable. Our survey is organized as follows.

In Section~\ref{sec:pre}, we recall the original definition of DP and introduce
our dimensions along which DP can be modified. Moreover, we present the basic
properties of DP, and define how definitions can relate to each other. In the
following 7 sections (Sections~\ref{sec:q} to~\ref{sec:c}), we introduce our
dimensions and list the corresponding definitions. In Section~\ref{sec:related},
we review the methodology and scope of this work and mention the relevant works
from the literature. In Section~\ref{sec:conc}, we conclude the paper.
