# Refinement Orders for Quantitative Information Flow and Differential Privacy +
### Related Work  
We are not aware of many studies on refinement relations for QIF. [PERSON] and [PERSON] [10] and [PERSON] [11] have explored strong orders on _deterministic_ mechanisms, focusing on the fact that such mechanisms induce _partitions_ on the space of secrets. They showed that the orders produced by min-entropy leakage [5] and Shannon leakage [12; 13] are the same and, moreover, they coincide with the _partition refinement_ order in the _Lattice of Information_[14]. This order was extended to the probabilistic case in [6], resulting in the relation \(\sqsubseteq^{\text{avg}}\) mentioned in Section 2. The same paper [6] proposed the theory of \(g\)-leakage and introduced the corresponding order \(\sqsubseteq_{G}^{\text{avg}}\). Furthermore, [6] proved that \(\sqsubseteq^{\text{avg}}\subseteq_{\mathbb{G}}^{\text{avg}}\) and conjectured that also the reverse should hold. This conjecture was then proved valid in [7]. The max-case leakage, on which the relation \(\sqsubseteq_{\mathbb{Q}}^{\text{max}}\) is based, was introduced in [9], but \(\sqsubseteq_{\mathbb{Q}}^{\text{max}}\) and its properties were not investigated. Finally, \(\sqsubseteq^{\text{prv}}\) is a novel notion introduced in this paper.  
In the field of differential privacy, on the other hand, there have been various works aimed at trying understand the operational meaning of the privacy parameter \(\varepsilon\) and at providing guidelines for the choice of its values. We mention, for example [15; 16], which consider the value of \(\varepsilon\) from an economical point of view, in terms of cost. We are not aware, however, of studies aimed at establishing orders between the level of privacy of different mechanisms, except the one based on the comparison of the \(\varepsilon\)'s.  
The relation between QIF and DP, LDP, and \(d\)-privacy is based on the so-called _semantic interpretation_ of the privacy notions that regard these properties as expressing a bounds on the increase of knowledge (from prior to posterior) due to the answer reported by the mechanism. For \(d\)-privacy, the semantic interpretation is expressed by (2). To the best of our knowledge, this interpretation was first pointed out (for the location privacy instance) in [17]. The seminal paper on \(d\)-privacy, [3], also proposed a semantic interpretation, with a rather different flavor, although formally equivalent. As for DP, as explained in the Introduction, (2) instantiated to databases and Hamming distance corresponds to the odds ratio on which the semantics interpretation is based provided in [8]. Before that, another version of semantic interpretation was presented in [1] and proved equivalent to a form of DP called \(\varepsilon\)-indistinguishability. Essentially, in this version, an adversary that queries the database, and knows all the database except one record, cannot infer too much about this record from the answer to the query reported by the mechanism. Later on, an analogous version of semantic interpretation was reformulated in [18] and proved equivalent to DP. A different interpretation of DP, called _semantic privacy_, was proposed by [19]. This interpretation is based on a comparison between two posteriors (rather between the posterior and the prior), and the authors show that, within certain limits, it is equivalent to DP.  
A short version of this paper, containing only some of the proofs, appeared in [20].