Paper 2017/973

Symmetric Searchable Encryption with Sharing and Unsharing

Sarvar Patel, Giuseppe Persiano, and Kevin Yeo

Abstract

We consider Symmetric Searchable Encryption with Sharing and Unsharing (SSEwSU), a notion that models Symmetric Searchable Encryption (SSE) in a multi-user setting in which documents can be dynamically shared and unshared among users. Previous works on SSE involving multiple users have assumed that all users have access to the same set of documents and/or their security models assume that all users in the system are trusted. As in SSE, every construction of a SSEwSU will be a trade-off between efficiency and security, as measured by the amount of leakage. In multi-user settings, we must also consider cross-user leakage (x-user leakage) where a query performed by one user would leak information about the content of documents shared with a different user. We start by presenting two strawman solutions that are at the opposite side of the efficiency-leakage bidimensional space: x-uz, that has zero x-user leakage but is very inefficient, and x-uL, that is very efficient but highly insecure with very large x-user leakage. We give a third construction, x-um, that is as efficient as x-uL and more efficient than x-uz. At the same time, x-um is considerably more secure than x-uL. Construction x-um is based on the concept of a Re-writable Deterministic Hashing (RDH), which can be thought of as a two-argument hash function with tokens that add re-writing capabilities. Sharing and unsharing in x-um is supported in constant (in the number of users, documents, and keywords) time. We give a concrete instantiation whose security is based on the Decisional Diffie-Hellman assumption. We provide a rigorous analysis of x-um and show a tight bound on the leakage in the presence of an active adversary that corrupts a subset of the users. We report on experimental work that show that x-um is very efficient and x-user leakage grows very slowly as queries are performed by the users. Additionally, we present extensions of x-um. We modify x-um to support a finer grained access granularity, so a document can be shared to a user either only for reading (i.e., searching) or for writing (i.e., editing). We also extend x-um to the bilinear setting to further reduce leakage.