Conjunctive dynamic searchable symmetric encryption

Abstract

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 () construction from Crypto’13 is the most efficient SSE scheme that allows conjunctive searches, but only for static databases. In NDSS’20, was extended to supporting dynamic updates. However, 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 scheme as modular black-boxes. Our scheme generalises . We provide new security definitions of forward and backward privacy for the new NMD setting. Our generic construction (and hence ) achieves forward and backward privacy in the new setting, even when the underlying single keyword SSE scheme is only 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.