Paper 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 file 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.