Bibliography

1

M. Abadi, J. Feigenbaum, and J. Killian.
On hiding information from an oracle.
Journal of Computer and System Sciences, 39, 1989.

2

A. Ambainis.
Upper bound on the communication complexity of private information retrieval.
In Proceedings of the 24th International Colloquium on Automata, Languages and Programming ICALP 1997, Bologna, Italy, pages 401-407, 1997.

3

D. Beaver and J. Feigenbaum.
Hiding instances in mulit-oracle queries.
In Proc. of the 7th Sym. on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, pages 37-48, Berlin, 1990. Springer-Verlag.

4

D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway.
Locally random reductions: improvements and applications.
Journal of Cryptology, 10, 1997.
Earlier version in 1990 CRYPTO.

5

R. Beigel, L. Fortnow, and W. Gasarch.
A nearly tight lower bound for restricted private information retrieval protocols.
Computational Complexity, 15(1):82-91, 2006.
Also a 2003 TR03-087 at www.ecc.uni-trier.de/eccc/.

6

A. Beimel and Y. Ishai.
Information retrieval private information retrieval: A unified construction.
In ICALP01, 2001.
Also in ECCCTR, 2001. Was later subsumed by General constructions for information-theoretic private information retrieval by Beimel, Ishai, and Kushilevitz, http://www.springerlink.com.

7

A. Beimel, Y. Ishai, and E. Kushilevitz.
General constructions for information-theoretic private information retrieval, 2003.
Unpublished manuscripte available at www.cs.bgu.ac.il/~beimel/pub.html.

8

A. Beimel, Y. Ishai, E. Kushilevitz, and T. Malkin.
One-way functions are essential for single-server private information retrieval.
In Proceedings of the Thirty-first Annual ACM Symposium on the Theory of Computing, Atlanta GA, 1999.

9

A. Beimel, Y. Ishai, E. Kushilevitz, and J.-F. Rayomnd.
Breaking the $o(n^{1/(2k-1)})$ barrier for information-theoretic private information retrieval.
In Proceedings of the 43nd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, pages 261-270, 2002.

10

A. Beimel, Y. Ishai, and T. Malkin.
Reducing the servers' computation in private information retrieval: Pir with preprocessing.
Journal of Cryptology, 20, 2000.
Prelim version was in CRYPTO00.

11

A. Beimel and Y. Stahl.
Robust information-theoretic private information retrieval.
In Proceedings of the 3rd conference on security in Communications networks, pages 326-341, 2002.

12

G. Blakely and C. Meadows.
A database encryption scheme which allows computation of statistics using encrypted data.
In Proceedings of the Symposium on Security and Privacy, pages 116-122, 1985.

13

C. Blundo, P. DArco, and A. DeSantis.
A $t$-private $k$-database information retrieval scheme.
International Journal of Information Security, 1(1):64-68, 2001.

14

Boneh, Kushilevitz, Ostrovsky, and Skeith.
Public key encryption that allows PIR queries, 2006.
http://eprint.iacr.org/2007/073.

15

C. Cachin, S. Micali, and M. Stadler.
Computationally private information retrieval with polylog communication.
In EUROCRYPT99, pages 402-414, 1999.

16

B. Chor and N. Gilboa.
Computationally private information retrieval.
In Proceedings of the Twenty-ninth Annual ACM Symposium on the Theory of Computing, El Paso TX, pages 304-313, 1997.

17

B. Chor, N. Gilboa, and M. Naor.
Private information retrieval by keywords, 1998.
Unpublished manuscripte available at www.cs.technion.ac.il/~gilboa.

18

B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan.
Private information retrieval.
In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, Milwaukee WI, pages 41-50, 1995.
We are using the conference version since the item referenced did not appear in the journal version.

19

B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan.
Private information retrieval.
Journal of the ACM, 45:965-981, 1998.
Earlier version in FOCS 95.

20

A. K. D. Bleichenbacher and M. Yung.
Decoding of interleaved Reed-Solomon codes over noisy data.
In ICALP03, 2003.

21

G. DiCrescenzo, Y. Ishai, and R. Ostrovsky.
Universal service-providers for private information retrieval.
Journal of Cryptology, 14(1), 2001.
Earlier Version in PODS 1998.

22

J. Feigenbaum.
Encrypting problem instances, or, ... can you take advantage of someone without having to trust him?
In Advances in Cryptology: Proceedings of CRYPTO '85, Santa Barbara CA, pages 477-488, 1985.

