.png){kind=icon}
.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, <inline-formula><tex-math notation="LaTeX">$\mathsf {BF^{2}\,MM}$</tex-math></inline-formula>, which serves as the crucial component for volume-hiding conjunctive-keyword EMM. We then introduce a generic construction dubbed <inline-formula><tex-math notation="LaTeX">$\mathsf {vCMM}$</tex-math></inline-formula> 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, <inline-formula><tex-math notation="LaTeX">$\mathsf {BF^{2}CMM}$</tex-math></inline-formula>, which features nearly optimal query communication complexity and storage overhead. In addition, we extend our proposals to non-interactive DP-variants <inline-formula><tex-math notation="LaTeX">$\mathsf {DP\text {-}BF^{2}\,MM}$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\mathsf {DP\text {-}BF^{2}CMM}$</tex-math></inline-formula> to provide tunable trade-offs between performance and privacy. Finally, we provide a thorough comparison with the existing volume-hiding conjunctive-keyword EMM <inline-formula><tex-math notation="LaTeX">$\mathsf {OXTMM}$</tex-math></inline-formula>. Experimental results show a significant performance improvement of <inline-formula><tex-math notation="LaTeX">$\mathsf {BF^{2}CMM}$</tex-math></inline-formula>, with over a <inline-formula><tex-math notation="LaTeX">$2\times$</tex-math></inline-formula> storage saving, a <inline-formula><tex-math notation="LaTeX">$90\times$</tex-math></inline-formula> increase in setup efficiency, and roughly <inline-formula><tex-math notation="LaTeX">$180\times$</tex-math></inline-formula> speedup in search latency compared to <inline-formula><tex-math notation="LaTeX">$\mathsf {OXTMM}$</tex-math></inline-formula>, respectively.
Keywords:
Encrypted multi-map
conjunctive keyword query
volume-hiding
differential privacy
Journal
IF:
7.5
Papers:
2.4K
Citations:
9.6K