Abstract
Threshold cryptosystems allow n members of a group to share a private key such that any k of them can use the key without revealing its value. These systems can be divided into two categories, systems which use a trusted center to generate the shares and systems which create the shares in a distributed manner. This paper describes a number of security weaknesses which arise in systems which do not use a trusted center. We show that the n-out-of-n threshold undeniable signature scheme [8] has an actual security of only 2-out-of-n. The discrete log based threshold signature schemes [7, 11, 12] have a weakness in the key generation protocol. Finally, the generalized threshold cryptosystem [9] is not secure for some access structures.
Chapter PDF
Similar content being viewed by others
Keywords
References
D. Chaum and H. van Antwerpen, “Undeniable Signatures,” Advances in Cryptology — Eurocrypt’ 89 proceedings, Springer-Verlag, 1989, pp. 212–216.
Y. Desmedt, “Society and group oriented cryptography,” Advances in Cryptology-Crypto’ 87 proceedings, Springer-Verlag, 1988, pp. 120–127.
Y. Desmedt, “Threshold Cryptography,” European Transactions on Telecommunications and Related Technologies, Vol. 5, No. 4, July–August 1994, pp. 35–43.
Y. Desmedt and Y. Frankel, “Shared generation of authenticators and signatures,” Advances in Cryptology-Crypto’ 91 proceedings, Springer-Verlag, 1992, pp. 457–269.
T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Trans. Inform. Theory, Vol. 31, 1985, pp. 521–539.
Y. Frankel and Y. Desmedt, “Parallel reliable threshold multisignature,” Tech. Report TR-92-04-02, Dep. of EE & CS, Univ. of Wisconsin-Milwaukee, April 1992.
L. Harn, “Group-oriented (t, n) threshold digital signature scheme and digital multisignature,” IEE Proc.-Comput. Digit. Tech., Vol. 141, No. 5, September 1994, pp. 307–313.
L. Harn and S. Yang, “Group-Oriented Undeniable Signature Schemes without the Assistance of a Mutually Trusted Party,” Advances in Cryptology — Auscrypt’ 92 proceedings, Springer-Verlag, 1992, pp. 133–142.
C. Laih and L. Harn, “Generalized threshold cryptosystems,” Advances in Cryptology — Asiacrypt’ 91 proceedings, Springer-Verlag, 1993, pp. 159–166.
S. Langford, “Threshold DSS Signatures without a Trusted Party,” Advances in Cryptology — Crypto’ 95 proceedings, Springer-Verlag, 1995, pp. 397–409.
C. Li, T. Hwang, N. Lee, “(t, n)-threshold signature scheme based on discrete logarithm,” Advances in Cryptology — Eurocrypt’ 94 proceedings, Springer-Verlag, 1995, pp. 191–200.
C. Park and K. Kurosawa, “New ElGamal Type Threshold Digital Signature Scheme,” pre-print.
T. Pedersen, “A Threshold Cryptosystem without a Trusted Party,” Advances in Cryptology — Eurocrypt’ 91 proceedings, Springer-Verlag, 1992, pp. 522–526.
R. Rivest, A. Shamir, L. Adleman, “A method for obtaining digital signatures and public key cryptosystems,” Communications of the ACM, Vol. 21, April 1978, pp. 294–299.
A. Shamir, “How to share a secret,” Commun. ACM, 22:612–613, November 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Langford, S.K. (1996). Weaknesses in Some Threshold Cryptosystems. In: Koblitz, N. (eds) Advances in Cryptology — CRYPTO ’96. CRYPTO 1996. Lecture Notes in Computer Science, vol 1109. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68697-5_6
Download citation
DOI: https://doi.org/10.1007/3-540-68697-5_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61512-5
Online ISBN: 978-3-540-68697-2
eBook Packages: Springer Book Archive