23

Gentry and Ramzan.
Single-database private information retrieval with constant communication rate.
In ICALP05, 2005.

24

Y. Gertner, S. Goldwasser, and T. Malkin.
A random server model for private information retrieval or information theoretic pir avoiding database replication.
In Proc. of the 2nd RANDOM, 1998.

25

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin.
Protecting data privacy in private information retrieval schemes.
Journal of Computer and System Sciences, 60, 2000.
Prelimary version in STOC98.

26

O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan.
Lower bounds for linear local decodable codes and private information retrieval systems.
In Proceedings of the 17th IEEE Conference on Complexity Theory, Montreal, Canada, pages 175-183. IEEE Computer Society Press, 2002.
Updated version on Goldreich's website.

27

Y. Ishai and E. Kushilevitz.
Improved upper bounds on information-theoretic private information retrieval.
In Proceedings of the Thirty-first Annual ACM Symposium on the Theory of Computing, Atlanta GA, 1999.
Part of the paper General constructions for information-theoretic private information retrieval by Beimel, Ishai, and Kushilevitz.

28

T. Itoh.
Efficient private information retrieval.
IEICE Trans. Fundamentals, ES2-A(1), 1999.

29

T. Itoh.
On lower bounds for the communication complexity of private information retrieval.
IEICE Trans. Fundamentals, ES4-A(1), 2001.
This journal is at http://search.ieice.org/2001/index.htm.

30

I. Kerenidis and R. de Wolf.
Exponential lower bound for 2-query locally decodable codes.
Journal of Computer and System Sciences, pages 395-420, 2004.
Earlier version in STOC03. Electronic version at http://arxiv.org/abs/quant-ph/0208062.

31

A. Kiayias and M. Yung.
Secure games with polynomial expressions.
In ICALP01, 2001.

32

E. Kushilevitz and R. Ostrovsky.
Replication is not needed: Single database, computationally-private information retrieval (extended abstract).
In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach FL, pages 364-373, 1997.

33

E. Kushilevitz and R. Ostrovsky.
One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval.
In EUROCRYPT00, 2000.

34

H. Lipmaa.
An oblivious transfer protocol with log-squared total communication.
In The 8th Information Security Conference (ISC'05), pages 314-328, 2005.
See http://eprint.iacr.org/2004/063/ or Lipmann's website.

35

E. Mann.
Private access to distributed information.
Masters Thesis from Technion - Israel Institute of Technology, Haifa, 1998.

36

S. Mishra.
Symmetrically private information retrieval.
Available at citeseer.nj.nec.com/kumarmishra00symmetrically.html.

37

M. Naor and B. Pinkas.
Oblivious transfer with adaptive queries.
Advances in Cryptology: Proceedings of CRYPTO '99, Santa Barbara CA, 1999.

38

K. Obata.
Optimal lower bounds for 2-query locally decodable linear codes.
In Proc of the 6th workshop no Randomization and Approximation, 2002.

39

Razborov and Yekhanin.
An $\omega(n^{1/3})$ lower bound for bilinera group based private information retrieval.
In FOCS06, 2006.
Also on ECCC website.

40

R. Rivest, L. Adelman, and M. Dertouzos.
On databanks and privacy homomorphism.
In D. et al, editor, Foundations of secure computation, pages 168-177, 1978.

41

R. Sion and B. Carbunar.
On the computational practicality of private information retrieval.
In NDSS, 2007.

42

J. Stern.
A new and efficient all-or-nothing disclosure of secrets protocol.
In Asia Crypt 1998 (LNCS 1514)), pages 357-371, 1998.

43

M. Sudan and D. Coppersmith.
Reconstructing curves in three (and higher) dimensional spaces from noisy data.
Proceedings of the Thirty-fifth Annual ACM Symposium on the Theory of Computing, San Diego CA, 2003.

44

P. Williams and R. Sion.
Usable pir.
In NDSS, 2008.

45

D. Woodruff and S. Yekhanin.
A geometric approach to information-theoretic private information retrieval.
In Complexity05, 2005.
Available at web.mit.edu/dpwood/www/wy.pdf.

46

A. Yamamura and T. Saito.
Private information retrieval based on subgroup membership problem.
In Proc. of the 6th Australasian Conf., ACISP 2001, 2001.

47

Yekhanin.
New locally decodable codes and private information retrieval schemes, 2006.
See ECCC TR06-127, at eccc.hpi-web.de/eccc-reports/2006/TR06-127/index.html.