Article

Free access

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

Authors:

Rosario Gennaro,

Michael O. Rabin,

Tal RabinAuthors Info & Claims

PODC '98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing

Pages 101 - 111

https://doi.org/10.1145/277697.277716

Published: 01 June 1998 Publication History

PDF eReader

References

[1]

J. Bar-Ilan and D. Beaver. Non-cryptographic faulttolerant computing in a constant number of rounds. In Proc. 8th A CM Syrup. on Principles of Distributed Computati on, pages 201-209. ACM, 1989.]]

Digital Library

Google Scholar

[2]

D. Beaver. Multiparty Protocols Tolerating Half Faulty Processors. In G. Brassard, editor, Advances in Cryptology Crypto '89, pages 560-572, Berlin, 1989. Springer-Verlag. Lecture Notes in Computer Science No. 435.]]

Digital Library

Google Scholar

[3]

D. Beaver. Foundations of secure interactive computing. In J. Feigenbaum, editor, Advances in Cryptology Crypto '91, pages 377-391, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science No. 576.]]

Digital Library

Google Scholar

[4]

M. BenqOr, S. Goldwasser, and A. Wigderson. Completeness Theorems for Noncryptographic Fault- Tolerant Distributed Computations. In Proc. 20th Annual Syrup. on the Theory of Computing, pages 1-10. ACM, 1988.]]

Digital Library

Google Scholar

[5]

G.R. Blakley. Safeguarding cryptographic keys. In Proc. AFiPS 1979 National Computer Conference, pages 313-317. AFIPS, 1979.]]

Crossref

Google Scholar

[6]

C. Boyd. Digital Multisignatures. In H. Baker and F. Piper, editors, Cryptography and Coding, pages 241-246. Claredon Press, 1989.]]

Google Scholar

[7]

Ran Canetti. Studies in Secure Multiparty Computation. PhD thesis, weizmann Institute of Science, 1995.]]

Google Scholar

[8]

D. Chaum, C. Crepeau, and I. Damgard. Multiparty Unconditionally Secure Protocols. In Proc. 20th Annual Syrup. on the Theory of Computing, pages 11-19. ACM, 1988.]]

Digital Library

Google Scholar

[9]

R. Crarner and I. Damgard. Zero-knowledge for finite field arithmetic or: Can zero-knowledge be for free? Manuscript, 1997.]]

Google Scholar

[10]

R. Cramer, I. Damgard, and U. Maurer. Span programs and general multiparty computations. Manuscript, 1997.]]

Google Scholar

[11]

Ran Canetti, Uri Feige, Oded Goldreich, and Moni Naor. Adaptively secure multi-party computation. In Proc. 28th Annual Syrup. on the Theory of Computing, pages 639-648. ACM, 1996.]]

Digital Library

Google Scholar

[12]

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.]]

Digital Library

Google Scholar

[13]

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.]]

Google Scholar

[14]

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.]]

Google Scholar

[15]

J.L. Carter and M.N. Wegman. Universal Classes of Hash Functions. JC$$, vol.18, pp.143-154, 1979.]]

Google Scholar

[16]

Alfredo De Santis, Yvo Desmedt, Yair Frankel, and Moti Yung. How to share a function securely. In Proc. 26th Annual Syrup. on the Theory of Computing, pages 522-533. ACM, 1994.]]

Digital Library

Google Scholar

[17]

Yvo Desmedt. Society and group oriented cryptography: A new concept. In C. Pomerance, editor, Advances in Cryptology -- Crypto '87, pages 120- 127, Berlin, :{987. Springer-Verlag. Lecture Notes in Computer Science No. 293.]]

Digital Library

Google Scholar

[18]

Yvo G. Desmedt. Threshold cryptography. European Transactions on Telecommunications, 5(4):449-457, July 1994.]]

Crossref

Google Scholar

[19]

Yvo Desmedt and Yair Frankel. Threshold cryptosystems. In G. Brassard, editor, Advances in Cryptology- Crypto '89, pages 307-315, Berlin, 1989. Springer-Verlag. Lecture Notes in Computer Science No. 435.]]

Digital Library

Google Scholar

[20]

Y. Desmedt and Y. Frankel. Shared generation of authenticators and signatures. In J. Feigenbaum, editor, Advances in Cryptology Crypto '91, pages 457-469, Berlin, 1991. Springer-Verlag. Lecture Notes in Computer Science No. 576.]]

Digital Library

Google Scholar

[21]

W. Dittie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6):644-654, 1976.]]

Digital Library

Google Scholar

[22]

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]]

Google Scholar

[23]

T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory, iT 31, 1985.]]

Google Scholar

[24]

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.]]

Digital Library

Google Scholar

[25]

Y. Frankel, P. Gemmell, and M. Yung. Witnessbased Cryptographic Program Checking and Robust Function Sharing. In Proc. 28th Annual Syrup. on the Theory of Computing, pages 499-508. ACM, 1996.]]

Digital Library

Google Scholar

[26]

P. Feldman and S. Micali. A Definition of Verifiable Secret Sharing. An adaptation from {FM88}.]]

Google Scholar

[27]

P. Feldman and S. Micali. An Optimal Algorithm for Synchronous Byzantine Agreement. In Proc. 20th Annual Syrup. on the Theory of Computing, pages 148-161. ACM, 1988.]]

Digital Library

Google Scholar

[28]

M. Franklin and M. Yung. Communication complexity of secure computation. In Proc. 24th Annual Syrup. on the Theory of Computing, pages 699-710. ACM, 1992.]]

Digital Library

Google Scholar

[29]

R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust and efficient sharing of RSA functions. In N. Koblitz, editor, Advances in Cryptology Crypto '96, pages 157-172, Berlin, 1996. Springer- Verlag. Lecture Notes in Computer Science No. 1109.]]

Digital Library

Google Scholar

[30]

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.]]

Crossref

Google Scholar

[31]

S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM. J. Computing, 18(1):186-208, February 1989.]]

Digital Library

Google Scholar

[32]

O. Goldreich, S. Micali, and A. Wigderson. How to Play Any Mental Game. In Proc. 19th Annual Syrup. on the Theory of Computing, pages 218-229. ACM, 1987.]]

Digital Library

Google Scholar

[33]

O. Goldreich, S. Micali, and A. Wigderson. Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems . Journal of the ACM, 38(1):691-729, 1991.]]

Digital Library

Google Scholar

[34]

R. Gennaxo, M.O. Rabin and T. Rabin. Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography. Final version. Available on-line at ~w. re sear ch. i bin. corn/s ecuri ty/grr, ps]]

Digital Library

Google Scholar

[35]

L. Harn. Group oriented (t,n) digital signature scheme. IEEE Proc.- Comput. Digit. Tech, 141(5):307-313, Sept 1994.]]

Crossref

Google Scholar

[36]

Markus Jakobsson and Moti Yung. Distributed "magic ink" signatures. To appear in EuroCrypt97.]]

Google Scholar

[37]

S. Langford. Threshold dss signatures without a trusted party. In D. Coppersmith, editor, Advances in Cryptology -- Crypto '95, pages 397-409, Berlin, 1995. Springer-Verlag. Lecture Notes in Computer Science No. 963.]]

Digital Library

Google Scholar

[38]

S. Micali and P. Rogaway. Secure computation. In J. Feigenbaum, editor, Advances in Cryptology Crypto '91, pages 392-404, Berlin, 1991. Springer- Verlag. Lecture Notes in Computer Science No. 576.]]

Digital Library

Google Scholar

[39]

R.J. McEliece and D. V. Sarwate. On Sharing Secrets and Reed-Solomon Codes. Communications of the A CM, 24:583-584, September 1981.]]

Digital Library

Google Scholar

[40]

National Institute for Standards and Technology. Digital Signature Standard (DSS). Technical Report 169, August 30 1991.]]

Google Scholar

[41]

C. Park, and K. Kurosawa. New E1Gamal Type Threshold Digital Signature Scheme. IEICE Trans. Fundamentals, E79-A(1):86-93, January 1996.]]

Google Scholar

[42]

T. Pedersen. Non-interactive and informationtheoretic secure verifiable secret sharing, in j. Feigenbaum, editor, Advances in Cryptology Cry,~;o '91, pages 129-140, Berlin, 1991. Springer- Verlag. Lecture Notes in Computer Science No. 576.]]

Digital Library

Google Scholar

[43]

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.]]

Google Scholar

[44]

T. Rabin. Robust Sharing of Secrets When the Dealer is Honest or Faulty. Journal of the A CM, 41(6):1089-1109, 1994.]]

Digital Library

Google Scholar

[45]

T. Rabin and M. Ben-Or. Verifiable Secret Sharing and Multiparty Protocols with Honest Majority. In Proc. 21st Annual Syrup. on the Theory of Computing, pages 73-85. ACM, 1989.]]

Digital Library

Google Scholar

[46]

Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communication of the ACM, 21(2):120-126, 1978.]]

Digital Library

Google Scholar

[47]

C.P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4:161-174, 1991.]]

Digital Library

Google Scholar

[48]

A. Shamir. How to Share a Secret. Communications of the A CM, 22:612-613, 1979.]]

Digital Library

Google Scholar

[49]

M. Tompa and H. Wo11. How to share a secret with cheaters. Journal of Cryptology, 1(2):133-138, 1988.]]

Digital Library

Google Scholar

[50]

A.C. Yao. Protocols for secure computations. In Proceedings of FOCS'82, pages 160-164, Chicago, 1982. IEEE.]]

Crossref

Google Scholar

Cited By

View all

Sakamaki YFukuoka TYamaguchi JMorinaga M(2024)Secure Rating Computation on Weighted Signed Network for Supply Chain NetworkJournal of Information Processing10.2197/ipsjjip.32.71032(710-718)Online publication date: 2024
https://doi.org/10.2197/ipsjjip.32.710
IWAMOTO M(2024)Information-Theoretic Perspectives for Simulation-Based Security in Multi-Party ComputationIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2023TAI0001E107.A:3(360-372)Online publication date: 1-Mar-2024
https://doi.org/10.1587/transfun.2023TAI0001
Xie XLi YZhang WWang TXu SZhu JSong Y(2024)GAuV: A Graph-Based Automated Verification Framework for Perfect Semi-Honest Security of Multiparty Computation Protocols2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00131(484-502)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00131
Show More Cited By

Index Terms

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

Recommendations

Dynamic threshold secret reconstruction and its application to the threshold cryptography

Shamir's ( t , n ) secret sharing scheme (SS) is based on a univariate polynomial and is the most cited SS in the literature. The secret in a ( t , n ) SS can be recovered either by exactly t or more than t shareholders. Most SSs only consider when ...
VSS from Distributed ZK Proofs and Applications
Advances in Cryptology – ASIACRYPT 2023
Abstract
Non-Interactive Verifiable Secret Sharing (NI-VSS) is a technique for distributing a secret among a group of individuals in a verifiable manner, such that shareholders can verify the validity of their received share and only a specific number of ...
Threshold progressive visual cryptography construction with unexpanded shares

Differently from traditional secret sharing, progressive secret sharing can gain clearer recovered secret image with more shares. However, previous progressive visual secret sharing (PVSS) schemes with unexpanded shares are only for case (2, n) other ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing

June 1998

334 pages

ISBN:0897919777

DOI:10.1145/277697

Chairmen:
Brian Coan
Bellcore
,
Yehuda Afek
Tel-Aviv Univ.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC98

Sponsor:

PODC98: Seventeenth Annual ACM Symposium on Principles of Distributed Computing

June 28 - July 2, 1998

Puerto Vallarta, Mexico

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

275
Total Citations
View Citations
2,334
Total Downloads

Downloads (Last 12 months)365
Downloads (Last 6 weeks)46

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sakamaki YFukuoka TYamaguchi JMorinaga M(2024)Secure Rating Computation on Weighted Signed Network for Supply Chain NetworkJournal of Information Processing10.2197/ipsjjip.32.71032(710-718)Online publication date: 2024
https://doi.org/10.2197/ipsjjip.32.710
IWAMOTO M(2024)Information-Theoretic Perspectives for Simulation-Based Security in Multi-Party ComputationIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2023TAI0001E107.A:3(360-372)Online publication date: 1-Mar-2024
https://doi.org/10.1587/transfun.2023TAI0001
Xie XLi YZhang WWang TXu SZhu JSong Y(2024)GAuV: A Graph-Based Automated Verification Framework for Perfect Semi-Honest Security of Multiparty Computation Protocols2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00131(484-502)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00131
Dolev SFok ASegal M(2024)Swarming with (visual) secret (shared) missionWireless Networks10.1007/s11276-024-03840-zOnline publication date: 14-Nov-2024
https://doi.org/10.1007/s11276-024-03840-z
Benhamouda FHalevi SKrawczyk HMa YRabin T(2024)SPRINT: High-Throughput Robust Distributed Schnorr SignaturesAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_3(62-91)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58740-5_3
Dong SYao YZhou YYang Y(2024)Lattice-Based Secret Sharing Scheme (Chinese Remainder Theorem)Digital Forensics and Cyber Crime10.1007/978-3-031-56583-0_4(54-62)Online publication date: 3-Apr-2024
https://doi.org/10.1007/978-3-031-56583-0_4
HUO WYU YYANG KZHENG ZLI XYAO LXIE J(2023)Privacy-preserving cryptographic algorithms and protocols: a survey on designs and applicationsSCIENTIA SINICA Informationis10.1360/SSI-2022-043453:9(1688)Online publication date: 6-Sep-2023
https://doi.org/10.1360/SSI-2022-0434
Burkhardt JDamgård IFrederiksen TGhosh SOrlandi CMeng WJensen CCremers CKirda E(2023)Improved Distributed RSA Key Generation Using the Miller-Rabin TestProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623163(2501-2515)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623163
Shi QDeng K(2023)Privacy-Preserving Detection Method for Transmission Line Based on Edge Collaboration2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom60117.2023.00244(1798-1805)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TrustCom60117.2023.00244
Guo GZhu YChen EYu RZhang LLv KFeng R(2023)Efficient Multiparty Fully Homomorphic Encryption With Computation Fairness and Error Detection in Privacy Preserving Multisource Data MiningIEEE Transactions on Reliability10.1109/TR.2023.324656372:4(1308-1323)Online publication date: Dec-2023
https://doi.org/10.1109/TR.2023.3246563
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Dynamic threshold secret reconstruction and its application to the threshold cryptography

VSS from Distributed ZK Proofs and Applications

Threshold progressive visual cryptography construction with unexpanded shares