Paper 2021/879

Rethinking Searchable Symmetric Encryption

Zichen Gui, ETH Zurich
Kenneth G. Paterson, ETH Zurich
Sikhar Patranabis, IBM Research India

Symmetric Searchable Encryption (SSE) schemes enable keyword searches over encrypted documents. To obtain efficiency, SSE schemes incur a certain amount of leakage. The vast majority of the literature on SSE considers only leakage from one component of the overall SSE system, the encrypted search index. This component is used to identify which documents to return in response to a keyword query. The actual fetching of the documents is left to another component, usually left unspecified in the literature, but generally envisioned as a simple storage system matching document identifiers to encrypted documents. This raises the question: do SSE schemes actually protect the security of data and queries when considered from a system-wide viewpoint? We answer this question in the negative. We do this by introducing a new inference attack that achieves practically efficient, highly scalable, accurate query reconstruction against end-to-end SSE systems. In particular, our attack works even when the SSE schemes are built in the natural way using the state-of-the-art techniques (namely, volume-hiding encrypted multi-maps) designed to suppress leakage and protect against previous generations of attack. A second question is whether the state-of-the-art leakage suppression techniques can instead be applied on a system-wide basis, to protect both the encrypted search index and the encrypted document store, to produce efficient SSE systems. We also answer this question in the negative. To do so, we implement SSE systems using those state-of-the-art leakage suppression methods, and evaluate their performance. We show that storage overheads range from $100\times$ to $800\times$ while bandwidth overheads range from $20\times$ to $100\times$, as compared to a naive baseline system. Our results motivate the design of new SSE systems that are designed with system-wide security in mind from the outset. In this regard, we show that one such SSE system due to Chen et al. (IEEE INFOCOM 2018), with provable security guarantees based on differential privacy, is also vulnerable to our new attack. In totality, our results force a re-evaluation of how to build end-to-end SSE systems that offer both security and efficiency.

Available format(s)
Publication info
Published elsewhere. IEEE S&P 2023 (to appear)
Searchable Symmetric Encryption Structured Encryption Leakage-Abuse Attack Inference Attack System-Wide Leakage Query Reconstruction
Contact author(s)
zichen gui @ inf ethz ch
kenny paterson @ inf ethz ch
sikharpatranabis @ gmail com
2022-07-19: last of 4 revisions
2021-06-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zichen Gui and Kenneth G.  Paterson and Sikhar Patranabis},
      title = {Rethinking Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/879},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.