DVFS: A Dynamic Verifiable Fuzzy Search Service for Encrypted Cloud Data

Abstract:

Cloud storage introduces critical privacy challenges for encrypted data retrieval, where fuzzy multi-keyword search enables approximate matching while preserving data confidentiality. Existing solutions face fundamental trade-offs between security and efficiency: linear-search mechanisms provide adaptive security but incur prohibitive overhead for large-scale data, while tree-based indexes improve performance at the cost of branch leakage vulnerabilities.

To address these limitations, we propose DVFS - a dynamic verifiable fuzzy search service with three core innovations: (1) An adaptive-secure fuzzy search method integrating locality-sensitive hashing with virtual binary trees, eliminating branch leakage while reducing search complexity from linear to sublinear ($O(\log n)$ time); (2) A dual-repository version control mechanism supporting dynamic updates with forward privacy, preventing information leakage during operations; (3) A blockchain-based verification system that ensures correctness and completeness via smart contracts, achieving $O(\log n)$ verification complexity. Our solution advances secure encrypted retrieval by simultaneously resolving the security-performance paradox and enabling trustworthy dynamic operations.

Zhang J, Li X, Zheng M, Hou Z, Bai G, Feng R. DVFS: A Dynamic Verifiable Fuzzy Search Service for Encrypted Cloud Data[J]. arXiv preprint arXiv:2507.10927, 2025.