Improved upper bounds on information-theoretic private information retrieval (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved upper bounds on information-theoretic private information retrieval (extended abstract)

Full text

Pdf (777 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: 79 - 88

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Yuval Ishai	Department of Computer Science, Technion, Haifa 32000, Israel
Eyal Kushilevitz	IBM T.J. Watson Research Center, and Department of Computer Science, Technion

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 23, Citation Count: 6

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.301275 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	D. Beaver and A. Wool Quorum-based secure multiparty computation. In Proc. of EUROCRYPT'98, LNCS 1403, Springer Verlag, pages 375-390, 1998.
	6	Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, One-way functions are essential for single-server private information retrieval, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.89-98, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301277]
	7	C. Cachin, S.Micali, and M. StaAler. Computationslly private information retrieval with polylogarithrnic communication. In Advancez in CrFptolog~l - E UROCR YPT '99, 1999.
	8	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]
	9	B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
	10	R. Cramer, I. Damgard, and U. Maurer. Span programs and secure general multiparty computation. BKICS Report Series, B.S-97-28, 1997. Available from http://www.bdcs.dk.
	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	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
	13	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]
	14	M. Ito, A. Saito, and T. Nishizeki. Secret sharing schemes realizing general access structures. In Proc. IEEE Global Telecommunication Conf., Globecorn 87, pages 99-102, 1987.
	15	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
	16	E. Mann. Private access to distributed in~ormation. Master's thesis, Technion- Israel Institute of Technology, Haifa, 1998.
	17	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]
	18	Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]

CITED BY 6

	Ran Canetti , Yuval Ishai , Ravi Kumar , Michael K. Reiter , Ronitt Rubinfeld , Rebecca N. Wright, Selective private function evaluation with applications to private statistics, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.293-304, August 2001, Newport, Rhode Island, United States
	Wenliang Du , Mikhail J. Atallah, Secure multi-party computation problems and their applications: a review and open problems, Proceedings of the 2001 workshop on New security paradigms, September 10-13, 2001, Cloudcroft, New Mexico
	Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, One-way functions are essential for single-server private information retrieval, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.89-98, May 01-04, 1999, Atlanta, Georgia, United States
	Wenliang Du , Zhijun Zhan, A practical approach to solve Secure Multi-party Computation problems, Proceedings of the 2002 workshop on New security paradigms, September 23-26, 2002, Virginia Beach, Virginia
	Keith B. Frikken , Mikhail J. Atallah, Privacy preserving electronic surveillance, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC
	Amos Beimel , Yuval Ishai , Eyal Kushilevitz, General constructions for information-theoretic private information retrieval, Journal of Computer and System Sciences, v.71 n.2, p.213-247, August 2005