Additive and multiplicative notions of leakage, and their capacities

ABSTRACT. Protecting sensitive information from improper disclosure is a fundamental security goal. It is complicated, and difficult to achieve, often because of unavoidable or even unpredictable operating conditions that lead to breaches in planned security defences. An attractive approach is to frame the goal as a quantitative problem, and then to design methods that allow system vulnerabilities to be measured in terms of the amount of information that they leak. A consequence of this view is that the precise operating conditions and any assumptions about prior knowledge can play a crucial role in assessing the severity of any measured vunerability.

We develop this theme by concentrating on robustness of vulnerability measurements: we wish to allow general leakage bounds to be placed on a program, whatever its operating conditions and whatever the prior knowledge might be. In particular we propose a theory of channel capacity, generalizing Shannon capacity from information theory, that can apply both to additive- and to multiplicative forms of a recently-proposed measure known as g-leakage. Further, we explore the computational aspects of calculating these capacities: we show that one of these scenarios can be solved efficiently by expressing it as a Kantorovich distance, and that another is NP-complete. We also show capacity bounds for a scenario related to Dalenius's Desideratum.