Practical Verifiable Multi-Key Searchable Encryption with Optimal Overhead
Multi-Key Searchable Encryption (MKSE) enables data owners (DOs) to outsource their data to a cloud server (CS) while supporting fine-grained data sharing with other authorized users. Most existing MKSE schemes can protect data users’ (DUs’) search query privacy against collusion attacks between malicious DOs and the CS. However, the CS is not fully trusted and may maliciously return forged or incomplete search results. To address this issue, Verifiable MKSE (VMKSE) is proposed by leveraging Garbled Bloom Filter (GBF), which can support verifiability even when the search results are empty. Unfortunately, due to the massive native storage redundancy of GBF, the storage and computational overhead of verification evidence generated in the sharing phase increases as the number of shared documents grows. Therefore, in this paper, we present a novel VMKSE scheme (VMKSE-BFF) by adopting BFF, which can simultaneously support verifiability of and secure data sharing in a multi-user setting. We provide a comparison with the existing VMKSE schemes. Experimental results on a real-world dataset show a significant performance improvement of VMKSE-BFF.