Paper 2026/1934

ReinsPIRe: High-Throughput, Low-Communication PIR with Server Preprocessing

Abstract

We present ReinsPIRe, a new single-server PIR with higher throughput (smaller computation costs) than all previous schemes that avoid offline communication. The crux of ReinsPIRe is new techniques for leveraging preprocessing in the common reference string (CRS) model to bring down the compute cost significantly. We show that the majority of the server's FHE operations may completely avoid NTT polynomial encodings while maintaining the ability to efficiently multiply polynomials using matrix operations. As a result, most computation may be performed with moduli that are natively supported by modern hardware substantially improving throughput. Furthermore, our techniques result in more compact cryptographic materials reducing memory bandwidth bottlenecks. To obtain ReinsPIRe, we apply our new techniques to the prior InsPIRe construction [Mahdavi et al., S&P 2026] to obtain a higher throughput single-server PIR while maintaining the same low communication costs. ReinsPIRe obtains 5.9 GB/s throughput per server core that is a 2x improvement. We apply ReinsPIRe to improve two different applications. First, we consider the in-storage PIR setting where large databases are stored in external memory (such as SSD) that introduces additional storage I/O costs. In this model, ReinsPIRe obtains 3.3x better throughput than prior works due to its smaller cryptographic material. Secondly, we present a verifiable PIR scheme vReinsPIRe building upon our formulation of server computation as matrix operations. vReinsPIRe provides the smallest online communication cost while using nearly 50x smaller long-term client storage compared to prior works with low online communication.