Paper 2024/303

Single Pass Client-Preprocessing Private Information Retrieval

Arthur Lazzaretti, Yale University
Charalampos Papamanthou, Yale University

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).

Available format(s)
Cryptographic protocols
Publication info
Private Information Retrieval
Contact author(s)
arthur lazzaretti @ yale edu
charalampos papamanthou @ yale edu
2024-02-29: revised
2024-02-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Arthur Lazzaretti and Charalampos Papamanthou},
      title = {Single Pass Client-Preprocessing Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2024/303},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.