
\subsection{Intuition}
We believe that there is a subtle error in the privacy analysis in prior work (discussed in Section~\ref{sec:GPTT}). Prior work splits the probability $V(\mathbf{v})$ as: 
\begin{eqnarray*}
V(\mathbf{v}) & = & \prod_{i:v_i = \bot} P[v_i = \bot | \mathbf{v}^{<i}] \prod_{i:v_i = \top} P[v_i = \top | \mathbf{v}^{<i}] \\ 
& = & \int f(x) \prod_{i:v_i = \bot} P[v_i = \bot | x, \mathbf{v}^{<i}]dx\\
&& \times \int f(x) \prod_{i:v_i = \top} P[v_i = \top | x, \mathbf{v}^{<i}]dx\\
& = & \int f(x) \prod_{i:v_i = \bot} P[v_i = \bot | x]dx \\
&& \times \int f(x) \prod_{i:v_i = \top} P[v_i = \top | x]dx
\end{eqnarray*}
where $f(x) = P[\tilde{\theta} = x]$. 
This decomposition into $\top$ and $\bot$ answers are wrong. The main problem comes from the fact that it uses the unconditioned $f(x)$ for all queries, but the distribution of the noisy threshold would be affected given the previous output. To take a simple example, let $q_1 = m > 0$, $q_2 = 0$, $\theta = 0$ and assume $v_1 = \bot$, $v_2 = \top$. For ease of explanation assume $\epsilon_2 = \infty$ (but the argument would work for finite $\epsilon_2$ as well). Now we can compute the probability of GPTT outputing $v_1$, $v_2$ as
\begin{eqnarray*}
P(v_1 = \bot, v_2 = \top)& =& P(v_1 = \bot)P(v_1 = \bot \mid v_2 = \top) \\ 
&=& P(v_1 = \bot)P(m < \tilde{\theta} \mid 0 \ge \tilde{\theta}) = 0
\end{eqnarray*}

However, if we use the expression above, we have
\begin{eqnarray*}
V(\mathbf{v}) & = & \prod_{i:v_i = \bot} P[v_i = \bot | \mathbf{v}^{<i}] \prod_{i:v_i = \top} P[v_i = \top | \mathbf{v}^{<i}] \\
&=& \int f(x) P(v_1 = \bot \mid x)dx \times \int f(x) P(v_2 = \top \mid x)dx \\
&=& \int f(x) P(m < x)dx \times \int f(x) P(0 > x) dx \\
&=& F(m) \times (1 - F(0)) > 0
\end{eqnarray*}
where $F(x)$ is the distribution function of the noisy threshold.

Actually, the right decomposition should be 
\begin{eqnarray*}
V(\mathbf{v}) & = & \prod_{i:v_i = \bot} P[v_i = \bot | \mathbf{v}^{<i}] \prod_{i:v_i = \top} P[v_i = \top | \mathbf{v}^{<i}] \\ 
&=& \prod_{i:v_i = \bot} \int f(x | \mathbf{v}^{<i} ) P[v_i = \bot | x, \mathbf{v}^{<i}]dx\\
&& \times \prod_{i:v_i = \top} \int f(x | \mathbf{v}^{<i} )  P[v_i = \top | x, \mathbf{v}^{<i}]dx\\
&=& \prod_{i:v_i = \bot} \int f(x | \mathbf{v}^{<i} ) P[v_i = \bot | x]dx\\
&& \times \prod_{i:v_i = \top} \int f(x | \mathbf{v}^{<i} )  P[v_i = \top | x]dx
\end{eqnarray*}


