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.
Category / Keywords: cryptographic protocols / Encrypted Search Date: received 3 Oct 2017 Contact author: kwlyeo at google com Available format(s): PDF | BibTeX Citation Version: 20171005:142729 (All versions of this report) Short URL: ia.cr/2017/973 Discussion forum: Show discussion | Start new discussion