Practical Dynamic Searchable Encryption with Small Leakage

Dynamic Searchable Symmetric Encryption (DSSE) enables a client to encrypt his document collection in a way that it is still searchable and efficiently updatable.However, all DSSE constructions that have been presented in the literature so far come with several problems: Either they leak a significant amount of information (e.g., hashes of the keywords contained in the updated document) or are inefficient in terms of space or search/update time (e.g., linear in the number of documents).In this paper we revisit the DSSE problem.We propose the first DSSE scheme that achieves the best of both worlds, i.e., both small leakage and efficiency.In particular, our DSSE scheme leaks significantly less information than…