Ostrovsky scheme that relies on the
standard hardness assumption15—the
“quadratic residuosity assumption.”
Let m be a positive integer. A num-
ber a is called a “quadratic residue,”
or QR, modulo m, if there exists an
integer x such that x2 = a mod m. Oth-
erwise, a is called a “quadratic non-
residue,” or QNR, modulo m. The QR
assumption states that it is computa-
tionally hard to distinguish numbers
that are QRs modulo m from those
that are not, unless one knows the fac-
torization of m.
The protocol. The server stores the
n-bit database x in a square matrix of
size s by s for s = √n.
x11…x1j…x1s
xi1…xij…xis
xs1…xsj…xss
...
...
...
...
...
...
a1
bi
as
...
...
Suppose the database user is interested in obtaining the value xij for
some i, j between 1 and s. The user
would select a large integer m together
with its factorization at random and
generate s – 1 random QRs a1,…,ai– 1,
ai+ 1,…,as modulo m, as well as a single
random QNR bi. The user would then
send the string a1,…,ai− 1, bi, ai+ 1,…,as
and the integer m to the server.
The QR assumption implies that
the server cannot distinguish bi from
integers {al} and thus observes only
a string of s random-looking integers
u1,…,us modulo m (one per each row
of the database). The server responds
with s integers p1,…, ps (one per each
column of the database). Here each ph
is equal to a product of integers ul for all
l such that xlh = 1; formally, ph = ∏l | xlh= 1 ul
mod m.
Verifying that the value of pj is going to be a QR modulo m if xij = 0 and
is going to be a QNR modulo m is not
hard if xij = 1, since a product of two
QRs is a QR and the product of a QR
with a QNR is a QNR. The user need
only check whether pj is a QR, which is
easy, since the user knows the factorization of m.
The total amount of communication in this PIR scheme is roughly O(
√n). Better protocols are available; see
Gentry and Ramzan10 and Lipmaa16
for the most efficient computational
PIR schemes.
Conclusion
With nearly 15 years of development,
the PIR field has grown large and deep,
with many subareas and connections
to other fields. For more details, see
Ostrovsky and Sketch17 for a survey of
computational PIR and Trevisan20 and
Yekhanin25 for a survey of information
theoretic PIR; see also Gasarch. 9
Here, we have concentrated on a
single (the most studied) aspect of
PIR schemes—their communications
complexity. Another important aspect
of PIR schemes is the amount of computation servers must perform in order to respond to user queries. 5, 11, 23 We
are hopeful that further progress will
lead to the wide practical deployment
of these schemes.
Acknowledgments
We would like to thank Martin Abadi,
Alex Andoni, Mihai Budiu, Yuval Ishai,
Sumit Nain, and Madhu Sudan and
the anonymous referees for helpful
comments regarding this article.
References
1. ambainis, a. Upper bound on the communication
complexity of private information retrieval. In
Proceedings of the Automata, Languages and
Programming, 24th International Colloquium LNCS
1256 (bologna, Italy, July 7–11). springer, 1997,
401–407.
2. babai, L., Fortnow, L., Levin, L., and szegedy, M.
Checking computations in polylogarithmic time. In
Proceedings of the 23rd Annual ACM Symposium on
Theory of Computing (new orleans, La, May 5–8).
aCM Press, new york, 1991, 21–31.
3. beimel, a., Ishai, y., and Kushilevitz, e. general
constructions for information-theoretic private
information retrieval. Journal of Computer and
System Sciences 71, 2 (2005), 213–247.
4. beimel, a., Ishai, y., Kushilevitz, e., and raymond,
J.F. breaking the O(n1/(2k− 1)) barrier for information-theoretic private information retrieval. In
Proceedings of the 43rd Symposium on Foundations
of Computer Science (Vancouver, b.C., nov. 16–19).
Ieee Computer society, 2002, 261–270.
5. beimel, a., Ishai, y., and Malkin, t. reducing the
servers’ computation in private information retrieval:
PIr with preprocessing. In Proceedings of the 20th
Annual International Cryptology Conference LNCS
1880 (santa barbara, Ca, aug. 20–24). springer,
2000, 55–73.
6. Cachin, C., Micali, s., and stadler, M. Computationally
private information retrieval with polylogarithmic
communication. In Proceedings of the International
Conference on the Theory and Application of
Cryptographic Techniques LNCS 1592 (Prague, Czech
republic, May 2–6). springer, 1999, 402–414.
7. Chor, b., goldreich, o., Kushilevitz, e., and sudan, M.
Private information retrieval. Journal of the ACM 45,
6 (1998), 965–981.
8. efremenko, K. 3-query locally decodable codes of
subexponential length. In Proceedings of the 41st
Annual ACM Symposium on Theory of Computing
(bethesda, Md, May 31–June 2). aCM Press, new
york, 2009, 39–44.
9. gasarch, W. Web page on private information
retrieval; http://www.cs.umd.edu/ gasarch/pir/pir.
html
10. gentry, C. and ramzan, Z. single-database private
information retrieval with constant communication
rate. In Proceedings of the 32nd International
Colloquium on Automata, Languages and
Programming LNCS 3580 (Lisbon, Portugal, July
11–15). springer, 2005, 803–815.
Sergey Yekhanin ( yekhanin@microsoft.com) is
a researcher in Microsoft research silicon Valley,
Mountain View, Ca.
