Paper 2022/648

Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions

Javad Ghareh Chamani, Hong Kong University of Science and Technology
Dimitrios Papadopoulos, Hong Kong University of Science and Technology
Mohammadamin Karbasforushan, University of California, Santa Cruz
Ioannis Demertzis, University of California, Santa Cruz
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 $\mathsf{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 $\mathsf{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 $\mathsf{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.6$\times$ 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 $\mathsf{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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. USENIX 2022
Keywords
Dynamic Searchable Encryption Forward and Backward privacy Optimal Search
Contact author(s)
jgc @ cse ust hk
dipapado @ cse ust hk
mkarbasf @ ucsc edu
idemertz @ ucsc edu
History
2022-07-01: revised
2022-05-25: received
See all versions
Short URL
https://ia.cr/2022/648
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/648,
      author = {Javad Ghareh Chamani and Dimitrios Papadopoulos and Mohammadamin Karbasforushan and Ioannis Demertzis},
      title = {Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/648},
      year = {2022},
      url = {https://eprint.iacr.org/2022/648}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.