MUSES: Efficient Multi-User Searchable Encrypted Database

Abstract

Searchable encrypted systems enable privacy-preserving key- word search on encrypted data. Symmetric systems achieve high efficiency (e.g., sublinear search), but they mostly sup- port single-user search. Although systems based on public- key or hybrid models support multi-user search, they incur inherent security weaknesses (e.g., keyword-guessing vulner- abilities) and scalability limitations due to costly public-key operations (e.g., pairing). More importantly, most encrypted search designs leak statistical information (e.g., search, re- sult, and volume patterns) and thus are vulnerable to devas- tating leakage-abuse attacks. Some pattern-hiding schemes were proposed. However, they incur significant user band- width/computation costs, and thus are not desirable for large- scale outsourced databases with resource-constrained users.
In this paper, we propose MUSES, a new multi-writer en- crypted search platform that addresses the functionality, se- curity, and performance limitations in the existing encrypted search designs. Specifically, MUSES permits single-reader, multi-writer functionalities with permission revocation and hides all statistical information (including search, result, and volume patterns) while featuring minimal user overhead. In MUSES, we demonstrate a unique incorporation of various emerging distributed cryptographic protocols including Dis- tributed Point Function, Distributed PRF, and Oblivious Lin- ear Group Action. We also introduce novel distributed proto- cols for oblivious counting and shuffling on arithmetic shares for the general multi-party setting with a dishonest majority, which can be found useful in other applications. Our experi- mental results showed that the keyword search by MUSES is two orders of magnitude faster with up to 97× lower user bandwidth cost than the state-of-the-art.