Paper 2021/786

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

Yongjun Zhao, Huaxiong Wang, and 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Encrypted StorageSearchable EncryptionLeakage and Outsourced Encryption
Contact author(s)
yongjun zhao @ ntu edu sg
foreverjun zhao @ gmail com
2021-06-14: received
Short URL
Creative Commons Attribution


      author = {Yongjun Zhao and Huaxiong Wang and Kwok-Yan Lam},
      title = {Volume-Hiding Dynamic Searchable Symmetric Encryption with Forward and Backward Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2021/786},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.