Practical Verifiable Multi-Key Searchable Encryption with Optimal Overhead

Multi-Key Searchable Encryption (MKSE) enables data owners to outsource their data to a cloud server, while supporting fine-grained data sharing with other authorized users. Existing most MKSE schemes can protect the date user’s search query privacy against collusion attacks between malicious data owners and the server. However, the server is not fully trusted and may maliciously return forged or incomplete search result. To address this issue, Verifiable Multi-Key Searchable Encryption (VMKSE) is proposed by leveraging Garbled Bloom Filter(GBF), which can support verifiability even when the search result is empty. Unfortunately, due to the massive native storage redundancy of Garbled Bloom Filters (GBF), the storage and computation costs of verification evidence generated during the sharing phase rise sharply with the quantity of shared documents. Therefore, in this paper, we present a novel VMKSE scheme by adopting Binary Fuse Filter(BFF), VMKSE-BFF, which can simultaneously support verifiability of search result and secure data sharing in multi-user setting. We provide a comparison with the existing VMKSE schemes. Experimental results on real-world datasets show a significant performance improvement of VMKSE-BFF.