Christian Cachin
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.
- M. Ben-Or, R. Canetti, and O. Goldreich. Asynchronous secure computation. In Proc. 25th Annual ACM Symp. on Theory of Computing, 1993.]] Google Scholar
Digital Library
- G. Bracha. An asynchronous {(n-1)/3}-resilient consensus protocol. In Proc. 3rd ACM Symp. on Principles of Dist. Computing, pages 154--162, 1984.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute, 1995.]]Google Scholar
- R. Canetti, R. Gennaro, A. Herzberg, and D. Naor. Proactive security: Long-term protection against break-ins. RSA Laboratories' CryptoBytes, 3(1), 1997.]]Google Scholar
- 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.]] Google ScholarDigital Library
- R. Canetti, S. Halevi, and A. Herzberg. Maintaining authenticated communication in the presence of break-ins. J. Cryptology, 13(1):61--106, 2000.]]Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- Y. Desmedt. Threshold cryptography. European Trans. on Telecommunications, 5(4):449--457, 1994.]]Google ScholarCross Ref
- 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.]] Google ScholarDigital Library
- 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.]]Google Scholar
- S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Computing, 18(1):186--208, Feb. 1989.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. on Programming Languages and Systems, 4(3):382--401, July 1982.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228--234, Apr. 1980.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- V. Shoup. Practical threshold signatures. In B. Preneel, editor, EUROCRYPT 2000, volume 1087 of LNCS, pages 207--220. Springer, 2000.]]Google Scholar
- L. Zhou. Towards fault-tolerant and secure on-line services. PhD thesis, Cornell University, USA, 2001.]] Google ScholarDigital Library
- Asynchronous verifiable secret sharing and proactive cryptosystems
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 ComputingA 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