Abstract
Distributed key generation is a main component of threshold cryptosystems and distributed cryptographic computing in general. Solutions to the distributed generation of private keys for discrete-log based cryptosystems have been known for several years and used in a variety of protocols and in many research papers. However, these solutions fail to provide the full security required and claimed by these works. We show how an active attacker controlling a small number of parties can bias the values of the generated keys, thus violating basic correctness and secrecy requirements of a key generation protocol. In particular, our attacks point out to the places where the proofs of security fail.
Based on these findings we designed a distributed key generation protocol which we present here together with a rigorous proof of security. Our solution, that achieves optimal resiliency, can be used as a drop-in replacement for key generation modules as well as other components of threshold or proactive discrete-log based cryptosystems.
Chapter PDF
References
R. Canetti, R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Adaptive Security for Threshold Cryptosystems. Mansuscript, 1999.
R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Advances in Cryptology — Eurocrypt’ 97, pages 103–118. LNCS No. 1233.
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.
Yvo Desmedt and Yair Frankel. Threshold cryptosystems. In Advances in Cryptology — Crypto’ 89, pages 307–315. LNCS No. 435.
T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Info. Theory, IT 31:469–472, 1985.
P. Feldman. A Practical Scheme for Non-Interactive Verifiable Secret Sharing. In Proc. 28th FOCS, pages 427–437.
Y. Frankel, P. Gemmell, P. Mackenzie, and M. Yung. Optimal resilience proactive public-key cryptosystems. In Proc. 38th FOCS, pages 384–393. IEEE, 1997.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In Advances in Cryptology — Eurocrypt’ 96, pages 354–371. LNCS No. 1070.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems http://www.research.ibm.com/security/dkg.ps
L. Harn. Group oriented (t; n) digital signature scheme. IEE Proc.-Comput.Digit.Tech, 141(5):307–313, Sept 1994.
A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, and M. Yung. Proactive public key and signature systems. In 1997 ACM Conference on Computers and Communication Security, 1997.
A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing, or: How to cope with perpetual leakage. In Advances in Cryptology — Crypto’ 95, pages 339–352. LNCS No. 963.
C.-H. Li, T. Hwang, and N.-Y. Lee. (t; n) threshold signature schemes ased on discrete logarithm. In Advances in Cryptology — Eurocrypt’ 94, pages 191–200. LNCS No. 950.
T. Pedersen. A threshold cryptosystem without a trusted party. In Advances in Cryptology — Eurocrypt’ 91, pages 522–526. LNCS No. 547.
T. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Advances in Cryptology — Crypto’ 91, pages 129–140. LNCS No. 576.
C. Park and K. Kurosawa. New ElGamal Type Threshold Digital Signature Scheme. IEICE Trans. Fundamentals, E79-A(1):86–93, January 1996.
C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4:161–174, 1991.
V. Shoup and R. Gennaro. Securing threshold cryptosystems against chosen ciphertext attack. In Advances in Cryptology — Eurocrypt’ 98, pages 1–16. LNCS No. 1403.
A. Shamir. How to Share a Secret. Communications of the ACM, 22:612–613, 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T. (1999). Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In: Stern, J. (eds) Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48910-X_21
Download citation
DOI: https://doi.org/10.1007/3-540-48910-X_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65889-4
Online ISBN: 978-3-540-48910-8
eBook Packages: Springer Book Archive