.png){kind=icon}
Return
Flash: Practical Volume-Hiding Encrypted Conjunctive Multi-Map With Optimal Overhead
.png){kind=icon}
PRE
AI
DOI：10.1109/TDSC.2025.3600572.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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\text {-}BF^{2}\,MM}$ and $\mathsf {DP\text {-}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.
Keywords:
Encrypted multi-map
conjunctive keyword query
volume-hiding
differential privacy
Journal
IF:
7.5
Papers:
2.6K
Citations:
9.6K
Organization
Cited Papers
No cited papers available