Forward and Backward-Secure Range-Searchable Symmetric Encryption
Authors: Jiafan Wang (Dept. of Information Engineering, The Chinese University of Hong Kong), Sherman S. M. Chow (Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong)
Volume: 2022
Issue: 1
Pages: 28–48
DOI: https://doi.org/10.2478/popets-2022-0003
Abstract: Dynamic searchable symmetric encryption (DSSE) allows a client to query or update an outsourced encrypted database. Range queries are commonly needed. Previous range-searchable schemes either do not support updates natively (SIGMOD’16) or use file indexes of many long bit-vectors for distinct keywords, which only support toggling updates via homomorphically flipping the presence bit. (ESORICS’18). We propose a generic upgrade of any (inverted-index) DSSE to support range queries (a.k.a. range DSSE), without homomorphic encryption, and a specific instantiation with a new trade-off reducing client-side storage. Our schemes achieve forward security, an important property that mitigates file injection attacks. Moreover, we identify a variant of injection attacks against the first somewhat dynamic scheme (ESORICS’18). We also extend the definition of backward security to range DSSE and show that our schemes are compatible with a generic upgrade of backward security (CCS’17). We comprehensively analyze the computation and communication overheads, including implementation details of client-side index-related operations omitted by prior schemes. We show high empirical efficiency for millionscale databases over a million-scale keyword space.
Keywords: dynamic symmetric searchable encryption, range, generic construction, saving client storage, attack
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
