עמוס ביימל

The computational complexity of private information retrieval (PIR) was studied. It was shown that in the standard PIR model, where the servers hold only the database, linear computation cannot be avoided. Substantial savings in the amount of computation without severely affecting the communication complexity are obtained by using preprocessing in PIR protocols. Two alternative models to saving computation, by batching queries and by allowing a separate off-line interaction per future query were suggested.