Efficient Volume-Hiding Encrypted Multi-Maps with Support for Conjunctive Queries

Structured Encryption (STE), introduced by Chase and Kamara (ASIACRYPT 2010), enables to perform efficient private queries over an encrypted data structure. Very recently, Kamara and Moataz (EUROCRYPT 2019) formalized the notion of volume-hiding STE to mitigate the volume attack, and presented the first concrete volume-hiding encrypted multi-map (EMM) scheme with densest subgraph transform, which can ensure that the volume of values associated with the queried key is hidden to the adversary. To achieve better performance, Patel et al. (CCS 2019) designed a volume-hiding EMM scheme from cuckoo hash dubbed dprfMM. However, we observe that all the existing volume-hiding EMMs focus only on queries over a single key. Although the state-of-the-art conjunctive queries scheme OXT (CRYPTO 2013) can achieve sub-linear search complexity for conjunctive queries, it reveals the real volumes of the queried keys. Therefore, it is desirable to explore the volume-hiding encrypted multi-maps supporting conjunctive queries. In this paper, we initiate the study of volume-hiding EMM supporting conjunctive queries. We present, to our best knowledge, the first volume-hiding conjunctive EMM scheme OXTMM. Compared with the state-of-the-art volume-hiding single-key EMM scheme dprfMM, our proposed OXTMM can guarantee that the real volume of each key is hidden while supporting efficient conjunctive queries, the query communication overhead is \(2\ell \) encrypted key/value pairs together with a succinct data structure Bloom filter, where \(\ell \) is the maximum volume of all keys. In addition, we prove the security of our proposed OXTMM and give a thorough efficiency analysis between our proposal and the existing constructions. Finally we implement OXTMM and compare it with the most efficient scheme \(\textsf {OXT}\). Experiments result demonstrates that OXTMM can achieve volume-hiding conjunctive queries with a moderate efficiency loss.