Paper 2024/829

Multi-Server Doubly Efficient PIR in the Classical Model and Beyond

Abstract

A Doubly Efficient Private Information Retrieval (DEPIR) is defined as a Private Information Retrieval (PIR) scheme with both near-linear server-side preprocessing time and sublinear query time. For many years, it has been a strong open question to devise a DEPIR scheme from standard assumptions. Very recently, Lin et al. (STOC '23) devised the first single-server DEPIR scheme from standard assumptions. However, their work left one major question open: can we build a DEPIR scheme in the multi-server setting, without relying on heavy cryptographic machinery? In this work, we discuss two different settings for multi-server DEPIR. In the non-colluding, non-communicating servers setting, we propose the first doubly efficient multi-server PIR scheme. Our scheme is information-theoretic. For a database of size $N$, our scheme allows servers to answer an infinite number of client queries in $N^{o(1)}$ time, after a single preprocessing phase which takes $N^{1+o(1)}$ time. Our result is only a $N^{o(1)}$ factor from the lower bound proven by Persiano and Yeo (SODA '22) for this setting. In addition, we devise a second information-theoretic PIR scheme in this setting which pushes the state of the art for the setting where the number of servers is more constrained. It achieves equally fast query times as our first scheme above, and a preprocessing time of $N^{2+o(1)}$. This scheme uses $O(\log N)$ servers. Both schemes don't require any cryptographic primitives. Furthermore, in the setting where the servers are additionally allowed to communicate and keep a global state (which is similarly required by PIR allowing database updates), we show a family of information-theoretic DEPIR schemes which achieve $N\mathsf{polylog} N$ preprocessing time, and $\log^3 N$ communication and server time, for any number of servers $k$ greater than three. We also discuss how introducing more servers or computational assumptions in this setting may improve the concrete efficiency of the PIR. This setting of communicating servers requires online communication between servers to answer queries, in contrast to the standard multi-server PIR setting where servers only communicate to coordinate the database contents and do not communicate at query time.

Note: Added a new result: a model with stateful servers (similar to PIR with regular updates) and inter-server communication, enabling multi-server PIR with substantial improvements in both asymptotic and concrete efficiency.