Visible to the public EAGER: Collaborative: Quantifying Information Leakage in Searchable EncryptionConflict Detection Enabled

Project Details

Performance Period

Jan 01, 2018 - Jun 30, 2019

Institution(s)

Florida International University

Award Number


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.