Refinement relations

qif.refinement

A channel \(B\) refines \(A\), written \(A \sqsubseteq B\), if \(B = AR\) for some channel \(R\), that is if \(B\) can be obtained by post-processing the output of \(A\). Equivalently, \(B\) never leaks more than \(A\): \(V_g[\pi\triangleright A] \ge V_g[\pi\triangleright B]\) for all priors \(\pi\) and gain functions \(g\). This module checks refinement and some variants of it, and measures how much \(B\) can leak more than \(A\) when refinement fails.

Functions

refined_by(A: ndarray, B: ndarray, method: str = 'factorize') → object

Whether \(A \sqsubseteq B\).

With method="factorize" (default), it checks whether \(B = AR\) for some channel \(R\), by linear programming, and returns a bool.

With method="project" (double only), it computes the channel \(R\) minimizing the Euclidean distance between \(AR\) and \(B\) (by quadratic programming), and returns (refined, G, R). If refined is false, G is a counter-example: a gain matrix (with values in \([0,1]\)) such that \(V_G[\vartheta\triangleright A] < V_G[\vartheta\triangleright B]\) for the uniform prior \(\vartheta\). Otherwise G is empty and \(AR = B\).

max_refined_by(A: ndarray, B: ndarray) → bool

Whether \(A\) is refined by \(B\) in the max-case [CFP19]: \(R A^* = B^*\) for some channel \(R\), where \(C^*\) is obtained from \(C\) by normalizing its columns and transposing (its rows are the posteriors of \(C\) under the uniform prior). Equivalently, \(\max_y V(p_{X|y})\) is never larger for \(B\) than for \(A\), for all priors and all continuous quasi-convex vulnerabilities \(V\).

priv_refined_by(A: ndarray, B: ndarray) → bool

Whether \(A\) is refined by \(B\) with respect to privacy [CFP19]: for every metric \(d\), if \(A\) satisfies \(d\)-privacy then so does \(B\). Checked by testing whether \(B\) satisfies \(d_A\)-privacy, where \(d_A(x,x')\) is the multiplicative distance between the rows \(A_{x,-}\) and \(A_{x',-}\) (see d-privacy). Only double is supported.

add_metric(pi: ndarray, A: ndarray, B: ndarray) → Tuple[rat, ndarray]

The additive refinement metric [CS19]: the maximum of \(V_g[\pi\triangleright B] - V_g[\pi\triangleright A]\) over all one-bounded gain functions \(g\) (\(g \le 1\)), that is how much the additive leakage of \(B\) can exceed that of \(A\) on the prior pi. It is \(0\) when \(A \sqsubseteq B\). Computed by linear programming; returns (value, G), where G is a gain matrix achieving the maximum.

add_metric_bound(pi: ndarray, A: ndarray, B: ndarray) → float

An upper bound of add_metric(), cheaper to compute: the Kantorovich distance between the hypers \([\pi\triangleright A]\) and \([\pi\triangleright B]\), with respect to the quasiconvex separation \(q\) between their inners (see qif.metric.convex_separation_quasi()) [CS19].

References

[CFP19]

K. Chatzikokolakis, N. Fernandes, C. Palamidessi. Comparing systems: max-case refinement orders and application to differential privacy. CSF 2019.

[CS19]

K. Chatzikokolakis, G. Smith. Refinement metrics for quantitative information flow. In The Art of Modelling Computational Systems, LNCS 11760, 2019.