Correlated pseudorandomness and the complexity of private computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Correlated pseudorandomness and the complexity of private computations

Full text

Pdf (936 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 479 - 488

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Donald Beaver

Transarc Corp., Gulf Tower, 707 Grant St., Pittsburgh, PA

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): 21, Citation Count: 1

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/237814.237996 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.

	BCKO93	R. Bar-Yehuda, B. Chor, E. Kushilevitz, A. Orlitsky. "Privacy, Additional Information, and Communication." IEEE Trans. Info. Theory 39:6, November 1993, 1930-1943.
	Bea95	Donald Beaver, Precomputing Oblivious Transfer, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.97-109, August 27-31, 1995
	Bea89	D. Beaver. "Perfect Privacy for Two-Party Protocols." Proceedings of the DIMAC$ Workshop on Distributed Computing and Cryptography, Princeton, NJ, October 1989.
	BG89	D. Beaver, S. Goldwasser. "Multiparty Computation with Faulty Majority." Proceedings of the 30th FOCS, IEEE, 1989, 1989, 468-473.
	BS93	Donald Beaver , Nicol So, Global, unpredictable bit generation without broadcast, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.424-434, January 1994, Lofthus, Norway
	BM89	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
	Ben83	Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
	BM84	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	BC86	Gilles Brassard , Claude Crépeau, Zero-knowledge simulation of Boolean circuits, Proceedings on Advances in cryptology---CRYPTO '86, p.223-233, January 1987, Santa Barbara, California, United States
	BCR86	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
	BCR86	G. Brassard, C. Crdpeau, J. Robert. "Information Theoretic Reductions Among Disclosure Problems." Proceedings of the 27*h FOCS, IEEE, 1986, 1986, 168-173.
	CK91	Benny Chor , Eyal Kushilevitz, A zero-one law for Boolean privacy, SIAM Journal on Discrete Mathematics, v.4 n.1, p.36-47, Feb. 1991 [doi>10.1137/0404004]
	Cr87	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
	Boe91	Bert den Boer, Oblivious transfer protecting secrecy, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.31-45, February 1991, Aarhus, Denmark
	EGL82	S. Even, O. Goldreich, A. Lempel. "A Randomized Protocol for Signing Contracts." Proceeding~ of Crypto 1982, Springer- Verlag, 1983, 205-210.
	GHY87	Zvi Galil , Stuart Haber , Moti Yung, Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.135-155, August 16-20, 1987
	GMW86	O. Goldreich, S. Micali, A. Wigderson. "Proofs that Yield Nothing but Their Validity and a Methodology of Cryptographic Protocol Design." Proceedings of the 27ta FOC$, IEEE, 1986, 1986, 174-187.
	GMW87	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
	GV87	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
	GL90	Shafi Goldwasser , Leonid A. Levin, Fair Computation of General Functions in Presence of Immoral Majority, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.77-93, August 11-15, 1990
	GMR89	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	ILL89	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	IR89	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]
	Kil88	Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62215]
	Kil91	Joe Kilian, A general completeness theorem for two party games, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.553-560, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103475]
	KMO89	J. Kilian, S. Micali, R. Ostrovsky. "Minimum Resource Zero-Knowledge Proofs." Proceedings of the 30ta FOC$, iEEE, 1989, 1989, 474-479.
	Kus92	Eyal Kushilevitz, Privacy and communication complexity, SIAM Journal on Discrete Mathematics, v.5 n.2, p.273-284, May 1992 [doi>10.1137/0405021]
	KMO94	E. Kushilevitz, S. Micali, R. Ostrovsky. "Reducibility and Completeness in Multi-Party Private Computations." Proceedings of the 35ta FOCS, IEEE, 1994, 478-489.
	OVY91	R. Ostrovsky, R. Venkatesan, M. Yung. "Fair Games Against an All-Powerful Adversary.'' SEQUENCES '91, 1991.
	Rab81	M.O. Rabin. "How to Exchange Secrets by Oblivious Transfer." TR-81, Harvard, 1981.
	Yao86	A. Yao. "How to Generate and Exchange Secrets.'' Proceedings of the 27th FOCS, IEEE, 1986, 1986, 162-167.