XB-Muse: Practical Multiuser Dynamic Searchable Symmetric Encryption for Adaptive Revocation

Dynamic searchable symmetric encryption (DSSE) schemes support keyword search queries on encrypted dynamic datasets with add-or-delete operations stored on an untrusted remote server. Multi-user DSSE (MUDSSE) further considers multiple users to access the encrypted dataset. Most works of MUDSSE focus on how to promise forward and backward privacy of queries. However, the problem in which the data owner can not revocate the deleted encrypted data on the encrypted dataset adaptively and efficiently is not sufficiently considered. To solve this problem, we propose a new multi-user DSSE scheme named X-MUSE, extending cryptographic primitives Symmetric Revocable Encryption (SRE) to design a new searchable encryption with optimal search time for the deletion operation. Furthermore, to minimize communication size and counter new integrity threats raised by malicious clients, we extend X-MUSE to design a new MUDSSE named B-MUSE by integrating blockchain-based technology. Our evaluation confirms that our schemes have practical search performance and lower storage costs on both the server and the client side compared to the state-of-the-art.