MUSES: Efficient Multi-User Searchable Encrypted Database

Searchable encrypted systems enable privacy-preserving keyword search on encrypted data. Symmetric systems achieve high efficiency (e.g., sublinear search), but they mostly support single-user search. Although systems based on publickey or hybrid models support multi-user search, they incur inherent security weaknesses (e.g., keyword-guessing vulnerabilities) and scalability limitations due to costly public-key operations (e.g., pairing). More importantly, most encrypted search designs leak statistical information (e.g., search, result, and volume patterns) and thus are vulnerable to devastating leakage-abuse attacks. Some pattern-hiding schemes were proposed. However, they incur significant user bandwidth/computation costs, and thus are not desirable for largescale outsourced databases with resource-constrained users. In this paper, we propose MUSES, a new multi-writer encrypted search platform that addresses the functionality, security, 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 Distributed Point Function, Distributed PRF, and Oblivious Linear Group Action. We also introduce novel distributed protocols 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 experimental 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. * This is the full version of our USENIX Security'24 paper [61] . number of users. However, data outsourcing might lead to privacy concerns, especially for sensitive data (e.g., medical/financial). An adversarial cloud can access and exploit data illegitimately. Although end-to-end encryption permits confidentiality, it prevents data utility (e.g., querying, analytics), thereby invalidating the benefits of outsourcing services. To address the data utilization and privacy dilemma, Searchable Encryption (SE) was proposed to enable keyword search over encrypted data while respecting the confidentiality of the data and the search query. There are two main SE models including Symmetric SE (SSE) [12, 28, 30, 42, 47, 52, 78] and Public-Key SE (PKSE) [4, 8, 10, 91] . While SSE offers high efficiency, forward/backward privacy [12, 42, 59, 59, 79, 83] , and diverse queries (e.g., range [29, 56, 83] ), it only supports a single user, where the data can only be searched by its owner. This strictly limits its practicality to apply for realworld settings, where the data can be contributed by multiple users. Moreover, SSE leaks statistical information including search/result/volume patterns, thus are vulnerable to leakageabuse attacks [16, 49, 54, 58, 60, 64, 71, 72, 74, 89, 93] . To prevent these leakages, some oblivious SSE schemes (e.g., [28, 36, 47] were proposed using Oblivious RAM [77] or Private Information Retrieval (PIR) [43] ; however, they incur significant overhead (bandwidth, computation) to the user [70] . On the other hand, PKSE enables multi-user encrypted search, in which one user (reader) can search on encrypted documents shared by the other users (writers) [62, 66, 90, 91] . However, PKSE has some security issues including lack of forward privacy and dictionary attacks. Recently, Wang et al. proposed Hybrid SE (HSE) [84] , which elegantly combines SSE and PKSE to achieve the benefits of both models: forward privacy and search efficiency by SSE, and multi-writer capability by PKSE. Despite its merits, HSE inherits other security weaknesses of both models, including keyword-guessing vulnerabilities and pattern leakages. Given that all existing SE schemes pose certain fundamental security, functionality, and efficiency limitations, we raise the following question: Can we design a new SE scheme that not only supports multi-writer search but also achieves concrete efficiency with