TC: Small: Theory and Applications of Min-Entropy Leakage

点击翻译按钮获取中文摘要

In this age of identity theft, Facebook, and TSA screening, protecting confidential information from improper disclosure has emerged as a fundamental issue for trustworthy computing, involving both technical and social dimensions. While it is sometimes possible to stop undesirable information flows completely, it is perhaps more typical that some undesirable flows are unavoidable. For instance an ATM machine that rejects an incorrect PIN thereby reveals that the secret PIN is not the one that was entered. Similarly, revealing the tally of votes in an election reveals some information about the secret ballots that were cast. More subtly, the amount of time taken by a cryptographic operation may be observable by an adversary, and may inadvertently reveal information about the secret key. As a result, there is growing interest in quantitative theories of information flow, which allow us to talk about "how much" information is leaked and (perhaps) allow us to tolerate "small" leaks. But while it is tempting to base such theories on classic information-theoretic concepts like Shannon entropy and mutual information, these turn out not to provide very satisfactory confidentiality guarantees. As a result, several researchers have developed an alternative theory, based instead on Renyi's min-entropy, which gives strong, direct operational security guarantees.This project aims to deepen our understanding of the theory and applications of min-entropy leakage by pursuing several themes concurrently. In the theory of min-entropy leakage, uncertainty is measured in terms of a random variable's vulnerability to being guessed in one try by an adversary; note that this is the complement of the Bayes Risk. The mathematical properties of this theory will be explored for both deterministic and probabilistic systems, with the goal of better understanding the relationship to other theories, such as mutual information leakage and differential privacy. A variant called smooth min-entropy leakage will be developed, giving a measure that is less sensitive to extremely unlikely events. To support the compositional analysis of complex systems, leakage bounds will be established for channels in cascade, where the output of one channel becomes the input to another; moreover, algorithms will be developed for approximately factoring a channel into a cascade, giving a technique for automatic sanitization. Techniques will be developed for computing the min-entropy leakage of systems, giving a way to verify whether they conform to a given quantitative flow policy; both model-checking and statistical-sampling based techniques will be considered. Finally, applications of min-entropy leakage will be explored, for example to accountability systems that use logging and auditing to identify misbehaving entities. These efforts will develop new theory, enforcement techniques, and applications of min-entropy leakage, contributing broadly to a rigorous science of quantitative information flow.