Peer-to-Peer Private Information Retrieval

Private information retrieval (PIR) is normally modeled as a game between two players: a user and a database. The user wants to retrieve some item from the database without the latter learning which item. Most current PIR protocols are ill-suited to provide PIR from a search engine or large database: i) their computational complexity is linear in the size of the database; ii) they assume active cooperation by the database server in the PIR protocol. If the database cannot be assumed to cooperate, a peer-to-peer user community is a natural alternative to achieve some query anonymity: a user submits a query on behalf of another user in the community. A peer-to-peer PIR system is described in this paper which relies on an underlying combinatorial structure to reduce the required key material and increase availability.