The round complexity of secure protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The round complexity of secure protocols

Full text

Pdf (1.02 MB)

Source

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

Baltimore, Maryland, United States

Pages: 503 - 513

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

D. Beaver	Harvard University, Aiken Computation Laboratory, Harvard University, Cambridge, MA 02138
S. Micali	MIT, tMIT Laboratory for Computer Science, 545 Technology, Square, Cambridge, MA
P. Rogaway	MIT, tMIT Laboratory for Computer Science, 545 Technology, Square, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 88, Citation Count: 18

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/100216.100287 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	J. Bar-Ilan , D. Beaver, Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.201-209, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72995]
	2	[Be88] D. Beaver, "Secure Multiparty Protocols Tolerating Half Faulty Processors," Harvard Technical Report TR-19-88, and in CRYPTO-89 Proceedings.
	3	Donald Rozinak Beaver , Michael Rabin, Security, fault tolerance, and communication complexity in distributed systems, Harvard University, Cambridge, MA, 1990
	4	[BFKR89] D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, "Cryptographic Applications of Locally Random Reductions," Bell Laboratories Technical Memorandum, November 1989. Also a 1990 PODC submission, "Security with Low Communication Overhead."
	5	Donald Beaver , Shafi Goldwasser, Multiparty Computation with Faulty Majority, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.589-590, August 20-24, 1989
	6	[BE88] M. Ben-Or and R. El-Yaniv, "Interactive Consistency in Constant Expected Time," manuscript, December 1988.
	7	Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
	8	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]
	9	David Chaum, The Spymasters Double-Agent Problem: Multiparty Computations Secure Unconditionally from Minorities and Cryptographically from Majorities, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.591-602, August 20-24, 1989
	10	David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
	11	David Chaum , Ivan Damgård , Jeroen van de Graaf, Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.87-119, August 16-20, 1987
	12	[CGMA85] B. Chor, O. Goldreich, S. Micali and B. Awerbuch, "Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults," Proc. of the 26th FOCS (1985), 383-395.
	13	Benny Chor , Michael O. Rabin, Achieving independence in logarithmic number of rounds, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.260-268, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41862]
	14	[Fe88] P. Feldman, "One Can Always Assume Private Channels," unpublished manuscript (1988).
	15	Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62225]
	16	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
	17	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]
	18	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
	19	Stuart Alan Haber, Multiparty cryptographic computation: techniques and applications, Columbia University, New York, NY, 1988
	20	J. Håstad, Pseudo-random generators under uniform assumptions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.395-404, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100270]
	21	[KMR90] J. Kilian, S. Micali and P. Rogaway, "The Notion of Secure Computation," manuscript, March 1990.
	22	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]
	23	T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
	24	Phillip Rogaway, The round complexity of secure protocols, Massachusetts Institute of Technology, Cambridge, MA, 1992
	25	[Ya82a] A. Yao, Protocols for Secure Computation, Proc. of the 23rd FOCS (1982) 160-164.
	26	[Ya82b] A. Yao, "Theory and Applications of Trapdoor Functions," Proc. of the 23rd FOCS (1982) 80-91.
	27	[Ya86] A. Yao, "How to Generate and Exchange Secrets," Proc. of the 18th STOC (1986) 162-167.

CITED BY 18

	Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada
	Charles Rackoff , Daniel R. Simon, Cryptographic defense against traffic analysis, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.672-681, May 16-18, 1993, San Diego, California, United States
	Tal Rabin, Robust sharing of secrets when the dealer is honest or cheating, Journal of the ACM (JACM), v.41 n.6, p.1089-1109, Nov. 1994
	Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Rosario Gennaro , Yuval Ishai , Eyal Kushilevitz , Tal Rabin, The round complexity of verifiable secret sharing and secure multicast, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.580-589, July 2001, Hersonissos, Greece
	Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Benny Pinkas, Cryptographic techniques for privacy-preserving data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.12-19, December 2002
	Michael Ben-Or , Ran El-Yaniv, Resilient-optimal interactive consistency in constant time, Distributed Computing, v.16 n.4, p.249-262, December 2003
	Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin J. Strauss , Rebecca N. Wright, Secure multiparty computation of approximations, ACM Transactions on Algorithms (TALG), v.2 n.3, p.435-472, July 2006
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	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
	Jonathan Katz, On achieving the "best of both worlds" in secure multiparty computation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Jonathan Katz , Chiu-Yuen Koo, On expected constant-round protocols for Byzantine agreement, Journal of Computer and System Sciences, v.75 n.2, p.91-112, February, 2009
	Assaf Ben-David , Noam Nisan , Benny Pinkas, FairplayMP: a system for secure multi-party computation, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA
	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
	Takashi Nishide , Kazuo Ohta, Constant-Round Multiparty Computation for Interval Test, Equality Test, and Comparison, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.5, p.960-968, May 2007
	Prahladh Harsha , Yuval Ishai , Joe Kilian , Kobbi Nissim , S. Venkatesh, Communication vs. Computation, Computational Complexity, v.16 n.1, p.1-33, May 2007