Welcome to the resource topic for 2024/303
Title:
Single Pass Client-Preprocessing Private Information Retrieval
Authors: Arthur Lazzaretti, Charalampos Papamanthou
Abstract:Recently, many works have considered Private Information Retrieval (PIR) with client-preprocessing: In this model a client and a server jointly run a preprocessing phase, after which client queries can run in time sublinear in the size of the database. In addition, such approaches store no additional bits per client at the server, allowing us to scale PIR to a large number of clients.
In this work, we propose the first client-preprocessing PIR scheme with single pass'' client-preprocessing. In particular, our scheme is concretely optimal with respect to preprocessing, in the sense that it requires exactly one linear pass over the database. This is in stark contrast with existing works, whose preprocessing is proportional to $\lambda \cdot N$, where $\lambda$ is the security parameter (e.g., $\lambda=128$). Our approach yields a preprocessing speedup of 45-100$\times$ and a query speedup of up to 20$\times$ when compared to previous state-of-the-art schemes (e.g., Checklist, USENIX 2021), making preprocessing PIR more attractive for a myriad of use cases that are session-based’'.
In addition to fast preprocessing, our scheme features extremely fast updates (additions and edits)—in constant time. Previously, the best known approach for handling updates in client-preprocessing PIR had time complexity O(\log N), while also adding a \log N factor to the bandwidth. We implement our update algorithm and show concrete speedups of about 20$\times$ in update time when compared to the previous state-of-the-art updatable scheme (e.g., Checklist, USENIX 2021).
ePrint: https://eprint.iacr.org/2024/303
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 .