\eat{
\subsection{Claim~1 does not hold}
We show that Claim~\ref{claim:1} does not hold by showing that the probability that a query answer $v_i = 1$ is not independent of the previous query answers $v^{<i}$.

\begin{lemma}
\label{lemma:1}
Let $Q$ be a set of queries and $\mathbf{v}$ be the vector of answers output by GPTT with parameters  $\epsilon_1$ and $\epsilon_2$. Let $v_i$ be the answer to the $i^{th}$ query and $\mathbf{v}^{<i}$ be the answers to all the queries for $j < i$. Then, 
\[P[v_i = 1 \mid  v^{<i}] \ \neq \ P[v_i = 1] \]
\end{lemma}
\begin{proof}
We show this using a counterexample. Let $Q = \{q_1, q_2\}$ that both have sensitivity $\Delta = 1$. Let $D$ be a database such that $q_1 = m$, $q_2 = 0$, and and let threshold $\theta = 0$. Consider the following two probabilities, $P = P[v_2 = 0]$ and $P'= P[v_2 = 0 |  v_1 = 0)$. 
\begin{eqnarray*}
P&=& P[v_2 = 0 ] = P[\tilde{q_2} < \tilde{\theta}) \ = \ \frac{1}{2}\\
P' &=& P[v_2 = 0 | \wedge v_1 = 0]\\
&=&\frac{P[v_1 = 0, v_2 = 0 ]}{P[v_1 = 0 ]} \\
&=& \frac{P(\tilde{q_1} < \tilde{\theta}, \tilde{q_2} < \tilde{\theta})}{P(\tilde{q_2} < \tilde{\theta})}
\end{eqnarray*}

It is easy to see that when $q_2 = m$ is large enough, if $\tilde{q_2} < \tilde{\theta}$, $\tilde{q_1} < \tilde{\theta}$ will be true with very high probability and $P_2$ will tends to 1 when m goes to infinity. Since $P_1 = P_2$ does not hold, the output of $q_1$ and $q_2$ is not independent.
\end{proof}


Based on Lemma~\ref{lemma:1}, we know $P(v_i) \neq P(v_i \mid v^{-i})$. If Claim~\ref{claim:1} is correct, which means $P(v_i = 1 \mid x, v^{<i}) = P(v_i = 1 \mid x)$. By integrating $x$ on both sides, we get the contradiction. Therefore, Claim~\ref{claim:1} is incorrect.
}

\subsection{GPTT}



GPTT takes as input a dataset $D$, a set of queries $Q=\{q_1,\dots,q_n\}$ with bounded sensitivity $\Delta$, threshold $\theta$ and a privacy budget $\epsilon$. For every query GPTT  outputs either $\bot$ or $\top$ that approximates whether or not the queries are smaller than the threshold. GPTT works exactly like SVT -- the threshold is perturbed using noise drawn from $Lap(\Delta/\epsilon_1)$ and the queries are perturbed using noise from $Lap(\Delta/\epsilon_2)$, and the output is computed by comparing the noisy query answer with the noisy threshold. The only difference is that there is no limit on the number of positive or negative queries. 

GPTT is a generalization of variations presented in prior work. 
Lee and Clifton \cite{NoiseCut} used GPTT for private frequent itemset mining with $\epsilon_{1} = \frac{\epsilon}{4}$ and $\epsilon_2 = \frac{3\epsilon}{4}$. Chen et al \cite{KDD15} instantiate GPTT with  $\epsilon_1 = \epsilon_2 = \frac{\epsilon}{2}$, for generating synthetic data. Stoddard et al \cite{EML} observed that the privacy guarantee does not depend on $\epsilon_2$ and propose the Private Threshold Testing algorithm that is identical to GPTT with $\epsilon_1 = \epsilon$ and $\epsilon_2 = \infty$. Private threshold testing was used for private feature selection for classification. 

\subsection{Privacy Analysis of GPTT}
We now extend the privacy analysis from prior work \cite{NoiseCut, KDD15, EML} to generalized private threshold testing. We will show in the next section that this privacy analysis is flawed and that GPTT does not satisfy differential privacy. 

