Paper 2013/832

Practical Dynamic Searchable Encryption with Small Leakage

Emil Stefanov, Charalampos Papamanthou, and Elaine Shi


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 any other previous DSSE construction and supports both updates and searches in sublinear time in the worst case, maintaining at the same time a data structure of only linear size. We finally provide an implementation of our construction, showing its practical efficiency.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. NDSS 2014
dynamic searchable encryptionDSSEaccess patterns
Contact author(s)
emil @ cs berkeley edu
2013-12-16: received
Short URL
Creative Commons Attribution


      author = {Emil Stefanov and Charalampos Papamanthou and Elaine Shi},
      title = {Practical Dynamic Searchable Encryption with Small Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2013/832},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.