Cryptology ePrint Archive: Report 2017/1105

FFSSE: Flexible Forward Secure Searchable Encryption with Efficient Performance

Zheli Liu and Siyi Lv and Yu Wei and Jin Li and 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.

Category / Keywords: cryptographic protocols

Date: received 25 Oct 2017, last revised 15 Nov 2017

Contact author: liuzheli at nankai edu cn

Available format(s): PDF | BibTeX Citation

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

Version: 20171120:085708 (All versions of this report)

Short URL: ia.cr/2017/1105

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]