2014 | OriginalPaper | Chapter
On Formally Bounding Information Leakage by Statistical Estimation
Authors : Michele Boreale, Michela Paolini
Published in: Information Security
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the problem of giving formal bounds on the information leakage of deterministic programs, when only a black-box access to the system is provided, and little is known about the input generation mechanism. After introducing a statistical set-up and defining a formal notion of information leakage
estimator
, we prove that, in the absence of significant a priori information about the output distribution, no such estimator can in fact exist that does significantly better than exhaustive enumeration of the input domain. Moreover, we show that the difficult part is essentially obtaining tight
upper
bounds. This motivates us to consider a relaxed scenario, where the analyst is given some control over the input distribution: an estimator is introduced that, with high probability, gives lower bounds irrespective of the underlying distribution, and tight upper bounds if the input distribution induces a “close to uniform” output distribution. We then define two methods, one based on Metropolis Monte Carlo and one based on Accept-Reject, that can ideally be employed to sample from one such input distribution, and discuss a practical methodology based on them. We finally demonstrate the proposed methodology with a few experiments, including an analysis of cache side-channels in sorting algorithms.