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 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× over previous state-ofthe-art updatable schemes (e.g., Checklist).