Towards Efficient Verifiable Forward Secure Searchable Symmetric Encryption

Searchable Symmetric Encryption (SSE) allows a server to perform search directly over encrypted data outsourced by user. Recently, the primitive of forward secure SSE has attracted significant attention due to its favorable property for dynamic data searching. That is, it can prevent the linkability from newly update data to previously searched keyword. However, the server is assumed to be honest-but-curious in the existing work. How to achieve verifiable forward secure SSE in malicious server model remains a challenging problem. In this paper, we propose an efficient verifiable forward secure SSE scheme, which can simultaneously achieve verifiability of search result and forward security property. In particular, we propose a new verifiable data structure based on the primitive of multiset hash functions, which enables efficient verifiable data update by incrementally hash operation. Compared with the state-of-the-art solution, our proposed scheme is superior in search and update efficiency while providing verifiability of search result. Finally, we present a formal security analysis and implement our scheme, which demonstrates that our proposed scheme is equipped with the desired security properties with practical efficiency.