VeriFuzzy: A Dynamic Verifiable Fuzzy Search Service Framework for Encrypted Cloud Data
Jie Zhang, Xiaohong Li, Man Chun Zheng, Ruitao Feng, Shanshan Xu, Zhé Hóu, Guangdong Bai · IEEE Transactions on Services Computing · 2025
Enabling search over encrypted cloud data is essential for privacy-preserving data outsourcing. While searchable encryption has evolved to support individual requirements like fuzzy matching (tolerance to typos and variants in query keywords), dynamic updates, and result verification, designing a service that supports Dynamic Verifiable Fuzzy Search (DVFS) over encrypted cloud data remains a fundamental challenge due to inherent conflicts between underlying technologies. Existing approaches struggle with simultaneously achieving efficiency, functionality, and security, often forcing impractical trade-offs. This paper presentsVeriFuzzy, a novel DVFS service framework that cohesively integrates three innovations: anEnhanced Virtual Binary Tree (EVBTree)that decouples fuzzy semantics from index logic to support$O(\log n)$search/updates; ablockchain-reconstructed verificationmechanism that ensures result integrity with logarithmic complexity; and adual-repository state managementscheme that achieves IND-CKA2 security by neutralizing branch leakage. Extensive evaluation on 3,500+ documents shows VeriFuzzy achieves 41% faster search,$5\times$more efficient verification, and constant-time index updates compared to state-of-the-art alternatives. Our code and dataset are now open source, hoping to inspire future DVFS research.