Seny Kamara, Brown University

Abstract

We revisit the problem of designing secure and efficient dynamic searchable symmetric encryption (SSE) schemes in several respects. First, we consider the more general setting of structured encryption (STE). In particular, we focus on the design of dynamic encrypted multi-maps which give single-keyword SSE schemes and can be used as building blocks in boolean SSE and graph encryption schemes. Second, motivated by the problem of data breaches, we formalize a notion of security for dynamic STE schemes that guarantees security against a snapshot adversary; that is, an adversary that receives a copy of the encrypted structure at various times. Moreover, we initiate the study of dual-secure STE constructions; constructions that are secure against both a persistent and snapshot adversary while also being forward private.

As a concrete instantiation, we propose a new dual-secure dynamic multi-map encryption scheme. It outperforms all (non-dual-secure) existing constructions and has query complexity that grows with the selectivity of the query and the number of deletes since the client executed a (linear-time) rebuild protocol (which we show can be de-amortized).

We implemented our scheme and evaluated its concrete efficiency empirically. Our experiment shows that our construction is very efficient with queries taking less than 1 microsecond per query/label pair (keyword/id pair in the setting of SSE).