Symmetric Searchable Encryption with Sharing and Unsharing
We study Symmetric Searchable Encryption (SSE) in a multi-user setting in which each user dynamically shares its documents with selected other users, allowing shares also to perform searches. We introduce the concept of an SSE 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.
The main technical contribution is 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 our construction 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 our proposal is efficient and that cross-user leakage grows slowly as queries are performed.
Joint work with S. Patel and K. Yeo (Google Inc.)