$\mathrm{E}^{3}\text{FS}$: Efficient, Secure, and Verifiable Fuzzy Search with Data Updates in Hybrid-Storage Blockchains

The hybrid-storage blockchain (HSB) facilitates flexible data sharing and search applications across decentralized clients. However, ensuring data privacy and result integrity, while enhancing query and result verification efficiency in HSB-based search applications over dynamic datasets, poses significant challenges. In this paper, we propose E3FS, the first efficient, secure, and verifiable search scheme over dynamically updatable datasets in HSB systems, supporting multi-keyword fuzzy search, an important search function. E3FS accelerates search and verification through an updatable hybrid index with an efficient on-chain process. This design integrates encrypted LSH-based Bloom filters for maintaining file keyword information and an inverted index linking each keyword to a novel authenticated index tree spanning multiple files. Lightweight digests of these trees are stored on-chain to assist with verification, achieving sublinear search and verification costs. Moreover, the framework guarantees forward privacy by securely updating and refreshing both on-chain and off-chain index with new secrets upon each data update. Experimental results demonstrate that our solution outperforms state-of-the-art methods, achieving at least$\mathbf{58.6}\times$faster search and$\mathbf{34.4}\times$faster verification while reducing communication overhead by approximately$\mathbf{60}\times$.