\begin{algorithm}[t]
\caption{Generalized Private Threshold Testing}
Input: Dataset $D$,  a set of queries $Q=\{q_1,\dots,q_n\}$ with bounded sensitivity $\Delta$, threshold $\theta$, privacy parameters $\epsilon_1$, $\epsilon_2$\\
Output: A vector of answers $\mathbf{v} = [v_1, v_2, \ldots, v_n]\in \{\bot, \top\}^n$
\begin{algorithmic}[1]
	\State $\tilde{\theta} \gets \theta + Lap(\Delta/\epsilon_1)$
	\For{ $q_i \in Q$}
		\State $\tilde{q}_i \gets q_i(D) + Lap(\Delta/\epsilon_2)$
		\If {$\tilde{q}_i < \tilde{\theta}$}
			\State $v_i \gets \bot$
		\Else
			\State $v_i \gets \top$
		\EndIf
	\EndFor
	\State\Return $\mathbf{v}$
\end{algorithmic}
\label{alg:GPTT}
\end{algorithm}
 
Given any set of queries $Q=\{q_1,\dots,q_n\}$, let the vector $\mathbf{v} = <v_1,\dots,v_n> \in \{\bot, \top\}^n$ denote the output of GPTT. Given any two neighbering databases $D_1$ and $D_2$, let $V_1$ and $V_2$ denote the output distribution on $\mathbf{v}$ when $D_1$ and $D_2$ are the input databases, respectively. We use $\mathbf{v}^{<t}$ to denote $t-1$ previous answers(i.e., $\mathbf{v}^{<t}=<v_1,\dots,v_{t-1}>$). Then we have
\begin{eqnarray*}
\frac{V_1(\v)}{V_2(\v)} &=& \frac{\prod_{i=1}^{n}V_1(v_i =a_i \mid \v^{<i})}{\prod_{i=1}^{n}V_2(v_i =a_i \mid \v^{<i})} \\
&=& \prod_{i:a_i=\top}\frac{V_1(v_i =\top \mid \mathbf{v}^{<i})}{V_2(v_i =\top \mid \mathbf{v}^{<i})}\prod_{i:a_i=\bot}\frac{V_1(v_i =\bot \mid \mathbf{v}^{<i})}{V_2(v_i =\bot \mid \mathbf{v}^{<i})}
\end{eqnarray*}

