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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
dynamic symmetric searchable encryptionrange queryforward securitybackward security
Contact author(s)
wj016 @ ie cuhk edu hk
sherman @ ie cuhk edu hk
History
2019-05-20: received
Short URL
https://ia.cr/2019/497
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/497,
      author = {Jiafan Wang and Sherman S.  M.  Chow},
      title = {Forward and Backward-Secure Range-Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/497},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/497}},
      url = {https://eprint.iacr.org/2019/497}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.