Partitioned Searchable Encryption

Symmetric searchable encryption (SSE) allows to outsource encrypted data to an untrusted server and retain searching capabilities. This is done without impacting the privacy of both the data and the search/update queries. In this work we put forth a new flavour of symmetric searchable encryption (SSE): Partitioned SSE is meant to capture the cases where the search rights must be partitioned among multiple individuals. We motivate through compelling examples the practical need for such a notion and discuss instantiations based on functional encryption and trapdoor permutations.

First we leverage the power of functional encryption (FE). Our construction follows the general technique of encrypting the set of keywords and the presumably larger datafiles separately, a keyword acting as a ``pointer'' to datafiles it belongs to. To improve on the constraint factors (large ciphertext, slow encryption/decryption procedures) that are inherent in FE schemes, the keyword check is done with the help of a Bloom filter -- one per datafile: the crux idea is to split the filter into buckets, and encrypt each bucket separately under an FE scheme. Functional keys are given for binary \masks checking if relevant positions are set to 1 inside the underlying bit-vector of the Bloom filter.

The second construction we present achieves forward security and stems from the scheme by Bost in CCS'16. We show that a simple tweak of the original construction gives rise to a scheme supporting updates in the partitioned setting. Moreover, the constructions take into account the possibility that some specific users are malicious while declaring their search results.