# Refinement Orders for Quantitative Information Flow and Differential Privacy +
###### Abstract
It is important to have a rigorous and effective way to establish whether a mechanism is better or worse than another one, in order to guide the design and the implementation of mechanisms for information protection. This is not always an obvious task. To illustrate the point, consider the following examples. **Example 1**. : _Let \(P_{1},P_{2},P_{3}\) and \(P_{4}\) be the programs illustrated in Table 1, where \(\mathtt{H}\) is a \"high\" (i.e., secret) input and \(\mathtt{L}\) is a \"low\" (i.e., public) output. We assume that \(\mathtt{H}\) is a uniformly distributed \(32\)-bit integer with range \(0\leq\mathtt{H}<2^{32}\). All these programs leak information about \(\mathtt{H}\) via \(\mathtt{L}\), in different ways: \(P_{1}\) reveals \(\mathtt{H}\) whenever it is a multiple of \(8\) (\(\mathtt{H}\mod 8\) represents the integer division of \(\mathtt{H}\) by \(8\)), and reveals nothing otherwise. \(P_{2}\) does the same thing whenever \(\mathtt{H}\) is a multiple of \(4\). \(P_{3}\) reveals the last \(8\) bits of \(\mathtt{H}\) (note that \(\mathtt{H}\ll 0^{24}1^{8}\) represents the bitwise conjunction between \(\mathtt{H}\) and a string of \(24\) bits \"\(0\)\" followed by \(8\) bits \"\(1\)\"). Analogously, \(P_{4}\) reveals the last \(4\) bits of \(\mathtt{H}\). Now, it is clear that \(P_{2}\) leaks more than \(P_{1}\), and that \(P_{4}\) leaks more than \(P_{3}\), but how to compare, for instance, \(P_{1}\), and \(P_{3}\)? It is debatable which one is worse because their behavior is very different: \(P_{1}\) reveals nothing in most cases, but when it does reveal something, it reveals everything. \(P_{3}\), on the other hand, always reveals part of the secret. Clearly, we cannot decide which situation is worse, unless we have some more information about the goals and the capabilities of the attacker. For instance, if the adversary has only one attempt at his disposal (and no extra information), then the program \(P_{3}\) is better because even after the output of \(\mathtt{L}\) there are still \(24\) bits of \(\mathtt{H}\) that are unknown. On the other hand, if the adversary can repeat the attacks on program similar to \(P_{3}\), then eventually it will uncover the secret entirely all the times._ \begin{table}
\begin{tabular}{c c c c} \hline \hline \(P_{1}\) & \(P_{2}\) & \(P_{3}\) & \(P_{4}\) \\ \hline if H mod 8 = 0 then & if H mod 4 = 0 then & \(\mathtt{L}:=\mathtt{H}\ \&\ 0^{24}1^{8}\) & \(\mathtt{L}:=\mathtt{H}\ \&\ 0^{28}1^{4}\) \\  & \(\mathtt{L}:=\mathtt{H}\) & \(\mathtt{L}:=\mathtt{H}\) & \\  & \(\mathtt{else}\) & & \\  & \(\mathtt{L}:=\mathtt{1}\) & \(\mathtt{L}:=\mathtt{1}\) & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Programs that take in input a secret \(\mathtt{H}\) and leak information about \(\mathtt{H}\) via the output \(\mathtt{L}\). **Example 2**. : _Consider the domain of the integer numbers between \(0\) and \(100\), and consider a geometric mechanism (cf. Definition 9) on this domain, with \(\varepsilon=\log^{27}/25\). Then, consider a randomized response mechanism (cf. Definition 13) still on the same domain and \(\varepsilon=\log 2\). The two mechanisms are illustrated in Figure 1. They both satisfy d-privacy, but for different \(d\): in the first case \(d\) is the standard distance between numbers, while in the second case it is the discrete metric. Clearly, it does not make sense to compare these mechanisms on the basis of their respective privacy parameters \(\varepsilon\) because they represent different privacy properties, and it is not obvious how to compare them in general: The geometric mechanism tends to make the true value indistinguishable from his immediate neighbors, but it separates it from the values far away. The randomized response introduces the same level of confusion between the true value and any other value of the domain. Thus, which mechanism is more private depends on the kind of attack we want to mitigate: if the attacker is trying to guess an approximation of the value, then the randomized response is better.