Quantifying vulnerability of secret generation using hyper-distributions.
Mario Alvim, Piotr Mardziel, Michael Hicks.
In Proceedings of the Principles of Security and Trust (POST). April 2017.


Mario Alvim
Piotr Mardziel
Michael Hicks

Traditional approaches to Quantitative Information Flow (QIF) represent the adversary's prior knowledge of possible secret values as a single probability distribution. This representation may miss important structure. For instance, representing prior knowledge about passwords of a system's users in this way overlooks the fact that many users generate passwords using some \emph{strategy}. Knowledge of such strategies can help the adversary in guessing a secret, so ignoring them may underestimate the secret's vulnerability. In this paper we explicitly model strategies as distributions on secrets, and generalize the representation of the adversary's prior knowledge from a distribution on secrets to an \emph{environment}, which is a distribution on strategies (and, thus, a distribution on distributions on secrets, called a \emph{hyper-distribution}). By applying information-theoretic techniques to environments we derive several meaningful generalizations of the traditional approach to QIF. In particular, we disentangle the \emph{vulnerability of a secret} from the \emph{vulnerability of the strategies} that generate secrets, and thereby distinguish \emph{\aggrsecurity}---which relies on the uncertainty over strategies---from \emph{\realsecurity}---which relies on the intrinsic uncertainty within a strategy. We also demonstrate that, in a precise way, no further generalization of prior knowledge (e.g., by using distributions of even higher order) is needed to soundly quantify the vulnerability of the secret.
  title = {Quantifying vulnerability of secret generation using hyper-distributions},
  author = {Mario Alvim and Piotr Mardziel and Michael Hicks},
  booktitle = {Proceedings of the Principles of Security and Trust (POST)},
  year = {2017},
  month = {April},
  url = {http://www.dcc.ufmg.br/~msalvim/publications/2017-POST.pdf},