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 *compute* server, while the other is a restricted *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 $A$. Namely, correctness is guaranteed whenever the set of online servers $S$ satisfies $S\in A$, while privacy holds against every coalition $S\notin 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.
