A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol

Abstract

Picture the following scenario. Alice is looking for gold in California. What Alice does is look for a place with a little gold and follow the trace. Now, Alice wants to find gold in a place where no mining patent has been awarded, but many patents have been awarded in California during the gold rush. What Alice does is to walk around California with a GPS and a notebook computer. When ever she finds a trace of gold she follows it querying if any patent has been awarded in that location. If she finds a trace of gold in a piece of land with no issued patent she can request the patent and start mining for gold. The problem is that she is worried that Bob's Mining Patents Inc., the services he queries the patents from, might cheat on her. Because Bob's knows she is looking for gold in California (Alice said so when signing up for Bob's service), he knows that, if she queries from some location, then there is gold there. So, if she queries a location and there is no patent awarded, Bob may run to the patent office and get the mining patent for that location. Depending on privacy and economic constraints, a few solutions come to mind. Alice might buy from Bob the whole database for California. Alice then can make all the queries to her own database, and Bob will never find out where Alice is looking for gold. But this might be very expensive, because Bob charges per query; what he charges for the whole database will probably be more than what Alice is willing to pay. Alice can also, with each query, perform a collection of fake queries so that Bob can't figure out which is the real query (this leaks information unless she queries the whole database!), but that still makes Alice pay for more queries that she would like. This Alice-and-Bob scenario is a basic motivation for Private Information Retrieval: a family of two-party protocols in which one of the parties owns a database, and the other wants to query it with certain privacy restrictions and warranties. Since the PIR problem was posed, different approaches to its solution have been pursued. In the following sections, we will present the general ideas of the variations and proposed solutions to the PIR problem. Then, we will present a collection of basic protocols that allow the implementation of a general-purpose PIR protocol. Finally, we will show details of a particular PIR protocol we have implemented.

Back to publications
Back to previous page