Paper 2013/832
Practical Dynamic Searchable Encryption with Small Leakage
Emil Stefanov, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. NDSS 2014
- Keywords
- dynamic searchable encryptionDSSEaccess patterns
- Contact author(s)
- emil @ cs berkeley edu
- History
- 2013-12-16: received
- Short URL
- https://ia.cr/2013/832
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/832,
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{https://eprint.iacr.org/2013/832}},
url = {https://eprint.iacr.org/2013/832}
}
