EAGER: Collaborative: Quantifying Information Leakage in Searchable Encryption

随着越来越多的企业和组织将大量数据存储在云服务器上，云存储目前正在经历爆炸式增长。加密这些数据提供了针对不可信服务器或恶意入侵的安全性。然而，标准加密具有损害功能和效率的缺点，并且它是如此强大以至于其密文不可搜索。出于这个原因，可搜索加密（SE）已成为一个重要的研究领域，旨在提供较弱的加密形式，以平衡安全性，效率和功能目标。SE方案已经部署在像CryptDB这样的实际系统中，并且对更多这样的解决方案有强烈的需求。然而，最近公布的高调攻击引发了人们对此类系统是否可以安全使用的质疑。更一般地说，事实证明，很难理解在实践中使用SE的安全含义。该项目旨在澄清目前相当具有挑战性的情况，寻求分析和量化在实践中各种SE方案下可能发生的敏感信息泄漏量，从而为密码学家和从业者提供关于何时以及如何安全使用这些方案的指导。该项目的方法是跨学科的，将密码方案的可证明安全性分析与定量信息流（QIF）理论相结合，建立在各自领域的主要研究人员的专业知识基础上。一个技术上的挑战是，在可证明安全中考虑的对手是计算上有界的，而在QIF中考虑的是信息论。然而，SE方案的安全性通常被公式化为来自“理想对象”的计算不可扩展性，该理想对象可以被建模为信息理论信道，并且其泄漏可以使用QIF技术来分析。特别是，信道容量的概念允许建立最坏情况下的信息泄漏的界限，因为细化是一个偏序，它是可能的，以表明一个SE计划永远不会泄漏比另一个，无论对手的先验知识或目标。该项目旨在对一些相关的SE方案进行此类分析，包括确定性加密和保序加密。目标是建立新的加密基础和度量标准，用于测量和比较不同可搜索加密方案及其使用的安全性。

Cloud storage is currently experiencing explosive growth as more and more businesses and organizations store large amounts of data on cloud servers. Encrypting such data provides security against untrusted servers or malicious intrusions. However, standard encryption has the drawback of compromising functionality and efficiency and it is so strong that its ciphertexts are not searchable. For this reason, searchable encryption (SE) has become an important research area, aimed at providing weaker forms of encryption that balance security, efficiency, and functionality goals. SE schemes have already been deployed in practical systems like CryptDB and there is strong demand for more such solutions. However, recently published high-profile attacks call into question whether such systems can in fact be used safely. More generally speaking, it has proven very difficult to understand the security implications of using SE in practice. This project aims to bring clarity to the current rather challenging situation seeking to analyze and quantify the amount of leakage of sensitive information that can occur under various SE schemes in practice, thereby offering guidance to both cryptographers and practitioners about when and how such schemes can be used safely.The approach of this project is interdisciplinary, coupling the provable security analysis of cryptographic schemes with quantitative information flow (QIF) theory, building on the expertise of the principal investigators in their respective areas. A technical challenge is that the adversaries considered in provable security are computationally bounded, while those considered in QIF are information theoretic. Yet, the security of an SE scheme is often formulated as computational indistinguishability from an "ideal object" which can be modeled as an information-theoretic channel, and whose leakage can then be analyzed using QIF techniques. In particular, notions of channel capacity allow worst-case bounds on information leakage to be established, and since refinement is a partial order it is possible to show that one SE scheme never leaks more than another, regardless of the adversary's prior knowledge or goals. The project seeks to carry out such analyses on a number of pertinent SE schemes, including deterministic encryption and order-preserving encryption. The goal is to establish new cryptographic foundations and metrics for measuring and comparing the security of different searchable encryption schemes and their usage.