FSSE: Forward secure searchable encryption with keyed-block chains

Abstract Nowadays, people widely use Searchable Symmetric Encryption (SSE) to design the equality query and range query operation for encrypted database systems. A recent attack points out forward privacy is the necessary security goal which, however, has not been achieved by most of SSE schemes. Motivated by this security goal, we propose a forward secure SSE scheme whose index structure consists of keyed-block chains. The proposed scheme is efficient since the keyed-block chain can be implemented by symmetric encryption primitive and the scheme also supports both add and delete operations in one instance. We further employ the one-way permutation function to reduce the storage on the client side. Experiments show that our scheme is 4 × , 300 ×  and 300 ×  faster than the state-of-the-art forward private SSE scheme (CCS 2016) in search, update and token generation, respectively.