1 files changed, 33 insertions, 0 deletions
diff --git a/ACSAC/proofs/proof_egd_dp.tex b/ACSAC/proofs/proof_egd_dp.tex
new file mode 100644
index 0000000..d0f23f6
--- /dev/null
+++ b/ACSAC/proofs/proof_egd_dp.tex
@@ -0,0 +1,33 @@
+\begin{theorem}
+\label{th:dpgood}
+Maximum attack accuracy achievable by \aia in \ref{tm:hard} is equal to $\frac{1}{2}(1+\text{\demparlevel of }\targetmodel)$. 
+\end{theorem}
+\begin{proof}
+The set $B$ of function from $\{0,1\}$ to $\{0,1\}$ contains four elements: $b_0=0$, $b_1=id$, $b_2=1-id$ and $b,3=1$, where $\forall x, id(x) = x$.
+For every $b\in B$ the balanced \aia accuracy is 
+$BA(b) = \frac{1}{2}(P(b\circ \hat{Y}=0|S=0) + P(b\circ \hat{Y}=1|S=1))$.
+We have $BA(b_0) = BA(b_3) = \frac{1}{2}$, hence, we can discard those elements when solving the attack optimisation problem.
+This problem writes $\text{max}_{b\in B}B(A(b)) = \text{max}(BA(b_1), BA(b_2))$.
+We remark that $b_1\circ \hat{Y}=\hat{Y}$ and $b_2\circ \hat{Y}=1 - \hat{Y}$.
+Hence,
+{\footnotesize
+\begin{align*}
+    BA(b_1) &= \frac{1}{2}(P(\hat{Y}=0|S=0) + P(\hat{Y}=1|S=1))\\
+    &=\frac{1}{2}(1+P(\hat{Y}=1|S=1) - P(\hat{Y}=1|S=0))\\
+    BA(b_2)&=\frac{1}{2}(1+P(\hat{Y}=1|S=0) - P(\hat{Y}=1|S=1))
+\end{align*}
+}
+Thus,
+{\footnotesize
+\begin{align*}
+    &\text{max}_{b\in B}BA(b) 
+    = \frac{1}{2}\left(1+\text{max}\left(
+    \begin{matrix}
+        P(\hat{Y}=0|S=0) -P(\hat{Y}=1|S=1)\\ 
+        P(\hat{Y}=1|S=0) -P(\hat{Y}=0|S=1)
+    \end{matrix}
+    \right)\right)\\
+    =&\frac{1}{2}(1+|P(\hat{Y}=1|S=1) - P(\hat{Y}=1|S=0)|)
+\end{align*}
+}
+\end{proof}