Paper 2026/1372

Retrieve-Compute PIR and Its Applications

Abstract

Two-server Private Information Retrieval achieves arbitrarily small polynomial communication, but relies on a strong non-collusion assumption that is difficult to justify in practice. We introduce a new variant of two-server PIR in which one server acts as a standard \emph{compute} server, while the other is a restricted \emph{retrieval-only} server. The latter stores a public encoding of the database and merely serves requested symbols or blocks of this encoding, without performing any PIR-specific computation. We argue that such a retrieval-only server can be instantiated using existing static-content or repository-hosting services, thereby grounding the non-collusion assumption in realistic architectural and deployment constraints. Assuming Learning Parity with Noise (LPN) over the ternary field with inverse-polynomial noise rate, we construct RC-PIR with arbitrarily small polynomial communication and polynomial storage. Leveraging this construction, we derive the following unexpected applications for every constant \(k\): \begin{enumerate} \item \(k\)-server PIR with arbitrarily small polynomial communication and privacy against any coalition of \(k-1\) servers. \item \(k\)-server robust PIR with arbitrarily small polynomial communication that simultaneously achieves correctness and privacy with respect to an arbitrary monotone access structure \(\mathcal{A}\). Namely, correctness is guaranteed whenever the set of online servers \(S\) satisfies \(S \in \mathcal{A}\), while privacy holds against every coalition \(S \notin \mathcal{A}\). \item A \(k\)-party secure computation protocol for size-\(n\) truth tables also known as lookup tables, with arbitrarily small polynomial communication and passive security against any coalition of \(k-1\) parties. This result extends to active security either in the honest-majority setting, or without an honest majority assuming collision-resistant hash functions. \end{enumerate} None of these results were previously known under the LPN assumption. Along the way, we uncover new relationships between different complexity measures of PIR.