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.