Paper 2021/786

Volume-Hiding Dynamic Searchable Symmetric Encryption with Forward and Backward Privacy

Yongjun Zhao, Huaxiong Wang, and Kwok-Yan Lam

Abstract

Volumetric leakage in encrypted databases had been overlooked by the community for a long time until Kellaris et al. (CCS ’16) proposed the first database reconstruction attack leveraging communication volume. Their attack was soon improved and several query recovery attacks were discovered recently. In response to the advancements of volumetric leakage attacks, volume-hiding searchable symmetric encryption (SSE) schemes have been proposed (Kamara and Moataz, Eurocrypt ’19 & Patel et al., CCS ’19). In these schemes, the database is padded in a clever way so that the volume (i.e., the number of responses) for any search query is the same or computationally indistinguishable while keeping the storage complexity and search complexity as small as possible. Unfortunately, existing volume-hiding SSE schemes do not support atomic updates (i.e., addition/deletion of an arbitrary keyword-document pair), which is the most common update operation considered in the SSE literature. Meanwhile, recent volumetric attacks (Wang et al., EuroS&P ’20 & Blackstone et al., NDSS ’20) indeed target dynamic databases. We initiate a formal study of volume-hiding dynamic SSE. We extend the existing definition of volume-hiding leakage function into the dynamic setting and present efficient constructions VH-DSSE and VH-DSSE^k . VH-DSSE suffers from non-negligible correctness error. To remedy the disadvantage of VH-DSSE, we propose a multi-copy construction VH-DSSE^k that amplifies correctness by parallel repetition. As a side contribution, both VH-DSSE and VH-DSSE^k satisfy the strongest notions of backward-privacy, which is the first one in the literature, to the best of our knowledge.