The notion of Multi-Key Searchable Encryption (MKSE) enables data owners to outsource their data into a cloud server, while supporting fine-grained data sharing with the authorized users. Note that the traditional MKSE is vulnerable to data leakage. That is, the malicious data owner may collude with the server and recover the search queries of authorized users. Recently, Hamlin et al. (PKC’18) presented a new MKSE construction that can ensure data privacy between data owner and authorized users, where the share key is generated depending on data owner, authorized user and the specific document. However, their scheme cannot support verifiable search in the case of the malicious cloud server. In this paper, we propose a new verifiable MKSE (VMKSE) scheme by leveraging Garbled Bloom Filter, which can simultaneously support verifiability of search result and secure data sharing in multi-user setting. Compared to the state-of-the-art solution, the proposed scheme is superior in efficiency and verifiability. The experiment results demonstrate the efficiency of our scheme.

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.