Symmetric searchable encryption with sharing and unsharing

In this paper, we study Symmetric Searchable Encryption (SSE) in a multi-user setting in which each user dynamically shares its documents with selected other users, allowing sharees also to perform searches. We introduce the concept of a Symmetric Searchable Encryption with Sharing and Unsharing, an extension of Multi-Key Searchable Encryption (NSDI ’14), that supports dynamic sharing and unsharing of documents amongst users. We also strengthen the security notion by considering a simulation-based notion that does not restrict sharing between honest and compromised users. We present the notion of cross-user leakage, the information leaked about a user’s documents and/or queries from the queries of other users, and introduce a novel technique to quantify cross-user leakage. Specifically, we model cross-user leakage by using a graph where nodes correspond to users and the presence of edges between two nodes indicates the existence of cross-user leakage between the two adjacent users. The statistics on the connected components of the cross-user leakage graph provide a quantifiable way to compare the leakage of multi-user schemes which has eluded previous works. Our main technical contribution is mx-u, an efficient scheme with small cross-user leakage, whose security is based on the decisional Diffie-Hellman assumption. We prove a tight bound on the leakage of mx-u in the presence of an honest-but-curious adversary that colludes with a non-adaptively chosen subset of users. We report on experiments showing that mx-u is efficient and that cross-user leakage grows slowly as queries are performed.