Practical Volume-Hiding Encrypted Multi-Maps with Optimal Overhead and Beyond

Encrypted multi-map (EMM), as a special case of structured encryption, has attracted extensive attention recently. However, most of EMM constructions reveal the real volumes of queried keys, which can be leveraged to launch leakage-abuse attacks, as demonstrated by Kellaris et al. in CCS 2016 and Kornaropoulos et al. in S&P 2021. In this paper, we propose a practical non-lossy volume-hiding EMM scheme, XorMM, that can achieve optimal query communication complexity with minimal storage cost. Specifically, compared to the state-of-the-art dprfMM (Patel et al. CCS 2019), the client in our scheme receives only ĝ.,"matching results while not suffering from data loss, where ĝ.,"is the maximum volume of all keys. In addition, the storage cost of XorMM is approximately 1.23n, where n is the total number of key/value pairs. In contrast, the query communication and storage complexity of dprfMM is 2ĝ.,"and 2(1+α)n respectively, where 0<α<1 is a small constant. Furthermore, we initiate the study of volume-hiding EMM against malicious servers. To the best of our knowledge, we present the first verifiable volume-hiding EMM scheme, XorMM, from merely symmetric cryptographic tools. The scheme still outperforms dprfMM while supporting verifiability, the query complexity and storage overhead of which are approximately ĝ.,"+1 and 2.46n, respectively. Finally, we implement our proposed schemes and compare them with the most efficient scheme dprfMM (Patel et al. CCS 2019). The experimental results demonstrate that both of our schemes are superior to the state-of-the-art in both search and storage cost. In particular, XorMM (resp. VXorMM) brings a saving of 76% (resp. 52%) in server storage cost and achieves a speedup of 1.8x (resp. 1.6x) in search latency.