Welcome to the resource topic for 2025/2013
Title:
MARS: Low-Leakage Multi Adversarial Owner and Reader Replication-free Searchable Encryption from Private Information Retrieval
Authors: Benjamin Fuller, Arinjita Paul, Maryam Rezapour, Ronak Sahu, Amey Shukla
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.
ePrint: https://eprint.iacr.org/2025/2013
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .