Paper 2020/1357

Forward and Backward Private Dynamic Searchable Symmetric Encryption for Conjunctive Queries

Cong Zuo, Shi-Feng Sun, Joseph K. Liu, Jun Shao, Josef Pieprzyk, and Guiyi Wei


Recent research in Dynamic Searchable Symmetric Encryption (DSSE) focuses on efficient search over encrypted data while allowing updates. Unfortunately, as demonstrated by many attacks, updates can be a source of information leakage that can compromise DSSE privacy. To mitigate these attacks, forward and backward privacy of DSSE schemes have been introduced. A concerted effort of the research community has resulted in the publication of many DSSE schemes. To the best of our knowledge, however, there is no DSSE scheme supporting conjunctive queries, which achieves both forward and backward privacy. We give two DSSE schemes with forward and backward privacy, which support conjunctive queries, and they are suitable for different applications. In particular, we first introduce a new data structure termed the extended bitmap index. Then we describe our forward and backward private DSSE schemes, which support conjunctive queries. Our security analysis proves the claimed privacy characteristics, and experiments show that our schemes are practical. Compared to the state-of-the-art DSSE VBTree supporting conjunctive queries (but not backward privacy), our schemes offer search time that is a few orders of magnitude faster. Besides, our schemes claim better security (called Type-C backward privacy).

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Dynamic Searchable Symmetric EncryptionForward PrivacyBackward PrivacyConjunctive Queries
Contact author(s)
zuocong10 @ gmail com
2020-10-29: received
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Cong Zuo and Shi-Feng Sun and Joseph K.  Liu and Jun Shao and Josef Pieprzyk and Guiyi Wei},
      title = {Forward and Backward Private Dynamic Searchable Symmetric Encryption for Conjunctive Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1357},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.