Paper 2020/1328

SWiSSSE: System-Wide Security for Searchable Symmetric Encryption

Abstract

This paper initiates a new direction in the design and analysis of searchable symmetric encryption (SSE) schemes. We provide the first comprehensive security model and definition for SSE that takes into account leakage from the entirety of the SSE system, including not only from access to encrypted indices but also from access to the encrypted database documents themselves. Such system-wide leakage is intrinsic in end-to-end SSE systems, and can be used to break almost all state-of-the-art SSE schemes (Gui et al., IEEE S&P 2023). We then provide static and dynamic SSE constructions targeting our new notions. Our constructions involve a combination of novel techniques: bucketization to hide volumes of responses to queries; delayed, pseudorandom write-backs to disrupt access patterns; and indistinguishable search and update operations. The oblivious operations make it easy to establish strong versions of forward and backward security for our dynamic SSE scheme and rule out file-injection attacks. We implement our schemes and demonstrate that they offer very strong security against general classes of (system-wide) leakage-abuse attacks with moderate overhead. Our schemes scale smoothly to databases containing hundreds of thousand of documents and millions of keyword-document pairs. To the best of our knowledge, these are the first end-to-end SSE schemes that effectively suppress system-wide leakage while maintaining practical efficiency.

Note: This version of the paper contains a revised introduction that positions our main contribution as solving an open question (posed recently by Gui et al. at IEEE S&P 2023) on designing a practically efficient end-to-end SSE system that resists system-wide leakage cryptanalysis. Other changes from the previous version include: (a) more extensive coverage of related work, (b) additional experiments for highly-refined leakage cryptanalysis and parameter tuning in SWiSSSE, and (c) a more detailed experimental comparison of the performance of SWiSSSE with that of other end-to-end SSE systems over real-world databases. We thank the anonymous reviewers of PoPETS 2024 for their helpful feedback, comments, and suggestions.