CryptoDB
Dynamic Local Searchable Symmetric Encryption
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | CRYPTO 2022 |
| Abstract: | In this article, we tackle for the first time the problem of \emph{dynamic} memory-efficient Searchable Symmetric Encryption (SSE). In the term ``memory-efficient'' SSE, we encompass both the goals of \emph{local} SSE, and \emph{page-efficient} SSE. The centerpiece of our approach is a novel connection between those two goals. We introduce a map, called the Generic Local Transform, which takes as input a \emph{page-efficient} SSE scheme with certain special features, and outputs an SSE scheme with strong \emph{locality} properties. We obtain several results. (1) First, for page-efficient SSE with page size $p$, we build a \emph{dynamic} scheme with storage efficiency $\bigO{1}$ and page efficiency $O(\log \log (N/p))$, called LayeredSSE. The main technical innovation behind LayeredSSE is a novel weighted extension of the two-choice allocation process, of independent interest. (2) Second, we introduce the Generic Local Transform, and combine it with LayeredSSE to build a \emph{dynamic} SSE scheme with storage efficiency $O{1}$, locality $O{1}$, and read efficiency $O(\log\log N)$, under the condition that the longest list is of size $O(N^{1-1/\log \log \lambda})$. This matches, in every respect, the purely \emph{static} construction of Asharov et al. presented at STOC 2016: dynamism comes at no extra cost. (3) Finally, by applying the Generic Local Transform to a variant of the Tethys scheme by Bossuat et al. from Crypto 2021, we build an unconditional static SSE with storage efficiency $O(1)$, locality $O(1)$, and read efficiency $O(\log^\varepsilon N)$, for an arbitrarily small constant $\varepsilon > 0$. To our knowledge, this is the construction that comes closest to the lower bound presented by Cash and Tessaro at Eurocrypt 2014. |
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32109,
title={Dynamic Local Searchable Symmetric Encryption},
publisher={Springer-Verlag},
author={Michael Reichle and Brice Minaud},
year=2022
}