Let $H_i$(x) be the probability that $q_i$ is positive (i.e., $v_i = \top$) in $D$ when the noisy threshold is $x$. That is, 
\begin{eqnarray*}
H_i(x)  = P[v_i = \top \mid \tilde{\theta} = x, \mathbf{v}^{<i}
\end{eqnarray*}
Then, given a specific noisy threshold $\tilde{\theta} = x$, the probability that $v_i = \top$ is independent of the answers to previous queries. That is, 
\begin{equation}
H_i(x)  \ =\  P[v_i = \top \mid x, \mathbf{v}^{<i}] = P[v_i = \top \mid x] 
\end{equation}
Thus, if $f(y; \mu, \lambda) =  \frac{1}{2\lambda}exp(-\frac{|y-\mu|}{\lambda})$, then
\begin{eqnarray*}
H_i(x)  &=& \int_{x}^{\infty} f(y; q_i, \frac{\Delta}{\epsilon_2})dy \ = \ \int_{x+\Delta}^{\infty} f(y; q_i + \Delta, \frac{\Delta}{\epsilon_2})dy
\end{eqnarray*}



Prior work uses the above property of $H_i(x)$ to show that GPTT satisfies $2\epsilon_1$-differential privacy.

Let $S = \{i \mid a_i = \top~and~q_i(D_1) = q_i(D_2)\}$ and $\bar{S} = \{i \mid a_i = \top~and~q_i(D_1) \neq q_i(D_2)\}$.
\begin{eqnarray*}
\prod_{i:a_i=\top}V_1(v_i =\top \mid \mathbf{v}^{<i}) = \prod_{i \in S}V_1(v_i =\top \mid \mathbf{v}^{<i})\prod_{i \in \bar{S}}V_1(v_i =\top \mid \mathbf{v}^{<i})
\end{eqnarray*}
Let $H_i^{1}(x)$ and $H_i^{2}(x)$ denote the probability that $v_i = \top$ in $D_1$ and $D_2$, resp., when the noisy threshold is $x$. Then we have, 
\begin{eqnarray*}
&&\prod_{i \in S}V_1(v_i =\top \mid \mathbf{v}^{<i})\\
&=& \int_{-\infty}^{\infty} P[\tilde{\theta} = x] \prod_{i \in S} H_i^{1}(x)dx  \\
&=& \int_{-\infty}^{\infty} P[\tilde{\theta} = x] \prod_{i \in S} H_i^{2}(x)dx \mbox{\hspace{5mm} since $q_i(D_1) = q_i(D_2)$}\\
& =& \prod_{i \in S}V_2(v_i =\top \mid \mathbf{v}^{<i}) 
\end{eqnarray*}
\begin{eqnarray*}
&&\prod_{i \in \bar{S}}V_1(v_i =\top \mid \mathbf{v}^{<i})\\
&=& \int_{-\infty}^{\infty} P[\tilde{\theta} = x] \prod_{i \in \bar{S}} H_i^{1}(x)dx\\
&\leq& exp(\epsilon_1)\int_{-\infty}^{\infty}P[\tilde{\theta} = x - \Delta]\prod_{i \in \bar{S}} H_i^{2}(x-\Delta)dx\\
&=& \prod_{i \in \bar{S}}V_2(v_i =\top \mid \mathbf{v}^{<i})
\end{eqnarray*}

Thus, it is seen that 
\begin{eqnarray*}
\prod_{i:a_i=\top}V_1(v_i =\top \mid \mathbf{v}^{<i}) \leq exp(\epsilon_1) \prod_{i:a_i=\top}V_2(v_i =\top \mid \mathbf{v}^{<i})
\end{eqnarray*}
Similarly, 
\begin{eqnarray*}
\prod_{i:a_i=\bot}V_1(v_i =\bot \mid \mathbf{v}^{<i}) \leq exp(\epsilon_1) \prod_{i:a_i=\bot}V_2(v_i =\bot \mid \mathbf{v}^{<i})
\end{eqnarray*}
Therefore, $\frac{V_1(v)}{V_2(v)} \leq exp(2\epsilon_1)$

\stitle{Remarks:} Note that adding noise to the queries is not really required. The above proof will go through even if $\epsilon_2 = \infty$. In fact as we will see next, we can achieve the same utility no matter what the value of $\epsilon_2$ is. 

\subsection{Utility of GPTT}
We first consider the utility of the case when $\epsilon_2 = \infty$ (i.e. no noise added to queries), and show that we can achieve (almost) the same utility even when $\epsilon_2$ is finite. 

\begin{theorem}
\label{theo:PTT}
For GPTT with parameters $\epsilon_1$ and  $\epsilon_2 = \infty$, with the probability at least $1-\delta$, $v_i = \bot$ implies $q_i < \theta + \alpha$ and $v_i = \top$ implies $q_i > \theta - \alpha$, where
\begin{eqnarray*}
\alpha = \frac{\Delta}{\epsilon_1}\log(\frac{1}{\delta})
\end{eqnarray*}
where $\Delta$ is the max sensitivity of input queries.
\end{theorem}
\begin{proof}
All we need to show is that the noise added to the threshold is at most $\pm \alpha$  with probability $1-\delta$. Since $\tilde{\theta} = \theta + Lap(\frac{\Delta}{\epsilon_1})$, we have
\begin{eqnarray*}
\lefteqn{P(|\tilde{\theta} - \theta|) < \alpha)  \ge 1-\delta }\\
&\Rightarrow& P(-\alpha<Lap(\frac{\Delta}{\epsilon_1})<\alpha) \ge 1-\delta \\
&\Rightarrow& P(Lap(\frac{\Delta}{\epsilon_1}) > \alpha) \leq \frac{\delta}{2}\\
&\Rightarrow& 1 - (1-\frac{1}{2} exp(-\frac{\epsilon_1 \alpha}{\Delta})) \leq \frac{\delta}{2}\\
&\Rightarrow& \alpha \ge \frac{\Delta}{\epsilon_1} \log(\frac{1}{\delta})
\end{eqnarray*}
\end{proof}



