Oblivious transfer and polynomial evaluation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Oblivious transfer and polynomial evaluation

Full text

Pdf (956 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: 245 - 254

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Moni Naor	Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
Benny Pinkas	Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 33, Downloads (12 Months): 220, Citation Count: 44

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.301312 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	Donald Beaver, Foundations of Secure Interactive Computing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.377-391, August 11-15, 1991
	2	Mihir Bellare , Silvio Micali, Non-interactive oblivious transfer and applications, Proceedings on Advances in cryptology, p.547-557, July 1989, Santa Barbara, California, United States
	3	Steven M. Bellovin , Michael Merritt, Encrypted Key Exchange: Password-Based Protocols SecureAgainst Dictionary Attacks, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.72, May 04-06, 1992
	4	Gilles Brassard, Modern cryptology, Springer-Verlag New York, Inc., New York, NY, 1988
	5	G. Brassard, C. Cr~peau and J.-M. Robert Information Theoretic Reduction Among Disclosure Problems, 27th FOCS, pp. 168-173, 1986.
	6	Gilles Brassard , Claude Crépeau , Jean-Marc Robert, All-or-nothing disclosure of secrets, Proceedings on Advances in cryptology---CRYPTO '86, p.234-238, January 1987, Santa Barbara, California, United States
	7	G. Brassard, C. Cr~peau and M. Santha, Oblivious T~nsfer and Intersecting Codes, IEEE Trans. on Inform. Theory, Vol. 42(6), pp. 1769-I780, 1996.
	8	Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Proceedings of the seventh international conference on World Wide Web 7, p.379-388, April 1998, Brisbane, Australia
	9	C. Cachin, On the foundations of oblivious transfer, Advances in Cryptology- Eurocrypt '98, LNCS 1403, pp. 361- 374. Springer-Vertag, 1998.
	10	C. Cachin, S. Micali and M. Stadler, Computationaily Private Information Retrieval With Polylogarithmic Communication, Advances in Cryptology - Eurocrypt '99, LNCS, Springer-Verlag, 1999.
	11	It. Canetti, SecuritF and Composition of Multiparty Crypgographic Protocols, manuscript, 1998.
	12	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
	13	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
	14	C. Cr~peau and J. Kilian, Achieving oblivious transfer using weakened security assumptions, FOGS '88, pp. 42-52, I988.
	15	Alfredo De Santis , Yvo Desmedt , Yair Frankel , Moti Yung, How to share a function securely, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.522-533, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195405]
	16	W. Diffie and M. Hellman, New directions in crypto~raphF, IEEE Trans. Inform. Theory, vol. 22(6), pp. 644-654, 1976.
	17	P. Elias, List decoding for noisy channels, TR 335, Research Laboratory for Electronics, MIT, 1957.
	18	Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
	19	Ronald Fagin , Moni Naor , Peter Winkler, Comparing information without leaking it, Communications of the ACM, v.39 n.5, p.77-85, May 1996 [doi>10.1145/229459.229469]
	20	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]
	21	O. Goldreich, Foundations of Cryptography (Fragments of a Book), 1995. Electronic publication: http://~r~, eccc. uni-trier, de/eccc/inf o/E~CC-B ooka (Electronic Colloquium on Computational Complexity).
	22	O. Goldreich, Secure Multi-Party Computation (working draft) Version 1. l, 1998.
	23	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	24	O. Goldreich , R. Rubinfeld , M. Sudan, Learning polynomials with queries: The highly noisy case, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.294, October 23-25, 1995
	25	Oded Goldreich , Ronen Vainish, How to Solve any Protocol Problem - An Efficiency Improvement, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.73-86, August 16-20, 1987
	26	Venkatesan Guruswami , Madhu Sudan, Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.28, November 08-11, 1998
	27	R. Impagliazzo and M. Naor, Efficient Cryptographic schemes provably secure as subset sum, JournaJ of Cryptology, vol 9, pp. 199-216, 1996.
	28	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]
	29	Joe Kilian, Uses of randomness in algorithms and protocols, MIT Press, Cambridge, MA, 1990
	30	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
	31	Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
	32	Stefan Lucks, Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys, Proceedings of the 5th International Workshop on Security Protocols, p.79-90, April 07-09, 1997
	33	F. J. MacWilliams, N. Sloane. The Theory of Error Correcting Codes, North Holland, Amsterdam, 1977.
	34	S. Micali and P. Rogaway, Secure Computation, Advances in Cryptology- Crypto '91, pp. 392-404. LNCS 576, Springer- Verlag, 1992.
	35	M. N~or and B. Pinkas, Secure and Efficient Metering, Advances in Cryptology- Eurocrypt '98, LNCS 1403, Springer- Verlag, 1998.
	36	M. Naor and B. Pink~, Adaptive Oblivious 7bansj'er, manuscript, 1999.
	37	M. Naor , O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.170, October 23-25, 1995
	38	Moni Naor , Omer Reingold, On the construction of pseudo-random permutations: Luby-Rackoff revisited (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.189-199, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258581]
	39	M. Naor , O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.458, October 19-22, 1997
	40	M. O. Rabin, How to e~change secrets by oblivious transfer, Tech. Memo TR-81, Aiken Computation Laboratory, 1981.
	41	Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]
	42	Stephen Wiesner, Conjugate coding, ACM SIGACT News, v.15 n.1, p.78-88, Winter-Spring 1983 [doi>10.1145/1008908.1008920]
	43	A.C. Yao, How to Generate and Exchange Secrets, 27th FOGS, pp. 162-167, 1986.

