Searching secrets rationally

We study quantitative information flow, from the perspective of an analyst who is interested in maximizing its expected gain in the process of learning a secret, or settling a hypothesis, represented by an unobservable X, after observing some Y related to X. In our framework, learning the secret has an associated reward, while the investigation of the set of possibilities prompted by the observation has a cost, proportional to the set’s size. Approaches based on probability coverage, or on trying a fixed number of guesses, are sub-optimal in this framework. Inspired by Bayesian decision theory, we characterize the optimal behavior for the analyst and the corresponding expected gain (payoff) in a variety of situations. We argue about the importance of advantage, defined as the increment in expected gain after the observation if the analyst acts optimally, and representing the value of the information conveyed by Y . We characterize advantage precisely in a number of special but important instances of the framework. Applications to cryptographic systems and to familial DNA searching are examined.