# Refinement Orders for Quantitative Information Flow and Differential Privacy +
###### Abstract
Average-case and max-case are different principles, suitable for different scenarios: the former represents the point of view of an organization, for instance an insurance company providing coverage for risks related to credit cards, which for the cost-benefit analysis is interested in reasoning in terms of expectation (expected cost of an attack). The max-case represents the point of view of an individual, who is interested in limiting the cost of _any_ attack. As such, the max-case seems particularly suitable for the domain of privacy. In this paper, we combine the max-case perspective with the robustness of the QIF approach, and we introduce two refinement orders:  
* \(\sqsubseteq_{\mathbb{Q}}^{\max}\), based on the max-case leakage introduced in [9]. This order takes into account all possible privacy breaches caused by any observable (like in the DP world), but it quantifies over all possible quasi-convex vulnerability functions (in the style of the QIF world). * \(\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}\), based on \(d\)-privacy (like in the DP world), but quantified over all metrics \(d\). To underline the importance of a robust order, let us consider the case of the oblivious mechanisms for differential privacy: These mechanisms are of the form \(K=H\circ f\), where \(f:\mathcal{X}\rightarrow\mathcal{Y}\) is a query, namely a function from datasets in \(\mathcal{X}\) to some answer domain \(\mathcal{Y}\), and \(H\) is a probabilistic mechanism implementing the noise. The idea is that the system first computes the result \(y\in\mathcal{Y}\) of the query (_true answer_), and then it applies \(H\) to \(y\) to obtain a _reported answer_\(z\). In general, if we want \(K\) to be \(\varepsilon\)-DP, we need to tune the mechanism \(H\) in order to take into account the _sensitivity_ of \(f\), which is the maximum distance between the results of \(f\) on two adjacent databases, and as such it depends on the metric on \(\mathcal{Y}\). However, if we know that \(K=H\circ f\) is \(\varepsilon\)-DP, and that \(H\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}H^{\prime}\) for some other mechanism \(H^{\prime}\), then we can safely substitute \(H\) by \(H^{\prime}\) as it is because one of our results (cf. Theorem A5) guarantees that \(K^{\prime}=H^{\prime}\circ f\) is also \(\varepsilon\)-DP. In other words, \(H\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}H^{\prime}\) implies that we can substitute \(H\) by \(H^{\prime}\) in an oblivious mechanism for whatever query \(f\) and whatever metric on \(\mathcal{Y}\), without the need to know the sensitivity of \(f\) and without the need to do any tuning of \(H^{\prime}\). Thanks to Theorems 3 and 4, we know that this is the case also for \(\sqsubseteq_{\mathbb{G}}^{\mathrm{avg}}\) and \(\sqsubseteq_{\mathbb{Q}}^{\max}\). We illustrate this with the following example. **Example 3**. : _Consider datasets \(x\in\mathcal{X}\) of records containing the age of people, expressed as natural numbers from \(0\) to \(100\), and assume that each dataset in \(\mathcal{X}\) contains at least \(100\) records. Consider two queries, \(f(x)\) and \(g(x)\), which give the rounded average age and the minimum age of the people in \(x\), respectively. Finally, consider the truncated geometric mechanism \(TG^{\varepsilon}\) (cf. Definition 10), and the randomized response mechanism \(R^{\varepsilon}\) (cf. Definition 13). It is easy to see that \(K_{1}=TG^{\varepsilon}\circ f\) is \(\varepsilon\)-DP, and it is possible to prove that \(TG^{\varepsilon}\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}R^{\varepsilon}\) (cf. Theorem 14). We can then conclude that \(K_{2}=R^{\varepsilon}\circ f\) is \(\varepsilon\)-DP as well, and that in general it is safe to replace \(TG^{\varepsilon}\) by \(R^{\varepsilon}\) for whatever query. On the other hand, \(R^{\varepsilon}\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}TG^{\varepsilon}\), so we cannot expect that it is safe to replace \(R^{\varepsilon}\) by \(TG^{\varepsilon}\) in any context.