Abstract

We show that in any PIR (Private Information Retrieval) protocol without pre-processing, a server must perform a nearly linear number of public-key operations (in the size of the database), regardless of the number of symmetric-key operations. We will discuss the implications of this result for the communication complexity of oblivious transfer (OT) extension.