Paper 2020/1342

Forward and Backward Private Conjunctive Searchable Symmetric Encryption

Sikhar Patranabis and Debdeep Mukhopadhyay


Dynamic searchable symmetric encryption (SSE) supports updates and keyword searches in tandem on outsourced symmetrically encrypted data, while aiming to minimize the information revealed to the (untrusted) host server. The literature on dynamic SSE has identified two crucial security properties in this regard - forward and backward privacy. Forward privacy makes it hard for the server to correlate an update operation with previously executed search operations. Backward privacy limits the amount of information learnt by the server about documents that have already been deleted from the database. To date, work on forward and backward private SSE has focused mainly on single keyword search. However, for any SSE scheme to be truly practical, it should at least support conjunctive keyword search. In this setting, most prior SSE constructions with sub-linear search complexity do not support dynamic databases. The only exception is the scheme of Kamara and Moataz (EUROCRYPT'17); however it only achieves forward privacy. Achieving both forward and backward privacy, which is the most desirable security notion for any dynamic SSE scheme, has remained open in the setting of conjunctive keyword search. In this work, we develop the first forward and backward private SSE scheme for conjunctive keyword searches. Our proposed scheme, called Oblivious Dynamic Cross Tags (or ODXT in short) scales to very large arbitrarily-structured databases (including both attribute-value and free-text databases). ODXT provides a realistic trade-off between performance and security by efficiently supporting fast updates and conjunctive keyword searches over very large databases, while incurring only moderate access pattern leakages to the server that conform to existing notions of forward and backward privacy. We precisely define the leakage profile of ODXT, and present a detailed formal analysis of its security. We then demonstrate the practicality of ODXT by developing a prototype implementation and evaluating its performance on real world databases containing millions of documents.

Note: An extended abstract of this paper will appear in NDSS 2021. This is the full version of the paper.

Available format(s)
Publication info
Published elsewhere. Major revision. NDSS 2021
Searchable Symmetric EncryptionDynamicConjunctive Keyword SearchForward and Backward Privacy
Contact author(s)
sikharpatranabis @ gmail com
debdeep mukhopadhyay @ gmail com
2020-10-30: last of 3 revisions
2020-10-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sikhar Patranabis and Debdeep Mukhopadhyay},
      title = {Forward and Backward Private Conjunctive Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1342},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.