Verifiable secret sharing and multiparty protocols with honest majority

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Verifiable secret sharing and multiparty protocols with honest majority

Full text

Pdf (1.39 MB)

Source

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

Seattle, Washington, United States

Pages: 73 - 85

Year of Publication: 1989

ISBN:0-89791-307-8

Authors

T. Rabin	Institute of Mathematics and Computer Science, The Hebrew University, Jerusalem, Israel
M. Ben-Or	Institute of Mathematics and Computer Science, The Hebrew University, Jerusalem, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 26, Downloads (12 Months): 204, Citation Count: 66

Additional Information:

abstract 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/73007.73014 What is a DOI?

ABSTRACT

Under the assumption that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly, we present a verifiable secret sharing protocol, and show that any multiparty protocol, or game with incomplete information, can be achieved if a majority of the players are honest. The secrecy achieved is unconditional and does not rely on any assumption about computational intractability. Applications of these results to Byzantine Agreement are also presented. Underlying our results is a new tool of Information Checking which provides authentication without cryptographic assumptions and may have wide applications elsewhere.

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.

	B	M. Ben-Or, Multiparty Protocols with Honest Majority, in preparation.
	BGW	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]
	CCD	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]
	CGMA	B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, FOCS85, pp. 383-395
	D	D. Dolev, The Byzantine Generals Strike Again, J. of Algorithms, Vol. 3, pp. 14-30, 1980.
	DDY	D. Dolev, C. Dwork, M. Yung, NonCryptographic Secure Communication in General Networks. Preprint.
	F	P. Feldman, Optimal Algorithms for Byzantine Agreement, MIT Ph.D. Thesis, to appear.
	FM	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]
	GMW	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]
	R1	M. Rabin, Randomized Byzantine Generals, FOCS83, pp. 403-409
	R2	M. Rabin, Digitalized Signatures, Foundations of Secure Computations, R. Demillo et.al, editors, Academic Press, (1978), pp. 155-165
	RT	T. Rabin, Robust Sharing of Secrets when the Dealer is Honest or Cheating, M.Sc. Thesis, The Hebrew University, July 1988.
	S	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]
	TW	M. Tompa and H. Woll, How to Share a Secret with Cheaters, IBM Research Report, RC 11840 (Log :#: 52910) (1986)

CITED BY 66

	Matthew Franklin , Moti Yung, Communication complexity of secure computation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.699-710, May 04-06, 1992, Victoria, British Columbia, Canada
	J. D. Tygar, Atomicity in electronic commerce, netWorker, v.2 n.2, p.32-43, April/May 1998
	Thomas Beth , Hans-Joachim Knobloch , Marcus Otten, Verifiable secret sharing for monotone access structures, Proceedings of the 1st ACM conference on Computer and communications security, p.189-194, November 03-05, 1993, Fairfax, Virginia, United States
	Mattias Fitzi , Ueli Maurer, From partial consistency to global broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.494-503, May 21-23, 2000, Portland, Oregon, United States
	Michael Ben-Or , Boaz Kelmer , Tal Rabin, Asynchronous secure computations with optimal resilience (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.183-192, August 14-17, 1994, Los Angeles, California, United States
	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
	Claude Crépeau , Daniel Gottesman , Adam Smith, Secure multi-party quantum computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	J. D. Tygar, Atomicity in electronic commerce, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.8-26, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Ronald Cramer , Ivan Damgård , Stefan Dziembowski, On the complexity of verifiable secret sharing and multiparty computation, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.325-334, May 21-23, 2000, Portland, Oregon, United States
	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
	Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States
	Martin Hirt , Ueli Maurer, Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.25-34, August 21-24, 1997, Santa Barbara, California, United States
	Ran Canetti , Rafail Ostrovsky, Secure computation with honest-looking parties (extended abstract): what if nobody is truly honest?, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.255-264, May 01-04, 1999, Atlanta, Georgia, 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
	Amos Beimel , Lior Malka, Efficient reliable communication over partially authenticated networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.233-242, July 13-16, 2003, Boston, Massachusetts
	Josh Benaloh , Dwight Tuinstra, Receipt-free secret-ballot elections (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.544-553, May 23-25, 1994, Montreal, Quebec, Canada
	Michael K. Reiter, Secure agreement protocols: reliable and atomic group multicast in rampart, Proceedings of the 2nd ACM Conference on Computer and communications security, p.68-80, November 1994, Fairfax, Virginia, United States
	Rosario Gennaro , Michael O. Rabin , Tal Rabin, Simplified VSS and fast-track multiparty computations with applications to threshold cryptography, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.101-111, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Shafi Goldwasser, Multi party computations: past and present, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.1-6, August 21-24, 1997, Santa Barbara, California, United States
	Donald Beaver, Commodity-based cryptography (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.446-455, May 04-06, 1997, El Paso, Texas, United States
	Uri Feige , Joe Killian , Moni Naor, A minimal model for secure computation (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.554-563, May 23-25, 1994, Montreal, Quebec, Canada
	Carles Padro , Germán Sáez , Jorge Luis Villar, Detection of Cheaters in Vector Space Secret Sharing Schemes, Designs, Codes and Cryptography, v.16 n.1, p.75-85, January 1999
	Donald Beaver, Server-assisted cryptography, Proceedings of the 1998 workshop on New security paradigms, p.92-106, September 22-26, 1998, Charlottesville, Virginia, United States
	Danny Dolev , Cynthia Dwork , Orli Waarts , Moti Yung, Perfectly secure message transmission, Journal of the ACM (JACM), v.40 n.1, p.17-47, Jan. 1993
	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
	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991
	W. G. Tzeng, A Secure Fault-Tolerant Conference-Key Agreement Protocol, IEEE Transactions on Computers, v.51 n.4, p.373-379, April 2002
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	M V N Ashwin Kumar , Pranava R. Goundan , K Srinathan , C. Pandu Rangan, On perfectly secure communication over arbitrary networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	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
	Matt Lepinski , Silvio Micali , Chris Peikert , Abhi Shelat, Completely fair SFE and coalition-safe cheap talk, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	C. Blundo , B. Masucci , D. R. Stinson , R. Wei, Constructions and Bounds for Unconditionally Secure Non-Interactive Commitment Schemes, Designs, Codes and Cryptography, v.26 n.1-3, p.97-110
	Moni Naor, Cryptography and mechanism design, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	Kuo-Qin Yan , Shu-Ching Wang , Mao-Lun Chiang, New application of reliable agreement: underlying an unsecured business environment, ACM SIGOPS Operating Systems Review, v.38 n.3, p.42-57, July 2004
	Mikhail Atallah , Marina Bykova , Jiangtao Li , Keith Frikken , Mercan Topkara, Private collaborative forecasting and benchmarking, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA
	Amos Beimel , Lior Malka, Efficient reliable communication over partially authenticated networks, Distributed Computing, v.18 n.1, p.1-19, July 2005
	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
	Jingmin He , Ed Dawson, Shared Secret Reconstruction, Designs, Codes and Cryptography, v.14 n.3, p.221-237, Sept. 1998
	Ran Canetti, Security and composition of cryptographic protocols: a tutorial (part I), ACM SIGACT News, v.37 n.3, September 2006
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	Ueli Maurer, Secure multi-party computation made simple, Discrete Applied Mathematics, v.154 n.2, p.370-381, 1 February 2006
	Paolo D'Arco , Wataru Kishimoto , Douglas R. Stinson, Properties and constraints of cheating-immune secret sharing schemes, Discrete Applied Mathematics, v.154 n.2, p.219-233, 1 February 2006
	Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Kannan Srinathan , C. Pandu Rangan, Possibility and complexity of probabilistic reliable communication in directed networks, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Eyal Kushilevitz , Yehuda Lindell , Tal Rabin, Information-theoretically secure protocols and security under composition, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Sergio Rajsbaum, ACM SIGACT news distributed computing column 24, ACM SIGACT News, v.37 n.4, December 2006
	F. Emekci , O. D. Sahin , D. Agrawal , A. El Abbadi, Privacy preserving decision tree learning over multiple parties, Data & Knowledge Engineering, v.63 n.2, p.348-361, November, 2007
	Gillat Kol , Moni Naor, Games for exchanging information, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Dov S. Gordon , Hazay Carmit , Jonathan Katz , Yehuda Lindell, Complete fairness in secure two-party computation, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Zero-knowledge from 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, 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
	Sébastien Gambs , Balázs Kégl , Esma Aïmeur, Privacy-preserving boosting, Data Mining and Knowledge Discovery, v.14 n.1, p.131-170, February 2007
	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
	J. D. Tygar, Atomicity versus Anonymity: Distributed Transactions for Electronic Commerce, Proceedings of the 24rd International Conference on Very Large Data Bases, p.1-12, August 24-27, 1998
	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
	Phillip Rogaway , Mihir Bellare, Robust computational secret sharing and a unified account of classical secret-sharing goals, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA
	Ittai Abraham , Danny Dolev , Joseph Y. Halpern, An almost-surely terminating polynomial protocol forasynchronous byzantine agreement with optimal resilience, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Jonathan Katz , Chiu-Yuen Koo , Ranjit Kumaresan, Improving the round complexity of VSS in point-to-point networks, Information and Computation, v.207 n.8, p.889-899, August, 2009
	Arpita Patra , Ashish Choudhary , C. Pandu Rangan , Kannan Srinathan , Prasad Raghavendra, Perfectly reliable and secure message transmission tolerating mobile adversary, International Journal of Applied Cryptography, v.1 n.3, p.200-224, February 2009
	Amos Beimel, On private computation in incomplete networks, Distributed Computing, v.19 n.3, p.237-252, January 2007
	Lein Harn , Changlu Lin, Detection and identification of cheaters in (t, n) secret sharing scheme, Designs, Codes and Cryptography, v.52 n.1, p.15-24, July 2009
	Kannan Srinathan , Arpita Patra , Ashish Choudhary , C. Pandu Rangan, Unconditionally secure message transmission in arbitrary directed synchronous networks tolerating generalized mixed adversary, Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, March 10-12, 2009, Sydney, Australia
	Cheng-Chi Lee , Pi-Fang Ho , Min-Shiang Hwang, A secure e-auction scheme based on group signatures, Information Systems Frontiers, v.11 n.3, p.335-343, July 2009
	Arpita Patra , Ashish Choudhary , Chandrasekharan Pandu Rangan, Simple and efficient asynchronous byzantine agreement with optimal resilience, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada