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

在这个身份盗窃、Facebook和TSA筛选的时代，保护机密信息不被不当泄露已经成为可信计算的一个基本问题，涉及技术和社会两个维度。虽然有时完全阻止不受欢迎的信息流是可能的，但更典型的情况是，一些不受欢迎的信息流是不可避免的。例如，ATM机拒绝了不正确的PIN，从而揭示了秘密PIN不是输入的那个。同样，披露选举中的计票结果也揭示了一些有关所投无记名选票的信息。更微妙的是，加密操作所花费的时间可能是对手可以观察到的，并且可能无意中泄露关于秘密密钥的信息。因此，人们对信息流的量化理论越来越感兴趣，它使我们能够谈论“有多少”信息被泄露，并(也许)允许我们容忍“微小”的泄露。但是，尽管这样的理论很容易建立在香农熵和互信息等经典信息论概念的基础上，但事实证明，这些概念并不能提供非常令人满意的保密保证。因此，几位研究人员提出了一种替代理论，该理论基于Renyi的最小熵，它提供了强有力的、直接的操作安全保障。该项目旨在通过同时追求几个主题来加深我们对最小熵泄漏理论和应用的理解。在最小熵泄漏理论中，不确定性是根据随机变量在一次尝试中被对手猜测的脆弱性来衡量的；请注意，这是贝叶斯风险的补充。这一理论的数学性质将在确定性和概率系统中进行探索，目的是更好地理解与其他理论的关系，如相互信息泄漏和差异隐私。将开发一种称为平滑最小熵泄漏的变种，给出一种对极不可能发生的事件不那么敏感的衡量标准。为了支持复杂系统的成分分析，将为级联中的通道建立泄漏界限，其中一个通道的输出将成为另一个通道的输入；此外，将开发出将通道近似分解为级联的算法，从而提供自动消毒技术。将开发计算系统最小熵泄漏的技术，提供一种验证它们是否符合给定定量流动策略的方法；将考虑基于模型检查和统计抽样的技术。最后，将探索最小熵泄漏的应用，例如，在使用日志记录和审计来识别行为不端实体的问责系统中。这些努力将发展最小熵泄漏的新理论、实施技术和应用，为定量信息流的严谨科学做出广泛贡献。

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.