One-way functions are essential for single-server private information retrieval

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

One-way functions are essential for single-server private information retrieval

Full text

Pdf (790 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 89 - 98

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Amos Beimel	Division of Engineering and Applied Science, Harvard University, 40 Oxford St., Cambridge, MA
Yuval Ishai	Computer Science Department, Technion, Haifa 32000, Israel
Eyal Kushilevitz	IBM T.J. Watson Research Center, and Computer Science Department, Technion, Haifa, Israel
Tal Malkin	Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology sq., Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 29, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301277 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Abadi , J. Feigenbaum , J Kilian, On hiding information form an oracle, Journal of Computer and System Sciences, v.39 n.1, p.21-50, Aug. 1989 [doi>10.1016/0022-0000(89)90018-4]
	2	Andris Ambainis, Upper Bound on Communication Complexity of Private Information Retrieval, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.401-407, July 07-11, 1997
	3	Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
	4	Donald Beaver , Joan Feigenbaum , Joe Kilian , Phillip Rogaway, Security with Low Communication Overhead, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.62-76, August 11-15, 1990
	5	C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology- EUROCRYPT '99, 1999. To appear.
	6	Benny Chor , Niv Gilboa, Computationally private information retrieval (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.304-313, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258609]
	7	Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
	8	Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998 [doi>10.1145/293347.293350]
	9	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	10	Claude Crépeau, Equivalence Between Two Flavours of Oblivious Transfers, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.350-354, August 16-20, 1987
	11	Giovanni Di-Crescenzo , Yuval Ishai , Rafail Ostrovsky, Universal service-providers for database private information retrieval (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.91-100, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277713]
	12	G. Di Crescenzo, T. Malkin, and R. Ostrovsky. Singledatabase private information retrieval implies oblivious transfer. Manuscript, November, 1998.
	13	Yael Gertner , Shafi Goldwasser , Tal Malkin, A Random Server Model for Private Information Retrieval or How to Achieve Information Theoretic PIR Avoiding Database Replication, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.200-217, October 08-10, 1998
	14	Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.151-160, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276723]
	15	O. Goldreich, A note on computational indistinguishability, Information Processing Letters, v.34 n.6, p.277-281, May 1990 [doi>10.1016/0020-0190(90)90010-U]
	16	O. Goldreich. Foundations of Cryptography (}ragments of a book). Electronic Colloquium on Computational Complexity, 1995. Electronic publication: http://www.eccc.uni-trier.de/eccc-local/ECCC- Books / eccc- books, h tml.
	17	S. Goldwasser and S. Micali. Probabilistic encryption. J. of Computer and System Sciences, 28(21):270-299, 1984.
	18	J. Hasted, R. Impagliazzo, L. A. Levin, and M. Luby. Construction of a pseudo-random generator from any one-way function. Technical Report TR-91-068, International Computer Science Institute, 1991.
	19	R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography. In Proc. of the 30th Annu. IEEE Syrup. on Foundations of Computer Science, pages 230-235, t989.
	20	R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
	21	Yuval Ishai , Eyal Kushilevitz, Improved upper bounds on information-theoretic private information retrieval (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.79-88, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301275]
	22	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	23	E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
	24	Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
	25	E. Mann. Private access to distributed information. Master's thesis, Technion - Israel Institute of Technology, Halls, 1998.
	26	M. N a or. Bit commitment using pseudorastdom generators. J. of Cryptology, 4:I51-158, 1991.
	27	Rafail Ostrovsky , Victor Shoup, Private information storage (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.294-303, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258606]
	28	R. Ostrovsky and A. Wigderson. One-way functions are essential for non-trivial zero-knowledge. In ~nd Israel Syrup. on Theory of Computing and Systems, pages 3- 17, 1993.
	29	M. O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard Aiken Computation Laboratory, 1981.
	30	J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]
	31	A. (3. Yao. Theory and application of trapdoor func~ tions. In Proc. of the ~3th Annu. IEEE Syrup. on Foundations of Computer Science, pages 80-91, 1982.

CITED BY 7

	Hua Wang , Jinli Cao , Yanchuan Zhang, Ticket-based service access scheme for mobile users, Australian Computer Science Communications, v.24 n.1, p.285-292, January-February 2002
	Yuval Ishai , Eyal Kushilevitz, Improved upper bounds on information-theoretic private information retrieval (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.79-88, May 01-04, 1999, Atlanta, Georgia, United States
	David Woodruff , Jessica Staddon, Private inference control, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA
	Hua Wang , Lili Sun , Yanchun Zhang , Jinli Cao, Anonymous access scheme for electronic-services, Proceedings of the 27th Australasian conference on Computer science, p.295-304, January 01, 2004, Dunedin, New Zealand
	Ping Lin , K. Selçuk Candan, Enabling access-privacy for random walk based data analysis applications, Data & Knowledge Engineering, v.63 n.3, p.667-683, December, 2007
	Hua Wang , Yanchun Zhang , Jinli Cao , Yahiko Kambayahsi, A Global Ticket-Based Access Scheme for Mobile Users, Information Systems Frontiers, v.6 n.1, p.35-46, March 2004
	Moni Naor , Guy N. Rothblum, The complexity of online memory checking, Journal of the ACM (JACM), v.56 n.1, p.1-46, January 2009