Verifiable Fuzzy Multi-Keyword Search with Public Verification over Encrypted Cloud Databases

• Lang Cheng,
• Changgen Peng,
• Jin Niu,
• Hanlin Tang,

Vol. 20, No. 3, March 31, 2026
10.3837/tiis.2026.03.020, Download Paper (Free):

• fuzzy-keyword searchable encryption
• locality-sensitive hashing
• MinHashLSH
• verifiability
• vector commitment

Abstract

In the realm of cloud storage, verifiable fuzzy searchable encryption (VFSE) enables clients to verify the integrity of outsourced encrypted data while supporting fuzzy keyword search over ciphertext, thereby mitigating the risks associated with using untrusted servers. A prevalent approach for implementing fuzzy keyword search in VFSE is to combine Bloom Filters (BF) with locality-sensitive hashing (LSH). However, most BF-LSH-based schemes require the computation of inner products between the trapdoor and all database entries during retrieval, which incurs much computational overhead. Furthermore, most of the current VFSE schemes support only private verification, which not only increases the computational burden on the client but may also lead to dispute issues with third-party data users. To address these challenges, this paper proposes a novel verifiable database scheme that supports fuzzy multi-keyword search with public verification. We refer to it as MLVC-VDB. The proposed scheme initially uses the MinHashLSH index to identify a candidate range of documents for retrieval, then utilizes a BF-LSH structure to match fuzzy keywords within this candidate set. Finally, the vector commitment is used to enable public verification of the query results. Additionally, to further reduce parameter complexity and alleviate the computational overhead inherent in vector commitment, we design a double-layer fuzzy clustering index structure based on MinHashLSH. Comprehensive security analysis and experimental evaluations demonstrate that our scheme is both secure and efficient for practical applications.

Statistics

Cite this article