Paper 2021/1585

Searchable Encryption for Conjunctive Queries with Extended Forward and Backward Privacy

Cong Zuo, Shangqi Lai, Xingliang Yuan, Joseph K. Liu, Jun Shao, and Huaxiong Wang


Recent developments in the field of Dynamic Searchable Symmetric Encryption (DSSE) with forward and backward privacy have attracted much attention from both research and industrial communities. However, most forward and backward private DSSE schemes support single keyword queries only, which impedes its prevalence in practice. Until recently, Patranabis et al. (NDSS 2021) introduced a forward and backward private DSSE for conjunctive queries (named ODXT) based on the Oblivious Cross-Tags (OXT) framework. Unfortunately, its security is not comprehensive for conjunctive queries, and it deploys “lazy deletion”, which incurs more communication cost. Besides, it cannot delete a file in certain circumstances. To address these problems, we introduce two forward and backward private DSSE schemes with conjunctive queries (named SDSSE-CQ and SDSSE-CQ-S). To analysis their security, we present two new levels of backward privacy (named Type-O and Type-O$^-$, where Type-O$^-$ is more secure than Type-O), which describe the leakages of conjunctive queries with OXT framework more accurately. Finally, the security and experimental evaluation demonstrate that our proposed schemes achieve better security with comparable computation and communication increase in comparison with ODXT.

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


      author = {Cong Zuo and Shangqi Lai and Xingliang Yuan and Joseph K.  Liu and Jun Shao and Huaxiong Wang},
      title = {Searchable Encryption for Conjunctive Queries with Extended Forward and Backward Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1585},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.