# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## 4 Privacy-Based Refinement
### Privacy as Max-Case Capacity  
In this section we show that \(d\)-privacy can be expressed as a (max-case) information leakage. Note that this provides an alternative proof that \(\sqsubseteq^{\max}\) is stronger than \(\sqsubseteq^{\text{prv}}\). We start this by defining a suitable vulnerability function:  
**Definition 8**. : _The \(d\)-unnerability function \(V_{d}\) is defined as_  
\[V_{d}(\pi) := \inf\{\varepsilon\geq 0\mid\forall x,x^{\prime}\in\mathcal{X},\pi_ {x}\leq e^{\varepsilon\cdot d(x,x^{\prime})}\pi_{x^{\prime}}\} \tag{22}\]  
Note the difference between \(V_{d}(\pi)\) (a vulnerability function on _distributions_) and \(\text{Priv}_{d}(C)\) (a \"leakage\" measure on _channels_). A fundamental notion in QIF is that of _capacity_: the maximization of leakage over all priors. In turns out that, for \(V_{d}\), the capacity-realizing prior is the uniform one. In the following, \(\mathcal{L}_{d}^{+,\max}\) denotes the additive max-case \(d\) leakage, namely:  
\[\mathcal{L}_{d}^{+,\max}(\pi,C)=V_{d}^{\max}[\pi,C]-V_{d}(\pi) \tag{23}\]  
and \(\mathcal{M}\mathcal{L}_{d}^{+,\max}\) denotes the additive max-case \(d\)-capacity, namely:  
\[\mathcal{M}\mathcal{L}_{d}^{+,\max}(C)=\max_{\pi}\mathcal{L}_{d}^{+,\max}(\pi,C) \tag{24}\] \begin{table}
\begin{tabular}{c c c} \hline \hline
**Leakage Orders** & \multicolumn{2}{c}{**Refinement Orders**} \\ \hline \(\sqsubseteq^{\text{avg}}_{G}\) & \(\Leftrightarrow\) & \(\sqsubseteq^{\text{avg}}_{G}\) \\ \(\sqsubseteq^{\text{max}}_{G}\) & \(\Leftrightarrow\) & \(\sqsubseteq^{\text{max}}_{G}\) \\ \(\sqsubseteq^{\text{prv}}_{M}\) & \(\Leftrightarrow\) & \(\sqsubseteq^{\text{prv}}\) \\ \(\sqsubseteq_{A}\) & \(\sqsubseteq^{\text{prv}}_{d}\) & \(\
less\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison of leakage and refinement orders. All implications are strict. **Theorem 6**. : \({\cal ML}^{+,{\rm max}}_{d}\) _is always achieved on a uniform prior \(\pi^{u}\). Namely_  
\[\max_{\pi}{\cal L}^{+,{\rm max}}_{d}(\pi,C) = {\cal L}^{+,{\rm max}}_{d}(\pi^{u},C) = V^{\rm max}_{d}[\pi^{u},C] \tag{25}\]  
This finally brings us to our goal of expressing \({\rm Priv}_{d}\) in terms of information leakage (for a proper vulnerability function). **Theorem 7**. : _[DP as max-case capacity] \(C\) satisfies \(\varepsilon\cdot d\)-privacy iff \({\cal ML}^{+,{\rm max}}_{d}(C)\leq\varepsilon\). In other words: \({\cal ML}^{+,{\rm max}}_{d}(C)={\rm Priv}_{d}(C)\)._  
**5. Verifying the Refinement Orders**  
We now turn our attention to the problem of checking whether the various orders hold, given two _explicit representations_ of channels \(A\) and \(B\) (in terms of their matrices). We show that, for all orders, this question can be answered in time polynomial in the size of the matrices. Moreover, when one of the order fails, we discuss how to obtain a _counter-example_ (e.g., a gain function \(g\) or a vulnerability function \(V\)), demonstrating this fact. All the methods discussed in the section have been implemented in a publicly available library, and have been used in the experimental results of Section 6. _5.1. Average-Case Refinement_  
Verifying \(A\sqsubseteq^{\rm avg}B\) can be done in polynomial time (in the size of \(A,B\)) by solving the system of equations \(AR=B\), with variables \(R\), under the linear constraints that \(R\) is a channel matrix (non-negative and rows sum up to 1). However, if the system has no solution (i.e., \(A\sqsubseteq^{\rm avg}B\)), this method does not provide us with a counter-example gain function \(g\). We now show that there is an alternative efficient method: define \(C^{\uparrow}=\{CR\mid R\) is a channel\(\}\), the set of all channels obtainable by post-processing \(C\). The idea is to compute the projection of \(B\) on \(A^{\uparrow}\). Clearly, the projection is \(B\) itself iff \(A\sqsubseteq^{\rm avg}B\); otherwise, the projection can be directly used to construct a counter-example \(g\). **Theorem 8**. : _Let \(B^{*}\) be the projection of \(B\) on \(A^{\uparrow}\)._  
1.