Private Information Retrieval (PIR)

Informally, the problem of PIR studies how to access a record from a server without the server knowing what record is being retrived. Formally, the problem is defined as follows: the server has a binary string (X^n) of length n and the user wants to retrieve the Yth bit X_Y in such a way that the server does not learn Y at all. In this talk, we will prove optimality (communication complexity) of a trivial scheme where the server sends the whole string to the user. A better scheme is possible if we replicate the same string in two servers and we will see such a scheme. We also discuss a variant of PIR, called symmetric PIR, where we put one more constraint that the user also shouldn't learn anything about the database other than the output. We will prove that for any number k>=1 of servers, if no two servers communicate, then symmetric PIR can't be done.