Paper 2026/1336

RotPIR: Sublinear Single-Server PIR with Efficient Pre-Processing via Oblivious Homomorphic Rotation

Abstract

Single-server PIR is a powerful cryptographic primitive that allows a client to retrieve public data from a remote server without revealing which item it accessed. Its privacy guarantee, however, inherently forces the server to do work linear in the database size, which is impractical at a large scale. Client-Preprocessing PIR (CP-PIR)~[Patel et al., CCS 2018] suggests to push linear computation to an offline preprocessing phase, enabling online queries with sublinear server computation and communication. While CP-PIR has since attracted considerable attention, designing an efficient preprocessing phase remains challenging. The original construction, along with much subsequent work~(e.g.,~[Zhou et al., S\&P 2024]), streams the entire database, which incurs linear communication that scales only to moderately sized data. A different approach consists of implementing the preprocessing using Fully Homomorphic Encryption (FHE) (e.g.,~[Corrigan-Gibbs et al., Eurocrypt 2022]), but the current best proposal (ThorPIR [Fisch et al., CCS 2024]) still imposes prohibitively expensive homomorphic computation on the server. In this paper, we tackle the problem of designing a practical preprocessing phase for CP-PIR. We introduce RotPIR, a novel CP-PIR with a preprocessing that is simultaneously sublinear-communication (i.e., no database streaming) and computation-efficient, while keeping online communication and computation sublinear. RotPIR is obtained by co-designing our PIR protocol with the underlying FHE operations. Specifically, we propose an innovative preprocessing framework with an advanced homomorphic operator, {\em oblivious homomorphic rotation}, which enables the database to be rotated according to an encrypted offset, and significantly accelerates the offline server-side computation. Our experimental results show that RotPIR can achieve up to $1000\times$ speedup in offline server-side computation when compared to the state-of-the-art CP-PIR protocols that do not stream the entire database during the preprocessing.