Article

Asynchronous verifiable secret sharing and proactive cryptosystems

Authors:

Christian Cachin,

Anna Lysyanskaya,

Reto StroblAuthors Info & Claims

CCS '02: Proceedings of the 9th ACM conference on Computer and communications security

Pages 88 - 97

https://doi.org/10.1145/586110.586124

Published: 18 November 2002 Publication History

Abstract

Verifiable secret sharing is an important primitive in distributed cryptography. With the growing interest in the deployment of threshold cryptosystems in practice, the traditional assumption of a synchronous network has to be reconsidered and generalized to an asynchronous model. This paper proposes the first practical verifiable secret sharing protocol for asynchronous networks. The protocol creates a discrete logarithm-based sharing and uses only a quadratic number of messages in the number of participating servers. It yields the first asynchronous Byzantine agreement protocol in the standard model whose efficiency makes it suitable for use in practice. Proactive cryptosystems are another important application of verifiable secret sharing. The second part of this paper introduces proactive cryptosystems in asynchronous networks and presents an efficient protocol for refreshing the shares of a secret key for discrete logarithm-based sharings.

References

[1]

M. Ben-Or, R. Canetti, and O. Goldreich. Asynchronous secure computation. In Proc. 25th Annual ACM Symp. on Theory of Computing, 1993.]]

Digital Library

[2]

G. Bracha. An asynchronous {(n-1)/3}-resilient consensus protocol. In Proc. 3rd ACM Symp. on Principles of Dist. Computing, pages 154--162, 1984.]]

Digital Library

[3]

C. Cachin, K. Kursawe, F. Petzold, and V. Shoup. Secure and efficient asynchronous broadcast protocols (extended abstract). In J. Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 524--541. Springer, 2001.]]

Digital Library

[4]

C. Cachin, K. Kursawe, and V. Shoup. Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. In Proc. 19th ACM Symp. on Principles of Distributed Computing, pages 123--132, 2000.]]

Digital Library

[5]

R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute, 1995.]]

[6]

R. Canetti, R. Gennaro, A. Herzberg, and D. Naor. Proactive security: Long-term protection against break-ins. RSA Laboratories' CryptoBytes, 3(1), 1997.]]

[7]

R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In Proc. 30th Annual ACM Symp. on Theory of Computing, pages 209--218, 1998.]]

Digital Library

[8]

R. Canetti, S. Halevi, and A. Herzberg. Maintaining authenticated communication in the presence of break-ins. J. Cryptology, 13(1):61--106, 2000.]]

Digital Library

[9]

R. Canetti and T. Rabin. Fast asynchronous Byzantine agreement with optimal resilience. In Proc. 25th Annual ACM Symp. on Theory of Computing, pages 42--51, 1993.]]

Digital Library

[10]

M. Castro and B. Liskov. Proactive recovery in Byzantine-fault-tolerant systems. In Proc. 3rd USENIX Symposium on Operating System Design and Implementation (OSDI'99), 1999.]]

Digital Library

[11]

B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults. In Proc. 26th IEEE Symp. on Found. of Computer Science, pages 383--395, 1985.]]

Digital Library

[12]

Y. Desmedt. Threshold cryptography. European Trans. on Telecommunications, 5(4):449--457, 1994.]]

[13]

M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374--382, Apr. 1985.]]

Digital Library

[14]

R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure key generation for discrete-log based cryptosystems. In J. Stern, editor, EUROCRYPT '99, volume 1592 of LNCS, pages 295--310. Springer, 1999.]]

[15]

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

Digital Library

[16]

S. Goldwasser, S. Micali, and R. L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing, 17(2):281--308, Apr. 1988.]]

Digital Library

[17]

V. Hadzilacos and S. Toueg. Fault-tolerant broadcasts and related problems. In S. J. Mullender, editor, Distributed Systems. ACM Press & Addison-Wesley, New York, 1993.]]

Digital Library

[18]

A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing or how to cope with perpetual leakage. In D. Coppersmith, editor, CRYPTO '95, volume 963 of LNCS, pages 339--352. Springer, 1995.]]

Digital Library

[19]

L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. on Programming Languages and Systems, 4(3):382--401, July 1982.]]

Digital Library

[20]

R. Ostrovsky and M. Yung. How to withstand mobile virus attacks. In Proc. 10th ACM Symp. on Principles of Distributed Computing, pages 51--59, 1991.]]

Digital Library

[21]

M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228--234, Apr. 1980.]]

Digital Library

[22]

T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, CRYPTO '91, volume 576 of LNCS, pages 129--140. Springer, 1992.]]

Digital Library

[23]

V. Shoup. Practical threshold signatures. In B. Preneel, editor, EUROCRYPT 2000, volume 1087 of LNCS, pages 207--220. Springer, 2000.]]

[24]

L. Zhou. Towards fault-tolerant and secure on-line services. PhD thesis, Cornell University, USA, 2001.]]

