|Cryptography and Information Security Group: Private
This pages presents research results relating to
private information retrieval that have been discovered in the
Cryptography and Information
Security Group of
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
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
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
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
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin.
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
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
Computationally Private Information Retrieval With Polylogarithmic
Christian Cachin, Silvio Micali, and Markus Stadler. Eurocrypt 99.
Back to CIS Home Page