Paper 2019/1483

Communication--Computation Trade-offs in PIR

Asra Ali and Tancrède Lepoint and Sarvar Patel and Mariana Raykova and Phillipp Schoppmann and Karn Seth and Kevin Yeo

Abstract

In this work, we study the computation and communication costs and their possible trade-offs in existing constructions for private information retrieval (PIR), including schemes based on homomorphic encryption and the Gentry--Ramzan PIR (ICALP'05). We present MulPIR, a PIR construction which uses somewhat homomorphic encryption in a new way that provides a better trade-off between communication and computation, and for the first time enables the implementation of PIR with full recursion. Our construction leverages optimizations from SealPIR (S&P'18) and extends them with new packing and compression techniques. We also present improvements for the Gentry--Ramzan PIR that reduce significantly the computation cost, the main overhead for this scheme, which achieves optimal communication in several settings. We further show how to efficiently construct PIR for sparse databases. Our constructions support batching for multi-queries as well as symmetric PIR. We finally implement several PIR constructions and present a comprehensive comparison of their communication and computation overheads, as well as a cost analysis assuming a standard price setting for CPU power and bandwidth.