# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## 2 Average-Case Refinement
### Vulnerability, Channels, and Leakage  
Quantitative Information Flow studies the problem of quantifying the _information leakage_ of a system (e.g., a program, or an anonymity protocol). A common model in this area is to consider that the user has a secret \(x\) from a finite set of possible secrets \(\mathcal{X}\), about which the adversary has some probabilistic knowledge \(\pi\colon\mathbb{D}\mathcal{X}\) (\(\mathbb{D}\mathcal{X}\) denoting the set of probability distributions over \(\mathcal{X}\)). A function \(V\colon\mathbb{D}\mathcal{X}\to\mathbb{R}_{\geq 0}\) is then employed to measure the _vulnerability_ of our system: \(V(\pi)\) quantifies the adversary's success in achieving some desired goal, when his knowledge about the secret is \(\pi\). Various such functions can be defined (e.g., employing well-known notions of entropy), but it quickly becomes apparent that no single vulnerability function is meaningful for all systems. The family of \(g\)-vulnerabilities [6] tries to address this issue by parametrizing \(V\) in an operational scenario: first, the adversary is assumed to possess a set of _actions_\(\mathcal{W}\); second, a gain function \(g(w,x)\) models the adversary's gain when choosing action \(w\) and the real secret is \(x\). \(g\)-vulnerability can be then defined as the expected gain of an optimal guess: \(V_{g}(\pi)=\max_{w:\,\mathcal{W}}\sum_{x:\,\mathcal{X}}\pi_{x}g(w,x)\). Different adversaries can be modelled by proper choices of \(\mathcal{W}\) and \(g\). We denote by \(\mathbb{G}\mathcal{X}\) the set of all gain functions. A system is then modelled as a _channel_: a probabilistic mapping from the (finite) set of secrets \(\mathcal{X}\) to a finite set of observations \(\mathcal{Y}\), described by a stochastic matrix \(C\), where \(C_{x,y}\) is the probability that secret \(x\) produces the observation \(y\). When the adversary observes \(y\), he can transform his initial \begin{table}
\begin{tabular}{c c} \hline \hline \multicolumn{1}{c}{Defn} & Vulnerabilities \\ \hline Equation (4) & \(V[\pi,C]:=\ \sum_{y}a_{y}V(\delta^{y})\) \\ Section 3 & \(V^{\max}[\pi,C]:=\ \max_{y}V(\delta^{y})\) \\ Definition 8 & \(V_{d}(\pi):=\ \inf\{\varepsilon\geq 0\mid\forall x,x^{\prime}\in\mathcal{X},\ \pi_{x}\leq e^{ \varepsilon\cdot d(x,x^{\prime})}\pi_{x^{\prime}}\}\) \\ \hline \multicolumn{1}{c}{Defn} & Leakage Measures \\ \hline Definition 4 & \(\operatorname{Priv}_{d}(C):=\ \inf\{\varepsilon\geq 0\mid C\text{ satisfies }\varepsilon\cdot d \text{-privacy}\}\) \\ Equation (23) & \(\mathcal{L}_{d}^{+,\max}(\pi,C):=\ V_{d}^{\max}[\pi,C]-V_{d}(\pi)\) \\ Equation (24) & \(\mathcal{ML}_{d}^{+,\max}(C):=\ \max_{\pi}\mathcal{L}_{d}^{+,\max}(\pi,C)\) \\ \hline \multicolumn{1}{c}{Defn} & Refinement Orders \\ \hline Equation (6) & \(A\sqsubseteq^{\text{avg}}B\) iff \(AR=B\) for some channel \(R\) \\ Definition 2 & \(A\sqsubseteq^{\text{max}}B\) iff \(R\tilde{A}=\tilde{B}\) for some channel \(R\) \\ Definition 7 & \(A\sqsubseteq^{\text{prev}}B\) iff \(B\) satisfies \(d_{A}\)-privacy \\ \hline \multicolumn{1}{c}{Defn} & Leakage Orders \\ \hline Section 2.2 & \(A\sqsubseteq^{\text{avg}}_{\mathbb{G}}B\) iff \(\forall g\colon\mathbb{G}\mathcal{X},\forall\pi\colon\mathbb{D}\mathcal{X},\ \forall g [\pi,A]\geq V_{g}[\pi,B]\) \\ Definition 1 & \(A\sqsubseteq^{\text{max}}_{\mathbb{Q}}B\) iff \(\forall V\colon\mathbb{Q}\mathcal{X},\forall\pi\colon\mathbb{D}\mathcal{X},\ \forall ^{\max}[\pi,A]\ \geq V^{\max}[\pi,B]\) \\ Definition 6 & \(A\sqsubseteq^{\text{prev}}_{\mathbb{M}}B\) iff \(\forall d\in\mathbb{M}\mathcal{X},\ A\sqsubseteq^{\text{prev}}_{d}B\) \\ Definition 5 & \(A\sqsubseteq^{\text{prev}}_{d}B\) iff \(\operatorname{Priv}_{d}(A)\geq\operatorname{Priv}_{d}(B)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Definitions and symbols used in this paper. knowledge \(\pi\) into a _posterior_ knowledge \(\delta^{y}\colon\mathbb{D}\mathcal{X}\).