Cryptology ePrint Archive: Report 2013/832

Practical Dynamic Searchable Encryption with Small Leakage

Emil Stefanov and Charalampos Papamanthou and Elaine Shi

Abstract: 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.

Category / Keywords: cryptographic protocols / dynamic searchable encryption, DSSE, access patterns

Original Publication (in the same form): NDSS 2014

Date: received 8 Dec 2013

Contact author: emil at cs berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20131216:190531 (All versions of this report)

Short URL: ia.cr/2013/832

Discussion forum: Show discussion | Start new discussion