Achieving independence in logarithmic number of rounds

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Achieving independence in logarithmic number of rounds

Full text

Pdf (963 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the sixth annual ACM Symposium on Principles of distributed computing table of contents

Vancouver, British Columbia, Canada

Pages: 260 - 268

Year of Publication: 1987

ISBN:0-89791-239-4

Authors

Benny Chor	Aiken Computation Laboratory, Harvard University, 33 Oxford St., Cambridge, Massachusetts
Michael O. Rabin	Aiken Computation Laboratory, Harvard University, 33 Oxford St., Cambridge, Massachusetts

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	ABCGM	B. Awerbuch, M. Blum, B. Chor, S. Goldwasser, and S. MicMi, "How to implement Bracha's O(log n) Byzantine Agreement Algorithm," unpublished manuscript, 1985.
	Ba	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	Br	G Bracha, An O(lg n) expected rounds randomized Byzantine generals protocol, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.316-326, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22180]
	BD	A. Broder and D. Dolev, ~Flipping coins in many pockets (Byzantine agreement on uniformly random values)," Proc. $5th IEEE Conf. on the Foundations of Computer Science (Oct. 1984), pp. 157-170.
	C	B. Chor, "Critical remarks on the Broder- Dolev coin flipping protocol," unpublished, 1985.
	CGMA	B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch, ~Verifiable secret sharing and achieving simultaneity in the presence of faults,~ Proc. ~6th IEEE Conf. on the Foundations of Computer Science (October 1985), pp. 383-395.
	CF	J. Cohen and M. Fischer, ~A robust and verifiable cryptographically secure election scheme,~ Proc. ~6th IEEE Conf. on the Foundations of Computer Science (October 1985), 372-382.
	DSS	C. Dwork, D. Shmoys, and L. Stockmeyer, ~Flipping persuasively in constant expected time,= Proc. ~7th IEEE Conf. on the Foundations of Computer Science (October 1986), pp. 222-232.
	GMW	O. Goldreich, S. Mica}i, and A. Wigderson, ~Proofs that yield nothing but their va~ lidity and a methodology of cryptographic protocol design,~ Proc. ~7th IEEE Conf. on the Foundations of Computer Science (October 1986), pp. 174-187.
	GMW2	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]
	GM	S. Goldwasser and S. Micali "Probabilistic encryption," J. Comp. and Sys. Sci. 28(2), 270-299, (1984).
	GMR	S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
	Me	Michael Merritt, Elections in the presence of faults, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.134-142, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806741]
	Sh	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]
	Sp	E. Sperner, "Ein Satz fiber Untermenge einer endlichen Menge," Math. Z. 27, 544- 54s, (ig2s).

CITED BY 9

	Rosario Gennaro, Achieving independence efficiently and securely, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.130-136, August 20-23, 1995, Ottowa, Ontario, Canada
	Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Rosario Gennaro, A Protocol to Achieve Independence in Constant Rounds, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.636-647, July 2000
	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
	Yael Tauman Kalai , Yehuda Lindell , Manoj Prabhakaran, Concurrent general composition of secure protocols in the timing model, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Alejandro Hevia , Daniele Micciancio, Simultaneous broadcast revisited, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	D. Beaver , S. Micali , P. Rogaway, The round complexity of secure protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.503-513, May 13-17, 1990, Baltimore, Maryland, United States