Dynamic Searchable Symmetric Encryption with forward and stronger backward privacy

Cong Zuo, Shi Feng Sun, Joseph K. Liu, Jun Shao, Josef Pieprzyk

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

24 Citations (Scopus)


Dynamic Searchable Symmetric Encryption (DSSE) enables a client to perform updates and searches on encrypted data which makes it very useful in practice. To protect DSSE from the leakage of updates (leading to break query or data privacy), two new security notions, forward and backward privacy, have been proposed recently. Although extensive attention has been paid to forward privacy, this is not the case for backward privacy. Backward privacy, first formally introduced by Bost et al., is classified into three types from weak to strong, exactly Type-III to Type-I. To the best of our knowledge, however, no practical DSSE schemes without trusted hardware (e.g. SGX) have been proposed so far, in terms of the strong backward privacy and constant roundtrips between the client and the server. In this work, we present a new DSSE scheme by leveraging simple symmetric encryption with homomorphic addition and bitmap index. The new scheme can achieve both forward and backward privacy with one roundtrip. In particular, the backward privacy we achieve in our scheme (denoted by Type-I is stronger than Type-I. Moreover, our scheme is very practical as it involves only lightweight cryptographic operations. To make it scalable for supporting billions of files, we further extend it to a multi-block setting. Finally, we give the corresponding security proofs and experimental evaluation which demonstrate both security and practicality of our schemes, respectively.

Original languageEnglish
Title of host publicationComputer Security – ESORICS 2019
Subtitle of host publication24th European Symposium on Research in Computer Security Luxembourg, September 23–27, 2019 Proceedings, Part II
EditorsKazue Sako, Steve Schneider, Peter Y.A. Ryan
Place of PublicationCham Switzerland
Number of pages21
ISBN (Electronic)9783030299620
ISBN (Print)9783030299613
Publication statusPublished - 2019
EventEuropean Symposium On Research In Computer Security 2019 - Luxembourg, Luxembourg
Duration: 23 Sep 201927 Sep 2019
Conference number: 24th
https://link.springer.com/book/10.1007/978-3-030-29959-0 (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceEuropean Symposium On Research In Computer Security 2019
Abbreviated titleESORICS 2019
Internet address


  • Backward privacy
  • Dynamic Searchable Symmetric Encryption
  • Forward privacy

Cite this