International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Dynamic Local Searchable Symmetric Encryption

Michael Reichle , Inria and ENS, Paris
Brice Minaud , Inria and ENS, Paris
Search ePrint
Search Google
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
  title={Dynamic Local Searchable Symmetric Encryption},
  author={Michael Reichle and Brice Minaud},