Flash: Practical Volume-Hiding Encrypted Conjunctive Multi-Map With Optimal Overhead
Jiaojiao Wu, Jianfeng Wang, Shi-Feng Sun, Xiaofeng Chen · IEEE Transactions on Dependable and Secure Computing · 2025
Volume-hiding encrypted multi-map (EMM) allows the client to efficiently search on encrypted data while concealing the real volume of values for the queried key, thereby mitigating privacy-compromising attacks that depend on volume knowledge. However, most of the volume-hiding EMMs focus on single keyword queries, leaving the design of a volume-hiding conjunctive-keyword EMM a significant challenge. In this paper, we first propose a performance-optimized volume-hiding single-keyword EMM by adopting binary fuse filter,$\mathsf {BF^{2}MM}$, which serves as the crucial component for volume-hiding conjunctive-keyword EMM. We then introduce a generic construction dubbed$\mathsf {vCMM}$for volume-hiding conjunctive query, relying on a novel index structure from merely symmetric-key cryptographic tools. We further instantiate it to a practical volume-hiding conjunctive-keyword EMM,$\mathsf {BF^{2}CMM}$, which features nearly optimal query communication complexity and storage overhead. In addition, we extend our proposals to non-interactive DP-variants$\mathsf {DP\textrm {-}BF^{2}MM}$and$\mathsf {DP\textrm {-}BF^{2}CMM}$to provide tunable trade-offs between performance and privacy. Finally, we provide a thorough comparison with the existing volume-hiding conjunctive-keyword EMM$\mathsf {OXTMM}$. Experimental results show a significant performance improvement of$\mathsf {BF^{2}CMM}$, with over a$2\times$storage saving, a$90\times$increase in setup efficiency, and roughly$180\times$speedup in search latency compared to$\mathsf {OXTMM}$, respectively.