Paper 2025/2013

MARS: Low-Leakage Multi Adversarial Owner and Reader Replication-free Searchable Encryption from Private Information Retrieval

Abstract

In searchable encryption, a data owner outsources data to a server while allowing efficient search by clients. A multimap associates keywords with a variable number of documents. We consider the setting with multiple owners and multiple clients (Wang and Papadopolous, Cloud Computing 2023). The goal is for each owner to store a multimap and grant access to clients. Prior work shares three weaknesses: * Restricting patterns of adversarial behavior, * Duplicating any data shared with a new client, and * Leaking each client's access pattern and share pattern. We present MARS, the first SSE for multiple owners and clients that considers security for an arbitrary collection of adversarial parties. Our scheme only leaks the volume of the result size and the number of requested keywords, both of which can be padded. No data is replicated. Our scheme combines 1) private information retrieval (PIR) to protect search patterns, 2) efficient delegation of the ability to index keywords and decrypt records, and 3) tabulation hashing to allow a single query for locations associated with a keyword. The first two items can be thought of as a keyword unkeyed PIR where the data owner gives the client the identifiers for individual keywords and keys to decrypt records. Our system is implemented on multimaps up to size $24$ million (the Enron dataset) with total time of $1.2$s for keywords that match $100$ documents. This is in comparison to a time $.500$s for Wang and Papadapolous, which replicates data and has access, sharing, and query equality leakage. Storage overhead is a factor of $6.6$. Our implementation uses FrodoPIR as the underlying PIR. Our system can incorporate batch or doubly-efficient unkeyed PIR as their performance improves.