Single Pass Client-Preprocessing Private Information Retrieval

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 run in time sublinear in the database size. However, the preprocessing phase is expensive—proportional to λ N, where λ is the security parameter (e.g., λ=128).

In this paper we propose SinglePass, the first PIR protocol that is concretely optimal with respect to client-preprocessing, requiring exactly a single linear pass over the database. Our approach yields a preprocessing speedup ranging from 45× to 100× and a query speedup of up to 20× when compared to previous state-of-the-art schemes (e.g., Checklist, USENIX SECURITY 2021, making preprocessing PIR more attractive for a myriad of use cases that are "session-based".

In addition to practical preprocessing, SinglePass features constant-time updates (additions/edits). Previously, the best known approach for handling updates in client-preprocessing PIR had complexity OlogN, while also adding a logN factor to the bandwidth. We implement our update algorithm and show concrete speedups of about 20× over previous state-of-the-art updatable schemes (e.g., Checklist).