Paper 2020/1328

SWiSSSE: System-Wide Security for Searchable Symmetric Encryption

Zichen Gui, ETH Zurich
Kenneth G. Paterson, ETH Zurich
Sikhar Patranabis, IBM Research - India
Bogdan Warinschi, University of Bristol, Dfinity

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.

Available format(s)
Publication info
Published elsewhere. Minor revision. PoPETs 2024
Searchable Symmetric EncryptionSystem-Wide SecurityLeakage CryptanalysisBucketizationForward and Backward PrivacyOblivious Operations
Contact author(s)
zichen gui @ inf ethz ch
kenny paterson @ inf ethz ch
sikhar patranabis @ ibm com
csxbw @ bristol ac uk
2023-08-21: last of 5 revisions
2020-10-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zichen Gui and Kenneth G.  Paterson and Sikhar Patranabis and Bogdan Warinschi},
      title = {SWiSSSE: System-Wide Security for Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1328},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.