Joint work with Andre Scedrov and Fred B. Schneider

Abstract:

---------

Quantitative information flow (QIF) is concerned with measuring how much information about a system's secrets is being leaked to an adversary. The adversary is presumed to have a priori information about the secrets before execution starts and to access public obervables as execution proceeds. By combining a priori information and public observables, the adversary achieves a posteiori information about the secrets. The leakage from an execution is then computed either (i) as the difference between a posteriori information and a priori information or, equivalently, (ii) as the difference between a priori uncertainty and a posteriori uncertainty (since knowledge of information is the dual of uncertainty).

Approaches to QIF traditionally have presumed that all leaks involving a given number of bits are equally harmful. The presumption is unrealistic, so we describe a new approach to QIF. Here, secrets are defined in terms of fields, where derived secrets obtained by combining these fields can be assigned a different worth (perhaps in proportion to the harm that would result from disclosure). New measures that incorporate worth into QIF are then defined; they generalize probability of guessing, guessing entropy, and Shannon entropy. A lattice of information is derived to provide an underlying algebraic structure for an adversary's state of knowledge in this more-general setting.

Finally, we discuss directions to define worth assignments that are soundly based on the the relevant aspects of the scenario of interest. We take particular interest for defining worth assignments for anonymity systems.