Cryptology ePrint Archive: Report 2019/497

Forward and Backward-Secure Range-Searchable Symmetric Encryption

Jiafan Wang and Sherman S. M. Chow

Abstract: Dynamic searchable symmetric encryption (DSSE) allows a client to search or update over an outsourced encrypted database. Range query is commonly needed (AsiaCrypt'18) but order-preserving encryption approach is vulnerable to reconstruction attacks (SP'17). Previous range-searchable schemes (SIGMOD'16, ESORICS'18) require an ad-hoc instance of encrypted database to store the updates and/or suffer from other shortcomings, some brought by the usage of asymmetric primitives.

In this paper, with our encrypted index which enables queries for a sequence of contiguous keywords, we propose a generic upgrade of any DSSE to support range query (a.k.a. range DSSE), and a concrete construction which provides a new trade-off of reducing the client storage to "reclaim" the benefits of outsourcing.

Our schemes achieve forward security, an important property which mitigates file injection attacks. We identify a variant of fi le injection attack against a recent solution (ESORICS'18). We also extend the definition of backward security to range DSSE and show our schemes are compatible with a generic transformation for achieving backward security (CCS'17).

We comprehensively analyze the computation and communication overheads including some parts which were ignored in previous schemes, e.g., index-related operations in the client side. Our experiments demonstrate the high efficiency of our schemes.

Category / Keywords: cryptographic protocols / dynamic symmetric searchable encryption, range query, forward security, backward security

Date: received 14 May 2019

Contact author: wj016 at ie cuhk edu hk,sherman@ie cuhk edu hk

Available format(s): PDF | BibTeX Citation

Version: 20190520:123134 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]