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 various constructions for private information retrieval (PIR), including schemes based on homomorphic encryption (HE) and the Gentry--Ramzan PIR (ICALP'05). First, we introduce new packing and compression techniques which extend the construction of SealPIR (S&P'18), and reduce the communication bandwidth by 70% while preserving essentially the same computation cost. We then present MulPIR, a PIR construction based on homomorphic encryption, which leverages multiplicative homomorphism rather than layered additive homomorphism to implement the recursion steps in PIR. This reduces communication even further, at the cost of an increased computational cost for the server. In particular it eliminates the exponential dependence of PIR communication on the recursion depth due to the ciphertext expansion. Therefore, as a side result, we obtain the first implementation of PIR with full recursion. On the other end of the communication--computation spectrum, we take a closer look at Gentry--Ramzan PIR, a scheme with asymptotically optimal communication rate. Here, the bottleneck is the server's computation, which we manage to reduce significantly. Our optimizations enable a tunable trade-off between communication and computation, which allows us to reduce server computation by as much as 85%, at the cost of an increased query size. We further show how to efficiently construct PIR for sparse databases. Our constructions support batched queries, as well as symmetric PIR. We implement all of our PIR constructions, and compare their communication and computation overheads with respect to each other and previous work for several application scenarios.