Private Information Retrieval
Private Information Retrieval (PIR) protocols 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 protocols
aim at achieving this goal efficiently, where the main cost measure is
communication complexity. PIR is a strong primitive,
which may also be useful as a building block within other protocols.
A. Beimel, Y.
T. Malkin, and
functions are essential for single-server private information retrieval.
In Proc. of the 31st Annu. ACM Symp. on the Theory of Computing (STOC),
pages 89-98, 1999.
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 minimal assumption necessary for single database
PIR with sublinear communication complexity. We prove that if there is a
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. Similar results hold
(but requires more work) even if we allow the retrieval to fail with
Ishai, and T. Malkin.
Reducing the Servers Computation in Private Information Retrieval: PIR
with Preprocessing (ps),
2000, vol. 1880 of LNCS, pages 56-74. Springer, 2000.
In all previous private information retrieval protocols the servers'
computation for each retrieval is at least linear in
the size of entire database, even if the user requires just one bit.
In this paper, we study the computational complexity of PIR.
We show that in the standard PIR model, where the servers hold
only the database, linear computation cannot be avoided.
To overcome this problem we propose the model of
PIR with preprocessing:
Before the execution of the protocol each server may
compute and store polynomially-many
information bits regarding the database;
later on, this information should enable the servers to answer
each query of the user with more efficient computation.
We demonstrate that preprocessing can significantly save work
by presenting protocols with various tradeoff between communication,
computation, and space.
We also suggest two alternative models to
saving computation, by batching queries and by allowing a
separate off-line interaction per future query.
A. Beimel and
Ishai. Information-Theoretic Private Information Retrieval: A Unified
Colloquium on Computational Complexity, TR01-15, 2001. Extended abstract
in: ICALP 2001, volume 2076 of LNCS, pages 89-98, 2001. (ps),
This work addresses the information-theoretic setting for PIR, in
which the user's privacy should be unconditionally protected
from collusions of servers.
We present a unified general construction, whose abstract components
can be instantiated to yield both old and new families of PIR
protocols. A main ingredient in the new protocols is a generalization
of a solution by Babai, Kimmel, and Lokam to a communication
in the so-called simultaneous messages model.
Our construction strictly improves upon previous
constructions and resolves some previous anomalies. In
particular, we obtain: (1) Efficient
t-private k-server PIR protocols; (2)
a constant-factor improvement in the communication complexity of
1-private 2-server PIR, providing the first improvement to the 2-server case
since PIR protocols were introduced; and (3) efficient PIR protocols with
logarithmic query length. The latter protocols have applications to
the construction of efficient families of
locally decodable codes over large
alphabets and to PIR protocols with reduced work by the
Ishai, E. Kushilevitz,
and J. F. Raymond.
Barrier for Information-Theoretic
Private Information Retrieval.
In Proc. of the 43rd IEEE Symposium on Foundations of Computer
Science (FOCS), 2002. To appear.
Prior to this work, the best k-server private information
retrieval protocols had complexity
for any fixed k
Since then several methods were developed in an attempt to beat this
bound, but magically all these methods obtained the same
In this work, this barrier is finally broken and the
complexity of information-theoretic k-server PIR is
significantly improved to
The new PIR protocols can also be used to construct k-query
locally decodable codes with length
over a binary alphabet,
compared to in previously
The improvements presented in this paper apply even for small values of k:
the PIR protocols are more efficient than previous ones
for every k > 2,
and the locally decodable codes are
shorter for every k >3.
A. Beimel and Y. Stahl.
Robust Information-Theoretic Private Information Retrieval.
In Proc. of the 3rd Conference on Security in Communication Networks,
The definition of PIR protocols raises a simple question - what
happens if one of the servers crashes during the operation? How
can we devise a protocol which still works in the presence of
crashing servers? Current systems do not guarantee availability of
servers at all times for many reasons - crash of server,
Our purpose is to design
robust PIR protocols, i.e., protocols which still work correctly
even if only some of the servers are available during the
protocol's operation (the user does not know in advance which
servers are available). We present various robust PIR protocols
giving different tradeoffs between the different parameters.