examples.tex.bak

A simple way to design differentially private mechanisms is to add
random noises.
Now we describe our main ideas for  modelling differentially private mechanisms.
A state $s$ stores at least a database $x\in \mathcal{X}^n$, which is the data held by a trusted \emph{curator}. A transition corresponds to a data analysis mechanism.
States are typically labelled with the corresponding outputs
the curator generates. We explain the main idea with some examples.

\subsection{Survey Mechanisms}
\label{subsec:survey}

Consider the survey question: have you been diagnosed
with the disease $X$? In order to protect surveyees' privacy, each
answers the question as follows. The surveyee first flips a
coin. If it is tail, she answers the question truthfully. Otherwise,
she randomly answers \textit{Yes} or \textit{No}
uniformly~\cite{DR:14:AFDP}.

Let us analyze the mechanism briefly. The data universe $\mathcal{X}$
is $\{ +, - \}$. The mechanism $M$ is a randomized algorithm with
inputs in $\mathcal{X}$ and outputs in $\{ Y, N \}$. For any $x \in
\mathcal{X}$, we have $\frac{1}{4} \leq \Pr[M (x) = Y] \leq
\frac{3}{4}$. Hence $\Pr[M (x) = Y] \leq \frac{3}{4} = 3 \cdot
\frac{1}{4} \leq e^{\ln 3} \Pr[M (x') = Y]$ for any neighboring $x, x'
\in \mathcal{X}$. Similarly, $\Pr[M (x) = N] \leq e^{\ln 3} \Pr[M (x')
= N]$. The survey mechanism is $(\ln 3, 0)$-differentially private.

\begin{figure}
  \centering
  \begin{subfigure}{.48\columnwidth}
      \[
      \begin{array}{|c|c|c|}
        \hline
        &
        \multicolumn{2}{c|}{output}
        \\
        \hline
        state & Y & N \\
        \hline
        + & \frac{3}{4} = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot 1
          & \frac{1}{4} = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot 0
        \\
        \hline
        - & \frac{1}{4} = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot 0
          & \frac{3}{4} = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot 1
        \\
        \hline
      \end{array}
      \]
    \caption{Survey Mechanism}
    \label{figure:2-dp-table}
  \end{subfigure}
  \hspace{.05\columnwidth}
  \begin{subfigure}{.40\columnwidth}
    \resizebox{\columnwidth}{!}{
    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node
      distance=2cm,node/.style={circle,draw}]
      \node[node] (p) at ( 0,  .5) { $+$ };
      \node[node] (n) at ( 0, -.5) { $-$ };
      \node[node] (Y) at (-1.5,  0) { $s$ };
      \node at (-1.5, .5) { $\mathit{out}_Y$ };
      \node[node] (N) at ( 1.5,  0) { $t$ };
      \node at ( 1.5, .5) { $\mathit{out}_N$ };

      \path
      (p) edge node [above] { $\frac{3}{4}$ } (Y)
      (p) edge node [above] { $\frac{1}{4}$ } (N)
      (n) edge node [below] { $\frac{1}{4}$ } (Y)
      (n) edge node [below] { $\frac{3}{4}$ } (N)
      ;
      \end{tikzpicture}
    }
    \caption{Corresponding Markov Chain}
    \label{figure:2-dp-mdp}
  \end{subfigure}
  \caption{Survey Mechanism with $\ln 3$-Differential Privacy}
  \label{figure:2-dp}
\end{figure}

\begin{example}\label{exa:survey}
  Figure~\ref{figure:2-dp} shows the survey
mechanism and its corresponding Markov chain.
In the figure, the states
$+$ and $-$ denote the diagnoses are positive or negative
respectively; the states $s$ and $t$ denote answers to the survey
question and hence let $\mathit{out}_Y \in L (s)$ and $\mathit{out}_N
\in L (t)$.
States $+$ and $-$ are neighbors.
The random noise boosts the probability of answering
\textit{Yes} or \textit{No} to at least $1/4$ regardless of
diagnoses. Inferences on individual diagnosis can be plausibly denied.
Missing transitions (such as those from $s$ and $t$) lead
to a special state $\dagger$ with a self-loop. We omit the transitions
and the state $\dagger$ for clarity.
\end{example}


\subsection{Truncated $\alpha$-Geometric Mechanism}\label{subsec:geometric}
More sophisticated differentially private mechanisms are
available. Consider a query
$f : \mathcal{X}^n \rightarrow \bbfZ^{\geq 0}$. Let $\alpha \in (0, 1)$.
The \emph{$\alpha$-geometric mechanism}
outputs $f(x) + Y$ where $Y$ is a random variable with the geometric
distribution~\cite{GRS:09:UUPM,GRS:12:UUPM} :
\[
\Pr[Y = y] = \frac{1 - \alpha}{1 + \alpha}\alpha^{|y|}
\textmd{ for } y \in \bbfZ.
\]
The $\alpha$-geometric mechanism is oblivious since it has the same
output distribution on any inputs $x, x'$ with $f (x) = f
(x')$. Moreover, it is $(- {\Delta (f)} \ln \alpha, 0)$-differentially
private for any query $f$ with sensitivity $\Delta (f)$. The range of
the mechanism
however is $\bbfZ$. It may give nonsensical outputs such as
negative integers for queries with positive ranges.

The \emph{truncated $\alpha$-geometric mechanism over $\{ 0, 1,
  \ldots, n \}$}
outputs $f (x) + Z$ where $Z$ is a random variable with the following
distribution:
\[
\Pr[Z = z] =
\left\{
  \begin{array}{ll}
    0 & \textmd{ if } z < - f (x) \\
    \frac{\alpha^{f (x)}}{1 + \alpha} & \textmd{ if } z = -f (x)\\
    \frac{1 - \alpha}{1 + \alpha}\alpha^{|z|} &
    \textmd{ if } -f (x) < z < n - f (x)\\
    \frac{\alpha^{n - f (x)}}{1 + \alpha} & \textmd{ if } z = n-f (x)\\
    0 & \textmd{ if } z > n - f (x)
  \end{array}
\right.
\]
Note the range of the truncated $\alpha$-geometric mechanism is
$\{ 0, 1, \ldots, n \}$. The truncated $\alpha$-geometric mechanism is
again oblivious; it is also $(- {\Delta (f)} \ln \alpha, 0)$-differentially
private for any query $f$ with sensitivity $\Delta (f)$.
The truncated $\frac{1}{2}$-geometric mechanism over $\{ 0, 1, \ldots, 5 \}$ is
given in Figure~\ref{figure:geometric-mechanism-table}.

\begin{figure}[tbh]
  \centering
  \begin{subfigure}{.40\columnwidth}
    \[
    \begin{array}{|c|c|c|c|c|c|c|}
      \hline
      \textmd{input/output} & 0 & 1 & 2 & 3 & 4 & 5\\
      \hline
      0 & {2}/{3}  & {1}/{6} & {1}/{12} & {1}/{24}  & {1}/{48} & {1}/{48}\\
      \hline
      1 & {1}/{3}  & {1}/{3} & {1}/{6} & {1}/{12}  & {1}/{24} & {1}/{24}\\
      \hline
      2 & {1}/{6}  & {1}/{6} & {1}/{3} & {1}/{6}   & {1}/{12} & {1}/{12}\\
      \hline
      3 & {1}/{12} & {1}/{12} & {1}/{6} & {1}/{3}   & {1}/{6} & {1}/{6}\\
      \hline
      4 & {1}/{24} & {1}/{24} & {1}/{12} & {1}/{6}   & {1}/{3} & {1}/{3}\\
      \hline
      5 & {1}/{48} & {1}/{48} & {1}/{24} & {1}/{12} & {1}/{6} & {2}/{3}\\
      \hline
    \end{array}
    \]
    \caption{$1/2$-Geometric Mechanism}
    \label{figure:geometric-mechanism-table}
  \end{subfigure}
  \hspace{.08\columnwidth}
  \begin{subfigure}{.50\columnwidth}
    \centering
  \resizebox{.85\columnwidth}{!}{
    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node
      distance=2cm,node/.style={circle,draw}]
      \node[node] (i0) at (0,  1) { $s_0$ };
      \node at (0, 1.5) { $\mathit{in}_0$ };
      \node at (0, 0) { $\vdots$ };
      \node at (.8, -.8) { $\vdots$ };
      \node[node] (i5) at (0, -1) { $s_5$ };
      \node at (0, -.5) { $\mathit{in}_5$ };

      \node[node] (o0) at (4,  2.5) { $t_0$ };
      \node at (4, 3) { $\mathit{out}_0$ };
      \node[node] (o1) at (4,  1.5) { $t_1$ };
      \node at (4, 2) { $\mathit{out}_1$ };
      \node[node] (o2) at (4,  0.5) { $t_2$ };
      \node at (4, 1) { $\mathit{out}_2$ };
      \node[node] (o3) at (4, -0.5) { $t_3$ };
      \node at (4, 0) { $\mathit{out}_3$ };
      \node[node] (o4) at (4, -1.5) { $t_4$ };
      \node at (4, -1) { $\mathit{out}_4$ };
      \node[node] (o5) at (4, -2.5) { $t_5$ };
      \node at (4, -2) { $\mathit{out}_5$ };

      \path
      (i0) edge node [right=30,above=10] { $2/3$ } (o0)
      (i0) edge node [right=30,above=3] { $1/6$ } (o1)
      (i0) edge node [right=30,above=-3] { $1/12$ } (o2)
      (i0) edge node [right=30,below=-5] { $1/24$ } (o3)
      (i0) edge node [right=30,below] { $1/48$ } (o4)
      (i0) edge node [right=30,below=8] { $1/48$ } (o5)

      \hide{
      (i1) edge node [above] {  } (o0)
      (i1) edge node [above] {  } (o2)
      (i1) edge node [above] {  } (o3)
      (i1) edge node [above] {  } (o4)
      (i1) edge node [above] {  } (o5)

      (i2) edge node [above] {  } (o0)
      (i2) edge node [above] {  } (o2)
      (i2) edge node [above] {  } (o3)
      (i2) edge node [above] {  } (o4)
      (i2) edge node [above] {  } (o5)

      (i3) edge node [above] {  } (o0)
      (i3) edge node [above] {  } (o2)
      (i3) edge node [above] {  } (o3)
      (i3) edge node [above] {  } (o4)
      (i3) edge node [above] {  } (o5)

      (i4) edge node [above] {  } (o0)
      (i4) edge node [above] {  } (o2)
      (i4) edge node [above] {  } (o3)
      (i4) edge node [above] {  } (o4)
      (i4) edge node [above] {  } (o5)
      }

      (i5) edge node [right=10,above=16] { $1/48$ } (o0)
      \hide{
      (i5) edge node [above] {  } (o2)
      (i5) edge node [above] {  } (o3)
      (i5) edge node [above] {  } (o4)
      }
      (i5) edge node [right=15,below=8] { $2/3$ } (o5)
      ;
      \end{tikzpicture}
    }
    \caption{Markov Chain}
    \label{figure:geometric-mechanism-markov-chain}
  \end{subfigure}
  \caption{A Markov Chain for $\frac{1}{2}$-Geometric Mechanism}
  \label{figure:geometric-mechanism}\vspace*{-.5cm}
\end{figure}

Similar to the survey mechanism, it is
straightfoward to model the truncated $\frac{1}{2}$-geometric
mechanisms as Markov chains.

\begin{example}
Let the state $s_k$ and $t_l$
denote the input value $k$ and output value $l$ respectively. Define
the state set $S = \{ s_k, t_k : k \in \{ 0, 1, \ldots, n \} \}$.
The probability transition $\wp (s_k, t_l)$ is the probability of the
output value $l$ on the input value $k$ as defined in the
mechanism. Moreover, we have $\mathit{in}_k \in L (s_k)$ and
$\mathit{out}_k \in L (t_k)$ for $k \in \{ 0, 1, \ldots, n \}$.
If $\Delta (f) = 1$, $s_k$ and $s_l$ are
neighbors iff $| k - l | \leq 1$.
Figure~\ref{figure:geometric-mechanism-markov-chain} gives
the Markov chain of the truncated
$\frac{1}{2}$-geometric mechanism over $\{ 0, 1, \ldots, 5 \}$.
\end{example}

\begin{algorithm}[tbh]
	\begin{algorithmic}[1]
		\Function{OnlineModel}{$d$, $t$}
		\Match{the input threshold $t$}
		\Comment{Assignments of $t'$ by $\frac{1}{4}$-geometric mechanism}
		\lCase{$0$}{$t' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{4}{5}$,$\frac{3}{20}$,
			$\frac{3}{80}$,$\frac{3}{320}$,
			$\frac{3}{1280}$,$\frac{1}{1280}$ respectively}
		\lCase{$1$}{$t' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{5}$,$\frac{3}{5}$,
			$\frac{3}{20}$,$\frac{3}{80}$,
			$\frac{3}{320}$,$\frac{1}{320}$ respectively}
		\lCase{$2$}{$t' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{20}$,$\frac{3}{20}$,
			$\frac{3}{5}$,$\frac{3}{20}$,
			$\frac{3}{80}$,$\frac{1}{80}$ respectively}
		\lCase{$3$}{$t' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{80}$,$\frac{3}{80}$,
			$\frac{3}{20}$,$\frac{3}{5}$,
			$\frac{3}{20}$,$\frac{1}{20}$ respectively}
		\lCase{$4$}{$t' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{320}$,$\frac{3}{320}$,
			$\frac{3}{80}$,$\frac{3}{20}$,
			$\frac{3}{5}$,$\frac{1}{5}$ respectively}
		\lCase{$5$}{$t' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{1280}$,$\frac{3}{1280}$,
			$\frac{3}{320}$,$\frac{3}{80}$,
			$\frac{3}{20}$,$\frac{4}{5}$ respectively}
		\EndMatch
		\For{each query $f_i$}
		\Match{the input databese $d$}
		\Comment{Assignments of $f_{i}'$ by $\frac{1}{2}$-geometric mechanism}
		\lCase{$0$}{$f_{i}' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{2}{3}$,$\frac{1}{6}$,
			$\frac{1}{12}$,$\frac{1}{24}$,
			$\frac{1}{48}$,$\frac{1}{48}$ respectively}
		\lCase{$1$}{$f_{i}' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{3}$,$\frac{1}{3}$,
			$\frac{1}{6}$,$\frac{1}{12}$,
			$\frac{1}{24}$,$\frac{1}{24}$ respectively}
		\lCase{$2$}{$f_{i}' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{6}$,$\frac{1}{6}$,
			$\frac{1}{3}$,$\frac{1}{6}$,
			$\frac{1}{12}$,$\frac{1}{12}$ respectively}
		\lCase{$3$}{$f_{i}' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{12}$,$\frac{1}{12}$,
			$\frac{1}{6}$,$\frac{1}{3}$,
			$\frac{1}{6}$,$\frac{1}{6}$ respectively}
		\lCase{$4$}{$f_{i}' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{24}$,$\frac{1}{24}$,
			$\frac{1}{12}$,$\frac{1}{6}$,
			$\frac{1}{3}$,$\frac{1}{3}$ respectively}
		\lCase{$5$}{$f_{i}' \leftarrow 0, 1,2,3,4,5$ with probability
			$\frac{1}{48}$,$\frac{1}{48}$,
			$\frac{1}{24}$,$\frac{1}{12}$,
			$\frac{1}{6}$,$\frac{2}{3}$ respectively}
		\EndMatch
		\If{$f_{i}'>t'$}
		\State{$a_i=\top$}
		\State{\Return}
		\Else
		\State{$a_i=\bot$}
		\EndIf
		\EndFor
		\EndFunction
		
	\end{algorithmic}
	\caption{Input is a private database $d \in \{0,1,\ldots,5\}$, an adaptively chosen stream of sensitivity 1 queries $f_1,f_2$,\ldots, a threshold $t \in \{0,1,\ldots,5\}$. Output is a stream of answers $a_1,a_2$,\ldots}
	\label{algorithm:online-model}
\end{algorithm}

\subsection{Above Threshold Mechanisms}
In the differentially privacy context, we differentiate between \emph{offline} and \emph{online} models.
In the offline (or \emph{non-interactive}) model the curator releases the outputs only once and plays no further role. Thus the models we constructed in previous section are offline models. On the contrary, in the online (or \emph{interactive}) model the curator can permit further queries. In this setting it is obvious that queries do not change database themselves. To maintain differential privacy, the curator however can decide to change data analysis mechanisms accordingly. For instance, after a certain output is disclosed or a certain number of queries, it may decide to disable further queries.

Below we describe an online model adapted from~\cite{DR:14:AFDP}: it is used in the scenario where a large amount of queries occur, but we only care for the queries which
are above a given threshold. Other queries below the threshold are considered \emph{irrelevant} and won't cause privacy disclosure. In~\cite{DR:14:AFDP}, the model is set for continuous database, and the Laplace mechanisms are applied to both queries and the threshold. In our model, the database is discrete and instead the geometric mechanisms are applied.

We consider the database set $D = \{0,1\ldots,5\}$, a threshold $t \in \{0,1\ldots,5\}$, and queries $\{f| f $ with sensitivity $\Delta (f) = 1 \}$. In order to protect privacy, truncated $\alpha$-geometric mechanisms over $\{0,1\ldots,5\}$ are applied to each query and the threshold, and what we observe is the first time that a query result is greater than or equal to the threshold after interference. We are interested in the differentially private property of the data in $D$, assuming that a pair of data $d,d'$are neighbours, if $|d-d'|\le 1$. The algorithm is shown in Algorithm~\ref{algorithm:online-model} and a property will be specefied in Section~\ref{section:specifying-properties}.