FancyPIR: Stateless Batch Private Information Retrieval With Communication-Computation Trade-Offs

Existing Private Information Retrieval (PIR) protocols perform reasonably well in practice. However, the communication overhead remains a significant obstacle for large-scale applications. A natural approach is to amortize the communication overhead by querying multiple entries simultaneously. Recent research has explored Batch PIR (Multi-query PIR) protocols that optimize asymptotic complexity in single-server scenarios. This paper presentsFancyPIR, a stateless batch PIR solution that attempts to trade off communication against computation without depending on the preprocessing hint.FancyPIRaims to reduce the communication overhead while managing the computational cost. To this end,FancyPIRemploys two major strategies: first,FancyPIRreduces the number of rotations in the initialization (offline) phase and the number of multiplication operations in the server response (online) phase, which decreases the computational burden; second,FancyPIRpacks multiple queries and merges responses using the vectorized homomorphic encryption during the online phase, significantly reducing the communication overhead. Specifically, for retrieving a batch of 256 entries from a database containing2²⁰entries (each 256 Bytes in size),FancyPIRachieves a communication overhead reduction of 8.4~ 104×compared to state-of-the-art solutions (presented in IEEE S&P ’18 et al.), along with an improvement in initialization setup time by 1.9~ 3×. Considering communication and computation,FancyPIRreduces server monetary costs by 8.5~ 59×for different database sizes.