Digital Library

Cited By

Alhaddad NVaria MYang Z(2025)Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with ApplicationsIACR Communications in Cryptology10.62056/a0qj5w7sf1:4Online publication date: 13-Jan-2025
https://doi.org/10.62056/a0qj5w7sf
Kowalski VMostéfaoui APerrin MSengupta S(2025)Byzantine-Tolerant Privacy-Preserving Atomic RegisterProceedings of the 26th International Conference on Distributed Computing and Networking10.1145/3700838.3700867(201-210)Online publication date: 4-Jan-2025
https://dl.acm.org/doi/10.1145/3700838.3700867
Koziel BGordon SGentry CLuo BLiao XXu JKirda ELie D(2024)Fast Two-party Threshold ECDSA with Proactive SecurityProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670387(1567-1580)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670387
Show More Cited By

Asynchronous verifiable secret sharing and proactive cryptosystems
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout
2. Security and privacy

Recommendations

Paillier-based publicly verifiable (non-interactive) secret sharing

A verifiable secret sharing is a secret sharing scheme with an untrusted dealer that allows participants to verify validity of their own shares. A publicly verifiable secret sharing (PVSS) scheme is a verifiable secret sharing scheme that allows a third ...
Attacks to some verifiable multi-secret sharing schemes and two improved schemes

Secret sharing plays an important role in protecting confidential information from being lost, destroyed, or falling into wrong hands. Verifiable multi-secret sharing enables a dealer to share multiple secrets among a group of participants such that the ...
Non-malleable secret sharing
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A number of works have focused on the setting where an adversary tampers with the shares of a secret sharing scheme. This includes literature on verifiable secret sharing, algebraic manipulation detection(AMD) codes, and, error correcting or detecting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '02: Proceedings of the 9th ACM conference on Computer and communications security

November 2002

284 pages

ISBN:1581136129

DOI:10.1145/586110

Editor:
Vijay Atluri
Rutgers University
,
General Chair:
Sushil Jajodia
George Mason University
,
Program Chair:
Ravi Sandhu
SingleSignOn.Net and George Mason University

Copyright © 2002 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 November 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS02

Sponsor:

CCS02: ACM Conference on Computer and Communications Security

November 18 - 22, 2002

Washington, DC, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

106
Total Citations
View Citations
1,528
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)15

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Alhaddad NVaria MYang Z(2025)Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with ApplicationsIACR Communications in Cryptology10.62056/a0qj5w7sf1:4Online publication date: 13-Jan-2025
https://doi.org/10.62056/a0qj5w7sf
Kowalski VMostéfaoui APerrin MSengupta S(2025)Byzantine-Tolerant Privacy-Preserving Atomic RegisterProceedings of the 26th International Conference on Distributed Computing and Networking10.1145/3700838.3700867(201-210)Online publication date: 4-Jan-2025
https://dl.acm.org/doi/10.1145/3700838.3700867
Koziel BGordon SGentry CLuo BLiao XXu JKirda ELie D(2024)Fast Two-party Threshold ECDSA with Proactive SecurityProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670387(1567-1580)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670387
Xiang AGao HTian YXiong JWang LPeng C(2024)H²CT: Asynchronous Distributed Key Generation With High-Computational Efficiency and Threshold Security in Blockchain NetworkIEEE Internet of Things Journal10.1109/JIOT.2024.343155411:20(33758-33772)Online publication date: 15-Oct-2024
https://doi.org/10.1109/JIOT.2024.3431554
Schmiedel HHan RTang QSteinfeld RYu J(2024)Modeling Mobile Crash in Byzantine Consensus2024 IEEE 37th Computer Security Foundations Symposium (CSF)10.1109/CSF61375.2024.00043(159-171)Online publication date: 8-Jul-2024
https://doi.org/10.1109/CSF61375.2024.00043
Pang ZShi LXiang H(2024)Asynchronous verifiable information dispersal protocol of achieving optimal communicationComputer Networks10.1016/j.comnet.2024.110470247(110470)Online publication date: Jun-2024
https://doi.org/10.1016/j.comnet.2024.110470
Bacho RLoss JStern GWagner B(2024)HARTS: High-Threshold, Adaptively Secure, and Robust Threshold Schnorr SignaturesAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0891-1_4(104-140)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0891-1_4
Boneh DPartap ARotem L(2024)Proactive Refresh for Accountable Threshold SignaturesFinancial Cryptography and Data Security10.1007/978-3-031-78679-2_8(140-159)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-78679-2_8
Bhimrajka NChoudhury AVaradarajan S(2024)Network-Agnostic Multi-party Computation Revisited (Extended Abstract)Public-Key Cryptography – PKC 202410.1007/978-3-031-57722-2_6(171-204)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57722-2_6
Yurek TXiang ZXia YMiller ACalandrino JTroncoso C(2023)Long live the honey badgerProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620540(5413-5430)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620540
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten