Simplified VSS and fast-track multiparty computations with applications to threshold cryptography

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simplified VSS and fast-track multiparty computations with applications to threshold cryptography

Full text

Pdf (1.50 MB)

Source

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

Puerto Vallarta, Mexico

Pages: 101 - 111

Year of Publication: 1998

ISBN:0-89791-977-7

Authors

Rosario Gennaro	IBM T.J. Watson Research Center, PO Box 704, Yorktown, Heights, New York
Michael O. Rabin	IBM T.J. Watson Research Center, PO Box 704, Yorktown, Heights, New York
Tal Rabin

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): 21, Downloads (12 Months): 76, Citation Count: 12

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

	BB89	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]
	Bea89	Donald Beaver, Multiparty protocols tolerating half faulty processors, Proceedings on Advances in cryptology, p.560-572, July 1989, Santa Barbara, California, United States
	Bea91	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
	BGW88	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]
	Bla79	G.R. Blakley. Safeguarding cryptographic keys. In Proc. AFiPS 1979 National Computer Conference, pages 313-317. AFIPS, 1979.
	Boy89	C. Boyd. Digital Multisignatures. In H. Baker and F. Piper, editors, Cryptography and Coding, pages 241-246. Claredon Press, 1989.
	Can95	Ran Canetti. Studies in Secure Multiparty Computation. PhD thesis, weizmann Institute of Science, 1995.
	CCD88	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]
	CD97	R. Crarner and I. Damgard. Zero-knowledge for finite field arithmetic or: Can zero-knowledge be for free? Manuscript, 1997.
	CDM97	R. Cramer, I. Damgard, and U. Maurer. Span programs and general multiparty computations. Manuscript, 1997.
	CFGN96	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 [doi>10.1145/237814.238015]
	CGMA85	B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults. In Proceeding 26th Annual Symposium on the Foundations of Computer Science, pages 383-395. IEEE, 1985.
	CH89	R.A. Croft and S. P. Harris. Public-key cryptography and re-usable shared secrets. In H. Baker and F. Piper, editors, Cryptography and Coding, pages 189-201. Claredon Press, 1989.
	CMI93	M. Cerecedo, T. Matsumoto, and H. Imai. Efficient and secure multiparty generation of digital signatures based on discrete logarithms. IEICE Trans. Fundamentals, E76~A(4):532-545, 1993.
	CW79	J.L. Carter and M.N. Wegman. Universal Classes of Hash Functions. JC$$, vol.18, pp.143-154, 1979.
	DDFY94	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]
	Des87	Yvo Desmedt, Society and Group Oriented Cryptography: A New Concept, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.120-127, August 16-20, 1987
	Des94	Yvo G. Desmedt. Threshold cryptography. European Transactions on Telecommunications, 5(4):449-457, July 1994.
	DF89	Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
	DF91	Yvo Desmedt , Yair Frankel, Shared Generation of Authenticators and Signatures (Extended Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.457-469, August 11-15, 1991
	DH76	W. Dittie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6):644-654, 1976.
	DPP96	I. Damgard, T.P. Pedersen and B. Pfitzmann. On the existence of Statistically Hiding Bit Commitment Schemes and FaJi-Stop Signatures J. of Cryptology, vol.10, no.4, pp.163-194. See also Statistical Secrecy and Multi-Bit Commitments. BRICS report series, RS-96-45, available from http://www, brics.dk
	ElG85	T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory, iT 31, 1985.
	Fel87	P. Feldman. A Practical Scheme for Non-Interactive Verifiable Secret Sharing. In Proc. 28th Annual Syrup. on Foundations of Computer Science, pages 427-437. IEEE, 1987.
	FGY96	Yair Frankel , Peter Gemmell , Moti Yung, Witness-based cryptographic program checking and robust function sharing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.499-508, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237998]
	FM	P. Feldman and S. Micali. A Definition of Verifiable Secret Sharing. An adaptation from {FM88}.
	FM88	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]
	FY92	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 [doi>10.1145/129712.129780]
	GJKR96a	Rosario Gennaro , Stanislaw Jarecki , Hugo Krawczyk , Tal Rabin, Robust and Efficient Sharing of RSA Functions, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.157-172, August 18-22, 1996
	GJKR96b	R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In Ueli Maurer, editor, Advances in Cryptology Eurocrypt '96, pages 354-371, Berlin, 1996. Springer-Verlag. Lecture Notes in Computer Science No. 1070.
	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]
	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]
	GMW91	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 [doi>10.1145/116825.116852]
	GRR98	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 [doi>10.1145/277697.277716]
	Har94	L. Harn. Group oriented (t,n) digital signature scheme. IEEE Proc.- Comput. Digit. Tech, 141(5):307-313, Sept 1994.
	JY	Markus Jakobsson and Moti Yung. Distributed "magic ink" signatures. To appear in EuroCrypt97.
	Lan95	Susan K. Langford, Threshold DSS Signatures without a Trusted Party, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.397-409, August 27-31, 1995
	MR91	Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
	MS81	R. J. McEliece , D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Communications of the ACM, v.24 n.9, p.583-584, Sept. 1981 [doi>10.1145/358746.358762]
	NIST91	National Institute for Standards and Technology. Digital Signature Standard (DSS). Technical Report 169, August 30 1991.
	PK96	C. Park, and K. Kurosawa. New E1Gamal Type Threshold Digital Signature Scheme. IEICE Trans. Fundamentals, E79-A(1):86-93, January 1996.
	Ped91a	Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
	Ped91b	T. Pedersen. A threshold cryptosystem without a trusted party. In D. Davies, editor, Advances in Cryptology --Eurocrypt '91, pages 522-526, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science No. 547.
	Rab94	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 [doi>10.1145/195613.195621]
	RB89	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]
	RSA78	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
	Sch91	C.P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4:161-174, 1991.
	Sha79	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]
	TW88	M. Tompa , H. Woll, How to share a secret with cheaters, Journal of Cryptology, v.1 n.2, p.133-138, Aug. 1988
	Yao82	A.C. Yao. Protocols for secure computations. In Proceedings of FOCS'82, pages 160-164, Chicago, 1982. IEEE.

CITED BY 12

	Wei Jiang , Chris Clifton , Murat Kantarcıoğlu, Transforming semi-honest protocols to ensure accountability, Data & Knowledge Engineering, v.65 n.1, p.57-74, April, 2008
	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
	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
	Jiangtao Li , Ninghui Li, Policy-hiding access control in open environment, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Christian Scheideler, How to spread adversarial nodes?: rotate!, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	M. Moharrum , R. Mukkamala , M. Eltoweissy, A novel collusion-resilient architecture for secure group communication in wireless ad-hoc networks, Journal of High Speed Networks, v.15 n.1, p.73-92, January 2006
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	Sergio Rajsbaum, ACM SIGACT news distributed computing column 24, ACM SIGACT News, v.37 n.4, December 2006
	Arjan Durresi, Anonymous communications in the Internet, Cluster Computing, v.10 n.1, p.57-66, March 2007
	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
	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