Paper 2023/720

MUSES: Efficient Multi-User Searchable Encrypted Database

Tung Le, Virginia Tech
Rouzbeh Behnia, University of South Florida, Sarasota
Jorge Guajardo, Robert Bosch LLC – Research and Technology Center
Thang Hoang, Virginia Tech
Abstract

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 public-key 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 large-scale 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. USENIX Security Symposium 2024
Keywords
privacy-enhancing technologiesencrypted searchdata privacy
Contact author(s)
tungle @ vt edu
behnia @ usf edu
jorge guajardomerchan @ us bosch com
thanghoang @ vt edu
History
2024-07-26: last of 11 revisions
2023-05-18: received
See all versions
Short URL
https://ia.cr/2023/720
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2023/720,
      author = {Tung Le and Rouzbeh Behnia and Jorge Guajardo and Thang Hoang},
      title = {{MUSES}: Efficient Multi-User Searchable Encrypted Database},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/720},
      year = {2023},
      url = {https://eprint.iacr.org/2023/720}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.