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.

Topics:

Mario Alvim
(UFMG)
Piotr Mardziel
(CMU)
Michael Hicks
(UMD)

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.
@inproceedings{alvim2017quantifying,
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},
}