Advisor: Yuval Ishai

Private Information Retrieval deals with how to query a database securely. By secure, I mean that the database cannot determine, even partially, what the user is interested in. Today, this is accomplished by simply having user download the entire database. Though completely secure, this solution is not very efficient in terms of communication. Several schemes hav been developed in which the user queries multiple copies of the same database and recieves information from which s/he can reconstruct the answer to the query.

To study this problem mathematically, we make it simpler. First, we assume that the database is just a binary string. This is not a bad assumption, since anything can be encoded in a binary string assuming that there is an agreed upon encoding system. Next, we assume that the user is querying a single bit. Now this isn't very realistic, but the user's real interest could be seen as a sequence of single bit queries, so any method developed for single bit queries will work for longer ones.