# Refinement Orders for Quantitative Information Flow and Differential Privacy +
###### Abstract
In fact, \(K_{3}=R^{\varepsilon}\circ g\) is \(\varepsilon\)-DP, but \(K_{4}=TG^{\varepsilon}\circ g\) is not \(\varepsilon\)-DP, despite the fact that both mechanisms are constructed using the same privacy parameter \(\varepsilon\). Hence, we can conclude that a refinement relation based only on the comparison of the \(\varepsilon\) parameters would not be robust, at least not for a direct replacement in an arbitrary context. Note that \(K_{4}\) is \(100\times\varepsilon\)-DP. In order to make it \(\varepsilon\)-DP, we should divide the parameter \(\varepsilon\) by the sensitivity of \(g\) (with respect to the ordinary distance on natural numbers), which is \(100\), i.e., use \(TG^{\varepsilon/100}\). For \(R^{\varepsilon}\), this is not necessary because it is defined using the discrete metric on \(\{0,\ldots,100\}\), and the sensitivity of \(g\) with respect to this metric is \(1\)._The robust orders allow us to take into account different kinds of adversaries. The following example shows what the idea is. **Example 4**. : _Consider the following three LDP mechanisms, represented by their stochastic matrices (where each element is the conditional probability of the outcome of the mechanism, given the secret value). The secrets are three possible economic situations of an individual, \(p\), \(a\) and \(r\), standing for \"poor\", \"average\" and \"rich\", respectively. The observable outcomes are \(r\) and \(n\), standing for \"rich\" and \"not rich\"._  
\[ \begin{array}{|c|c|}\hline A&n&r\\ \hline p&3/4&1/4\\ a&1/2&1/2\\ r&1/4&3/4\\ \hline\end{array} \quad \begin{array}{|c|c|}\hline B&n&r\\ \hline p&2/3&1/3\\ a&2/3&1/3\\ r&1/3&2/3\\ \hline\end{array} \quad \begin{array}{|c|c|}\hline C&n&r\\ \hline p&2/3&1/3\\ a&1/2&1/2\\ r&1/3&2/3\\ \hline\end{array}  \tag{3}\]  
_Let us assume that the prior distribution \(\pi\) on the secrets is uniform. We note that \(A\) is \((\log 3)\)-LDP while \(B\) is \((\log 2)\)-LDP. Hence, if we only look at the value of \(\varepsilon\), we would think that \(B\) is better than \(A\) from the privacy point of view. However, there are attackers that gain more from \(B\) than from \(A\) (which means that, with respect to those attackers, the privacy of \(B\) is worse). For instance, this is the case when the attacker is only interested in discovering whether the person is rich or not. In fact, if we consider a gain \(1\) when the attacker guesses the right class (\(r\) versus (either \(p\) or \(a\))) and \(0\) otherwise, we have that the highest possible gain in \(A\) is \((3/4)\,\pi(p)+(1/2)\,\pi(a)=5/12\), while in \(B\) is \((2/3)\,\pi(p)+(2/3)\,\pi(a)=4/9\), which is higher than \(5/12\). This is consistent with our orders: it is possible to show that none of the three orders hold between \(A\) and \(B\), and that therefore we should not expect \(B\) to be better (for privacy) than \(A\) with respect to all possible adversaries._  
_On the other hand, the mechanism \(C\) is also \((\log 2)\)-LDP, and in this case we have that the relation \(A\sqsubseteq^{\max}_{\mathbb{Q}}C\) holds, implying that we can safely replace \(A\) by \(C\). We can also prove that the reverse does not hold, which means that \(C\) is strictly better than \(A\)._  
A fundamental issue is how to prove that these robust orders hold: Since \(\sqsubseteq^{\max}_{\mathbb{Q}}\) and \(\sqsubseteq^{\text{prv}}_{\mathbb{M}}\) involve universal quantifications, it is important to devise finitary methods to verify them. To this purpose, we will study their characterizations as structural relations between stochastic matrices (representing the mechanisms to be compared), along the lines of what was done for \(\sqsubseteq^{\text{avg}}_{\mathbb{G}}\). We will also study the relation between the three orders (the two above and \(\sqsubseteq^{\text{avg}}_{\mathbb{G}}\)), and their algebraic properties. Finally, we will analyze various mechanisms for DP, LDP, and \(d\)-privacy to see in which cases the order induced by \(\varepsilon\) is consistent with the three orders above.