# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## 4 Privacy-Based Refinement
### Privacy-Based Leakage and Refinement Orders  
When discussing the average- and max-case leakage orders \(\sqsubseteq_{G}^{\mathrm{avg}},\sqsubseteq_{\mathbb{Q}}^{\mathrm{max}}\), we obtained strong leakage guarantees by quantifying over _all vulnerability functions_. It is thus natural to investigate a similar quantification in the context of \(d\)-privacy. Namely, we define a stronger privacy-based \"leakage\" order, by comparing mechanisms not on a single metric \(d\), but on _all metrics_ simultaneously.  
**Definition 6**.: _The privacy-based leakage order is defined as \(A\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}B\) iff \(A\sqsubseteq_{d}^{\mathrm{prv}}B\) for all \(d\in\mathbb{M}\mathcal{X}\)._  
Similarly to the other leakage orders, the drawback of \(\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}\) is that it quantifies over an uncountable family of metrics. As a consequence, our first goal is to characterize it as a property of the channel matrix alone, which would make it much easier to reason about or verify.  
To do so, we start by recalling an alternative way of thinking about \(d\)-privacy. Consider the _multiplicative total variation_ distance between probability distributions \(\mu,\mu^{\prime}\in\mathbb{D}\mathcal{Y}\), defined as:  
\[\mathrm{tv}_{\otimes}(\mu,\mu^{\prime})\ \ :=\ \ \max_{y:\mathcal{Y}}|\ln\frac{\mu_{y}}{ \mu_{y}^{\prime}}| \tag{19}\]  
If we think of \(C\) as a function \(\mathcal{X}\to\mathbb{D}\mathcal{Y}\) (mapping every \(x\) to the distribution \(C_{x,-}\)), \(C\) satisfies \(d\)-privacy iff \(\mathrm{tv}_{\otimes}(C_{x,-},C_{x^{\prime},-})\leq d(x,x^{\prime})\), in other words iff \(C\) is non-expansive (1-Lipschitz) wrt \(\mathrm{tv}_{\otimes},d\).  
Then, we introduce the concept of the _distinguishability metric \(d_{C}\in\mathbb{M}\mathcal{X}\) induced by_ the channel \(C\), defined as  
\[d_{C}(x,x^{\prime})\ \ :=\ \ \mathrm{tv}_{\otimes}(C_{x,-},C_{x^{\prime},-}) \tag{20}\]  
Intuitively, \(d_{C}(x,x^{\prime})\) expresses exactly how much the channel distinguishes (wrt \(\mathrm{tv}_{\otimes}\)) the secrets \(x,x^{\prime}\). It is easy to see that \(d_{C}\) is the _smallest metric_ for which \(C\) is private; in other words, for any \(d\):  
\[C\ \text{satisfies $d$-privacy}\qquad\text{iff}\qquad d\geq d_{C} \tag{21}\]  
We can now give a refinement order on mechanisms, by comparing their corresponding induced metrics.  
**Definition 7**.: _The privacy-based refinement order is defined as \(A\sqsubseteq^{\mathrm{prv}}B\) iff \(d_{A}\geq d_{B}\), or equivalently iff \(B\) satisfies \(d_{A}\)-privacy._  
This achieves our goal of goal of characterizing \(\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}\).  
**Proposition 1**.: _The orders \(\sqsubseteq_{\mathbb{M}}^{\mathrm{prv}}\) and \(\sqsubseteq^{\mathrm{prv}}\) coincide._  
We now turn our attention to the question of how these orders relate to each other.  
**Theorem 4**.: \(\sqsubseteq^{\mathrm{max}}\) _is strictly stronger than \(\sqsubseteq^{\mathrm{prv}}\), which is strictly stronger than \(\sqsubseteq_{d}^{\mathrm{prv}}\)._  
The fact that \(\sqsubseteq^{\mathrm{max}}\) is stronger than \(\sqsubseteq^{\mathrm{prv}}\) is due to the fact than \(\mathrm{Priv}_{d}\) can be seen as a max-case information leakage, for a properly constructed vulnerability function \(V_{d}\). This is discussed in detail in Section 4.7. This implication means that \(\sqsubseteq^{\mathrm{avg}},\sqsubseteq^{\mathrm{max}}\) can be useful even if we \"only\" care about \(d\)-privacy.