Private Information Retrieval

This pages presents research results relating to private information retrieval that have been discovered in the Cryptography and Information Security Group of MIT's Lab for Computer Science.

Private Information Retrieval (PIR) schemes allow users to retrieve information from a database while keeping their query private. Motivating examples for this problem include databases with sensitive information, such as stocks, patents or medical databases, in which users are likely to be highly motivated to hide which record they are trying to retrieve. PIR schemes aim at achieving this goal efficiently, where the main cost measure has traditionally been the communication complexity. PIR is a strong primitive, which may also be useful as a building block within other protocols.

Protecting Data Privacy in Private Information Retrieval Schemes. Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Postcript of conference version (STOC 98); Postcript of journal version (draft). 

In this paper we introduce the model of Symmetrically Private Information Retrieval (SPIR), where the privacy of the database, as well as of the user, is guaranteed. That is, in every invocation of a SPIR scheme, the user learns only a single record and no other information about the data. Clearly, data privacy is a natural and crucial requirement in commercial applications where the database charges users by the amount of data they retrieve. We show how to transform PIR schemes into SPIR schemes with information theoretic privacy, paying only a constant factor in communication complexity. To this end, we introduce a new primitive, conditional disclosure of secrets, which may also be of independent interest for the design of other cryptographic protocols. Since the SPIR problem is equivalent to the cryptographic primitive oblivious transfer, our results yield the first 1-round implementation of a distributed version of oblivious transfer with information theoretic security and sublinear communication complexity. 



A Random Server Model for PIR. Yael Gertner, Shafi Goldwasser, and Tal Malkin. RANDOM 98 (Postcript) 

In this paper we introduce a new model for PIR (alternatively, SPIR), utilizing auxiliary servers providing privacy services for database access. Consequently, privacy and efficiency problems which are inherent in all previous PIR solutions, rendering them impractical, may be removed using our model. Specifically, we construct PIR protocols with information theoretic privacy which do not require replication of the data (the auxiliary servers only hold random strings, and cannot gain any information about the data or the user). Thus, we protect the database from having to distribute its data to untrusted parties. Moreover, our protocols are extremely efficient in terms of database computation, requiring only constant computation per query, as opposed to linear computation in previous solutions. The computational load is transferred to the special-purpose auxiliary servers. 


One-way Functions are Essential for Single-Server Private Information Retrieval. Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. STOC 99. (Postcript) 

Single database PIR with sublinear communication complexity cannot be achieved in the information theoretic model, so some computational assumptions must be made. Previous work consists of presenting specific computational assumptions under which such schemes can be constructed, such as quadratic residuosity (Kushilevitz-Ostrovsky), or the Phi-hiding assumption (Cachin-Micali-Stadler). A major question which we address in this work is what assumption is the minial assumption necessary for single database PIR with sublinear communication complexity. We prove that if there is a (0-error) PIR protocol in which the server sends less than $n$ bits then one-way functions exist (where n is the number of bits in the database). That is, even saving one bit compared to the naive protocol, in which the entire database is sent, already requires one-way functions. The same result holds (but requires more work) even if we allow the retrieval to fail with probability of at most 1/(8n). Moreover, similar results hold even if we allow constant probability of error. For example, we prove that if there is a PIR protocol with error 1/4 and communication complexity less than $n/10$ bits, then one-way functions exist. 


Computationally Private Information Retrieval With Polylogarithmic Communication. Christian Cachin, Silvio Micali, and Markus Stadler. Eurocrypt 99.