Trustworthy Systems

Abstract channels and their robust information-leakage ordering

Authors

Carroll Morgan, Annabelle McIver, Geoffrey Smith, Barbara Espinoza and Larisa Meinicke

NICTA

UNSW

Macquarie University

Abstract

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 that the strong g-leakage ordering is implied by a structural ordering called composition refinement, which requires that A=BC, for some channel C; but the converse was not established in full generality, left open as the so-called Coriaceous Conjecture. Using ideas from our earlier work, we here confirm the Coriaceous Conjecture. Hence the strong g-leakage ordering and composition refinement coincide on abstract channels, giving us a partial order that has both structural and leakage-testing significance.

BibTeX Entry

  @inproceedings{Morgan_MSEM_14,
    address          = {Grenoble, France},
    author           = {Morgan, Carroll and McIver, Annabelle and Smith, Geoffrey and Espinoza, Barbara and Meinicke, Larisa},
    booktitle        = {Principles of Security and Trust (ETAPS)},
    month            = apr,
    pages            = {83--102},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/7522.pdf},
    title            = {Abstract channels and their robust information-leakage ordering},
    year             = {2014}
  }

Download