Updatable searchable symmetric encryption: Definitions and constructions

Searchable symmetric encryption (SSE) allows a client to search over encrypted data. To address the real threat of key compromise in practice, this work initiates the study of key rotation for SSE and introduces the notion of updatable SSE (USSE). In USSE, a client can issue a single update token that permits the server to convert existing encrypted data from the old key to the new key. In particular, • we formalize the syntax of USSE and define the security model that captures the inference of key, search token, update token and encrypted data with bi-/uni-/no-directional key updates and bi-/uni-directional encrypted data updates. • we present a USSE scheme that supports conjunctive queries with sub-linear complexity, and prove its security with no-directional key update and bi-directional encrypted data update. We also give extensions for concerning different key/encrypted data updates. • we implement our USSE schemes and evaluate the performance with real-world dataset, which illustrates that our schemes achieve practically acceptable computational overhead and communication cost. Technically, our formalization of USSE is inspired by updatable encryption (UE); our USSE schemes are obtained by a semi-generic transformation from Cash et al.'s SSE and UE. The transformation itself only relies on DL and DBDH assumptions. We believe that the transformation is of independent interest and applicable to other scenarios where the SSE systems follow the structure of Cash et al.'s work.