Paper 2019/1227

Dynamic Searchable Encryption with Small Client Storage

Ioannis Demertzis, Javad Ghareh Chamani, Dimitrios Papadopoulos, and Charalampos Papamanthou


We study the problem of dynamic searchable encryption (DSE) with forward-and-backward privacy. Many DSE schemes have been proposed recently but the most efficient ones have one limitation: they require maintaining an operation counter for each unique keyword, either stored locally at the client or accessed obliviously (e.g., with an oblivious map) at the server, during every operation. We propose three new schemes that overcome the above limitation and achieve constant permanent client storage with improved performance, both asymptotically and experimentally, compared to prior state-of-the-art works. In particular, our first two schemes adopt a “static-to-dynamic” transformation which eliminates the need for oblivious accesses during searches. Due to this, they are the first practical schemes with minimal client storage and non-interactive search. Our third scheme is the first quasi-optimal forward-and-backward DSE scheme with only a logarithmic overhead for retrieving the query result (independently of previous deletions). While it does require an oblivious access during search in order to keep permanent client storage minimal, its practical performance is up to four orders of magnitude better than the best existing scheme with quasi-optimal search.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
dynamic searchable encryptionforward and backward privacy
Contact author(s)
yannis @ umd edu
demertzis1990 @ gmail com
cpap @ umd edu
dipapado @ cse ust hk
jgc @ cse ust hk
2019-10-21: received
Short URL
Creative Commons Attribution


      author = {Ioannis Demertzis and Javad Ghareh Chamani and Dimitrios Papadopoulos and Charalampos Papamanthou},
      title = {Dynamic Searchable Encryption with Small Client Storage},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1227},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.