CITED BY 44

	Maurizio Kliban Boyarsky, Public-key cryptography and password protocols: the multi-user case, Proceedings of the 6th ACM conference on Computer and communications security, p.63-72, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
	Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece
	Dan Boneh, Finding smooth integers in short intervals using CRT decoding, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.265-272, May 21-23, 2000, Portland, Oregon, United States
	Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
	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
	Bernardo A. Huberman , Matt Franklin , Tad Hogg, Enhancing privacy and trust in electronic communities, Proceedings of the 1st ACM conference on Electronic commerce, p.78-86, November 03-05, 1999, Denver, Colorado, 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
	Dan Boneh, Finding smooth integers in short intervals using CRT decoding, Journal of Computer and System Sciences, v.64 n.4, p.768-784, June 2002
	Yan-Cheng Chang , Chi-Jen Lu, Oblivious polynomial evaluation and oblivious neural learning, Theoretical Computer Science, v.341 n.1, p.39-54, 5 September 2005
	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
	Rakesh Agrawal , Alexandre Evfimievski , Ramakrishnan Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	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
	Sheng Zhong , Yang Richard Yang, Verifiable distributed oblivious transfer and mobile agent security, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.12-21, September 19, 2003, San Diego, CA, USA
	Wen-Guey Tzeng, Efficient 1-Out-of-n Oblivious Transfer Schemes with Universally Usable Parameters, IEEE Transactions on Computers, v.53 n.2, p.232-240, February 2004
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Batch codes and their applications, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Wakaha Ogata , Kaoru Kurosawa, Oblivious keyword search, Journal of Complexity, v.20 n.2-3, p.356-371, April/June 2004
	E. Aïmeur , G. Brassard , F. S. Mani Onana, Blind sales in electronic commerce, Proceedings of the 6th international conference on Electronic commerce, October 25-27, 2004, Delft, The Netherlands
	Hong-Da Li , Dong-Yao Ji , Deng-Guo Feng , Bao Li, Oblivious polynomial evaluation, Journal of Computer Science and Technology, v.19 n.4, p.550-554, July 2004
	Wenjun Luo , Xiang Li, A study of secure multi-party elementary function computation protocols, Proceedings of the 3rd international conference on Information security, November 14-16, 2004, Shanghai, China
	Hong-Da Li , Xiong Yang , Deng-Guo Feng , Bao Li, Distributed oblivious function evaluation and its applications, Journal of Computer Science and Technology, v.19 n.6, p.942-947, November 2004
	Moni Naor, Cryptography and mechanism design, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	Keith Frikken , Mikhail Atallah , Chen Zhang, Privacy-preserving credit checking, Proceedings of the 6th ACM conference on Electronic commerce, p.147-154, June 05-08, 2005, Vancouver, BC, Canada
	Benny Pinkas, Cryptographic techniques for privacy-preserving data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.12-19, December 2002
	Nan Zhang , Wei Zhao, Distributed privacy preserving information sharing, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Craig Gentry , Philip Mackenzie , Zulfikar Ramzan, Password authenticated key exchange using hidden smooth subgroups, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
	Hossein Ghodosi , Rahim Zaare-Nahandi, Comments on the 'm out of n oblivious transfer', Information Processing Letters, v.97 n.4, p.153-155, 28 February 2006
	Sheng Zhong , Yang Richard Yang, Verifiable distributed oblivious transfer and mobile agent security, Mobile Networks and Applications, v.11 n.2, p.201-210, April 2006
	M. Barni , C. Orlandi , A. Piva, A privacy-preserving protocol for neural-network-based computation, Proceeding of the 8th workshop on Multimedia and security, September 26-27, 2006, Geneva, Switzerland
	Wan Haiping , He Huacan, Tools for privacy preserving Kernel methods in data mining, Proceedings of the 24th IASTED international conference on Artificial intelligence and applications, p.388-391, February 13-16, 2006, Innsbruck, Austria
	K. El-Khatib , G. v. Bochmann, Protecting the privacy of user's QoS preferences for multimedia applications, Proceedings of the 2nd ACM international workshop on Wireless multimedia networking and performance modeling, October 06-06, 2006, Terromolinos, Spain
	Boris Rozenberg , Ehud Gudes, Association rules mining in vertically partitioned databases, Data & Knowledge Engineering, v.59 n.2, p.378-396, November 2006
	Dahlia Malkhi , Noam Nisan , Benny Pinkas , Yaron Sella, Fairplay—a secure two-party computation system, Proceedings of the 13th conference on USENIX Security Symposium, p.20-20, August 09-13, 2004, San Diego, CA
	Tomoyuki Yamakami, Quantum list decoding from quantumly corrupted codewords for classical block codes of polynomially small rate, Proceedings of the thirteenth Australasian symposium on Theory of computing, p.153-162, January 30-February 02, 2007, Ballarat, Victoria, Australia
	S.-C. S. Samson Cheung , Thinh Nguyen, Secure multiparty computation between distrusted networks terminals, European Journal of Information Systems, v.2007 n.1, p.1-11, January 2007
	Wei Jiang , Chris Clifton, A secure distributed framework for achieving k-anonymity, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.4, p.316-333, November 2006
	Geetha Jagannathan , Rebecca N. Wright, Privacy-preserving imputation of missing data, Data & Knowledge Engineering, v.65 n.1, p.40-56, April, 2008
	Jaideep Vaidya , Murat Kantarcıoğlu , Chris Clifton, Privacy-preserving Naïve Bayes classification, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.4, p.879-898, July 2008
	Khalil El-Khatib, The cost of protecting privacy in multimedia applications, Proceedings of the 4th ACM symposium on QoS and security for wireless and mobile networks, October 27-28, 2008, Vancouver, British Columbia, Canada
	Carmit Hazay , Yehuda Lindell, Constructions of truly practical secure protocols using standardsmartcards, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA
	Chin-Chen Chang , Jung-San Lee, Robust t-out-of-n oblivious transfer mechanism based on CRT, Journal of Network and Computer Applications, v.32 n.1, p.226-235, January, 2009
	Daisuke Inoue , Keisuke Tanaka, Conditional Converge Cast, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.6, p.1537-1540, June 2008
	John Bethencourt , Dawn Song , Brent Waters, New Techniques for Private Stream Searching, ACM Transactions on Information and System Security (TISSEC), v.12 n.3, p.1-32, January 2009
	Qingsong Ye , Huaxiong Wang , Josef Pieprzyk , Xian-Mo Zhang, Unconditionally secure disjointness tests for private datasets, International Journal of Applied Cryptography, v.1 n.3, p.225-235, February 2009
	Yuval Ishai , Tal Malkin , Martin J. Strauss , Rebecca N. Wright, Private multiparty sampling and approximation of vector combinations, Theoretical Computer Science, v.410 n.18, p.1730-1745, April, 2009