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.