TY - GEN
T1 - Abstract channels and their robust information-leakage ordering
AU - McIver, Annabelle
AU - Morgan, Carroll
AU - Smith, Geoffrey
AU - Espinoza, Barbara
AU - Meinicke, Larissa
PY - 2014
Y1 - 2014
N2 - The observable output of a probabilistic system that processes a secret input might reveal some information about that input. The system can be modelled as an information-theoretic channel that specifies the probability of each output, given each input. Given a prior distribution on those inputs, entropy-like measures can then quantify the amount of information leakage caused by the channel. But it turns out that the conventional channel representation, as a matrix, contains structure that is redundant with respect to that leakage, such as the labeling of columns, and columns that are scalar multiples of each other. We therefore introduce abstract channels by quotienting over those redundancies. A fundamental question for channels is whether one is worse than another, from a leakage point of view. But it is difficult to answer this question robustly, given the multitude of possible prior distributions and leakage measures. Indeed, there is growing recognition that different leakage measures are appropriate in different circumstances, leading to the recently proposed g-leakage measures, which use gain functions g to model the operational scenario in which a channel operates: the strong g-leakage pre-order requires that channel A never leak more than channel B, for any prior and any gain function. Here we show that, on abstract channels, the strong g-leakage pre-order is antisymmetric, and therefore a partial order. It was previously shown [1] that the strong g-leakage ordering is implied by a structural ordering called composition refinement, which requires that A = BR, for some channel R; but the converse was not established in full generality, left open as the so-called Coriaceous Conjecture. Using ideas from [2], we here confirm the Coriaceous Conjecture. Hence the strong g-leakage ordering and composition refinement coincide, giving our partial order both structural- and leakage-testing significance.
AB - The observable output of a probabilistic system that processes a secret input might reveal some information about that input. The system can be modelled as an information-theoretic channel that specifies the probability of each output, given each input. Given a prior distribution on those inputs, entropy-like measures can then quantify the amount of information leakage caused by the channel. But it turns out that the conventional channel representation, as a matrix, contains structure that is redundant with respect to that leakage, such as the labeling of columns, and columns that are scalar multiples of each other. We therefore introduce abstract channels by quotienting over those redundancies. A fundamental question for channels is whether one is worse than another, from a leakage point of view. But it is difficult to answer this question robustly, given the multitude of possible prior distributions and leakage measures. Indeed, there is growing recognition that different leakage measures are appropriate in different circumstances, leading to the recently proposed g-leakage measures, which use gain functions g to model the operational scenario in which a channel operates: the strong g-leakage pre-order requires that channel A never leak more than channel B, for any prior and any gain function. Here we show that, on abstract channels, the strong g-leakage pre-order is antisymmetric, and therefore a partial order. It was previously shown [1] that the strong g-leakage ordering is implied by a structural ordering called composition refinement, which requires that A = BR, for some channel R; but the converse was not established in full generality, left open as the so-called Coriaceous Conjecture. Using ideas from [2], we here confirm the Coriaceous Conjecture. Hence the strong g-leakage ordering and composition refinement coincide, giving our partial order both structural- and leakage-testing significance.
UR - http://www.scopus.com/inward/record.url?scp=84900525566&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-54792-8_5
DO - 10.1007/978-3-642-54792-8_5
M3 - Conference proceeding contribution
AN - SCOPUS:84900525566
SN - 9783642547911
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 83
EP - 102
BT - Principles of Security and Trust - Third International Conference, POST 2014, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, Proceedings
A2 - Abadi, Martín
A2 - Kremer, Steve
PB - Springer, Springer Nature
CY - Heidelberg
T2 - 3rd International Conference on Principles of Security and Trust, POST 2014 - Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014
Y2 - 5 April 2014 through 13 April 2014
ER -