Paper 2021/765

Dynamic Volume-Hiding Encrypted Multi-Maps with Applications to Searchable Encryption

Ghous Amjad, Sarvar Patel, Giuseppe Persiano, Kevin Yeo, and Moti Yung


We study encrypted storage schemes where a client outsources data to an untrusted third-party server (such as a cloud storage provider) while maintaining the ability to privately query and dynamically update the stored data. We focus on encrypted multi-maps, a structured encryption (STE) scheme that stores pairs of label and value tuples that have several important applications (most notably, to searchable encryption and encrypted SQL databases). Encrypted multi-maps support queries for specific labels that return the associated value tuple. As responses are variable-length, encrypted multi-maps are subject to volume leakage attacks introduced by Kellaris et al. [CCS’16] with several follow-up works (including Grubbs et al. [CCS’18] and Lacharite et al. [S&P’18]). To prevent these attacks, volume-hiding encrypted multi-maps were introduced by Kamara and Moataz [Eurocrypt’19] that hide the volume of labels (i.e., the size of the associated value tuple). As our main contribution, we present the first fully dynamic constructions of volume-hiding encrypted multi-maps that are both asymptotically and concretely efficient. Furthermore, our constructions simultaneously provide forward and backward privacy that are the de-facto standard security notions for dynamic STE schemes (Stefanov et al. [NDSS’14] and Bost [CCS’16]). Additionally, we implement our schemes to showcase their concrete efficiency. Our experimental evaluations show that our constructions are able to add dynamicity with minimal to no additional cost compared to the prior best static volume-hiding schemes of Patel et al. [CCS’20].

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
encrypted searchvolume hidingencrypted multi-mapsstructured encryptionleakage
Contact author(s)
ghous_amjad @ brown edu
kwlyeo @ google com
2021-06-11: revised
2021-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ghous Amjad and Sarvar Patel and Giuseppe Persiano and Kevin Yeo and Moti Yung},
      title = {Dynamic Volume-Hiding Encrypted Multi-Maps with Applications to Searchable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/765},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.