(AGENPARL) – WORLD WIDE, lun 14 giugno 2021
ePrint Report: Volume-Hiding Dynamic Searchable Symmetric Encryption with Forward and Backward Privacy
Yongjun Zhao, Huaxiong Wang, Kwok-Yan Lam
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.