Conjunctive dynamic searchable symmetric encryption

Abstract

A practical searchable symmetric encryption (SSE) should allow users to privately store documents on untrusted servers with the abilities to (1) search with multiple keywords, and (2) add or delete documents dynamically. The oblivious cross tag (OXT) construction from Crypto’13 is the most efficient SSE scheme that allows conjunctive searches, but only for static databases. In NDSS’20, OXT was extended to ODXT supporting dynamic updates. However, ODXT is not forward private. In this work, we identify a commonly used setting for SSE where a document with its associated keywords can be dynamically added to or deleted from the database as a whole, but the keyword set is not modified in between. We call it the non-modifiable document (NMD) setting. In this NMD setting, we propose a generic framework for designing conjunctive dynamic SSE (CD-SSE), supporting conjunctive queries that allow dynamic updates while being forward and backward private at the same time. Our construction uses a generic dynamic single keyword SSE and the OXT scheme as modular black-boxes. Our scheme generalises ODXT. We provide new security definitions of forward and backward privacy for the new NMD setting. Our generic construction (and hence ODXT) achieves forward and BPUP backward privacy in the new setting, even when the underlying single keyword SSE scheme is only WBP backward private. We analyse the precise leakages of our scheme to the adversarial server in the NMD setting. We have instantiated our generic construction with three different single keyword schemes. Experiments show that our schemes are very efficient and practical. Our code is publicly available.