Now we extend the utility for GPTT when $\epsilon_2 < \infty$.

\begin{theorem}
\label{theo:GPTT}
Let $D$ be a database and $Q$ a query set with maximum sensitivity of $\Delta$. For every $\beta, \delta > 0$, we can use GPTT with parameters $\epsilon_1, \epsilon_2 < \infty$ to determine whether $q_i < \theta + \alpha$ or $q_i > \theta - \alpha$ for any $q_i \in Q$, with probability $(1-\delta)(1 - \beta)$, where
\begin{eqnarray*}
\alpha = \frac{\Delta}{\epsilon_1}\log(\frac{1}{\delta})
\end{eqnarray*}
\end{theorem}
\begin{proof}
Since the privacy of GPTT does not depend on the number of queries $Q$ (as long as sensitivity is bounded by $\Delta$), we can consider a new query set $Q'$ that has $t$ copies $\{q_{i1}, q_{i2}, \ldots, q_{it}\}$ of each query $q_i \in Q$. Then for each query $q_i \in Q$, we have t independent comparisons of the noisy query answer $\tilde{q}_{ij}$ and the noisy threshold $\tilde{\theta}$. We use the majority of these $t$ results to determine whether $q_i$ is smaller or greater than $\tilde{\theta}$. 

We can show that with probability at least $1-\beta$, we can correctly identify whether $q_i(D)$ is greater or lesser than the noisy threshold $\tilde{\theta}$.

Without loss of generality, suppose $q_i < \tilde{\theta}$, then $p = P(\tilde{q_i} < \tilde{\theta}) > \frac{1}{2}$. Let $\{X_j, j \ge 1\}$ be an sequence of i.i.d. binary random variables with expected $E[X_j]=p$, where $X_j$ is $1$ if $\tilde{q}_{ij} < \tilde{\theta}$ and $0$ otherwise. Based on the law of large numbers, for any positive number $\gamma$ we have

\begin{eqnarray*}
&&\underset{t \to \infty}{lim} Pr(|\frac{1}{t}(X_1+\dots+X_t) - p| > \gamma) = 0\\
&\Rightarrow& \underset{t \to \infty}{lim} Pr(X_1+\dots+X_t > \frac{t}{2}) = 1
\end{eqnarray*}

Thus, there exists a number $t$ s.t. for every $q_i \in Q$, we can determine whether $q_i$ is smaller or greater than $\tilde{\theta}$ with probability greater than $1-\frac{\beta}{|Q|}$. So all the $q_i$ will be correctly judged with probability equals to $ (1-\frac{\beta}{|Q|})^{|Q|} \approx 1-\beta$.

We get the desired result by now combining with the proof of Theorem~\ref{theo:PTT}.
\end{proof}

We can see that the information leaked by GPTT with $\epsilon_2 < \infty$ will tend to the information leaked by GPTT with $\epsilon_2 = \infty$ as the number of copies $t$ goes to infinity. Thus, we can just focus on the case when $\epsilon_2 = \infty$. 







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

\section{Preliminaries}\label{sec:prelim}
\input{prelim}



\section{Generalized Private Threshold Testing} \label{sec:GPTT}
\input{GPTT}

\section{GPTT is not  Private}\label{sec:nonprivate}
\input{counterexample}

\section{Reconstructing the data using GPTT}\label{sec:recon}
\input{recon}

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


\newpage
\bibliographystyle{abbrv}



