Conference proceeding
Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions
PROCEEDINGS OF THE 31ST USENIX SECURITY SYMPOSIUM, pp.2425-2442
01 Jan 2022
Abstract
We focus on the problem of Dynamic Searchable Encryption (DSE) with efficient (optimal/quasi-optimal) search in the presence of deletions. Towards that end, we first propose OSSE, the first DSE scheme that can achieve asymptotically optimal search time, linear to the result size and independent of any prior deletions, improving the previous state of the art by a multiplicative logarithmic factor. We then propose our second scheme LLSE, that achieves a sublogarithmic search overhead (log log i(w), where i(w) is the number or prior insertions for a keyword) compared to the optimal achieved by OSSE. While this is slightly worse than our first scheme, it still outperforms prior works, while also achieving faster deletions and asymptotically smaller server storage. Both schemes have standard leakage profiles and are forward-and-backward private. Our experimental evaluation is very encouraging as it shows our schemes consistently outperform the prior state-of-the-art DSE by 1.2-6.6x in search computation time, while also requiring just a single roundtrip to receive the search result. Even compared with prior simpler and very efficient constructions in which all deleted records are returned as part of the result, our OSSE achieves better performance for deletion rates ranging from 45-55%, while the previous state-of-the-art quasi-optimal scheme achieves this for 65-75% deletion rates.
Metrics
5 Record Views
Details
- Title
- Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions
- Creators
- Javad Ghareh Chamani - HKUST, Hong Kong, Peoples R ChinaDimitrios Papadopoulos - HKUST, Hong Kong, Peoples R ChinaMohammadamin Karbasforushan - University of California, Santa CruzIoannis Demertzis - University of California, Santa CruzUSENIX Assoc
- Publication Details
- PROCEEDINGS OF THE 31ST USENIX SECURITY SYMPOSIUM, pp.2425-2442
- Conference
- 31ST USENIX SECURITY SYMPOSIUM, 31st
- Publisher
- Usenix Assoc
- Number of pages
- 18
- Grant note
- GRF-16200721 / Hong Kong Research Grants Council
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Mathematics
- Identifiers
- 991020532109404721
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Information Systems
- Computer Science, Theory & Methods