Paper 2017/1105

FFSSE: Flexible Forward Secure Searchable Encryption with Efficient Performance

Zheli Liu, Siyi Lv, Yu Wei, Jin Li, Joseph K. Liu, and Yang Xiang

Abstract

Searchable Symmetric Encryption (SSE) has been widely applied in the design of encrypted database for exact queries or even range queries in practice. In spite of its efficiency and functionalities, it always suffers from information leakages. Some recent attacks point out that forward privacy is the desirable security goal. However, there are only a very small number of schemes achieving this security. In this paper, we propose a new forward secure SSE scheme, denoted as ``FFSSE'', which has the best performance in the literature, namely with fast search operation, fast token generation and O(1) update complexity. It also supports both add and delete operations in the unique instance. Technically, we exploit a novel ``key-based blocks chain'' technique based on symmetric cryptographic primitive, which can be deployed in arbitrary index tree structures or key-value structures directly to provide forward privacy. In order to reduce the storage on the client side, we further propose an efficient permutation technique (with similar function as trapdoor permutation) to support the re-construction of the search tokens. Experiments show that our scheme is 4 times, 300 times and 300 times faster than the state-of-the-art forward private SSE scheme (proposed in CCS 2016) in search, update and token generation, respectively. Security analysis shows that our scheme is secure.

Note: We have corrected the encoding in the abstract "4×, 300× and 300× faster than the Σoφoς”