Abstract
Often it is desired that the power to sign or authenticate messages is shared. This paper presents methods to collectively generate RSA signatures, provably secure authenticators and unconditionally secure authenticators. In the new schemes, l individuals are given shares such that k ≤ l are needed to generate a signature (authenticator) but less than k can not. When the k people have finished signing (authenticating), nobody can perform an impersonation or substitution attack. These schemes are called threshold signature (authentication) schemes. Clearly these schemes are better than each of the k individuals sending a separate authenticator for each message or if each of the k individuals each send their share to a “trusted” person who will sign for them.
In all of the schemes we assume that the shareholders (senders) and receiver have secure workstations but the network and servers are not necessarily secure.
Research is being supported by NSF Grant NCR-9106327.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
B. Blakley and G. R. Blakley. Security of number theoretic public key cryptosystems against random attack. Cryptologia, 1978. In three parts: Part I: 2 (4), pp. 305–321, October 1978; Part II: 3(1), pp. 29–42, January 1979; Part III: 3(2), pp. 105–118, April 1979.
G. R. Blakley and I. Borosh. Rivest-Shamir-Adleman public key cryptosystems do not always conceal messages. Computers & Mathematics with Apllications, 5(3):169–178, 1979.
J. C. Benaloh. Secret sharing homomorphisms: Keeping shares of a secret secret. In A. Odlyzko, editor, Advances in Cryptology, Proc. of Crypto’86 (Lecture Notes in Computer Science 263), pages 251–260. Springer-Verlag, 1987. Santa Barbara, California, U.S.A., August 11–15.
G. R. Blakley. Safeguarding cryptographic keys. In Proc. Nat. Computer Conf. AFIPS Conf. Proc., pages 313–317, 1979. vol.48.
G. R. Blakley and L. Swanson. Infinite structures in information theory. In D. Chaum, R.L. Rivest, and A. T. Sherman, editors, Advances in Cryptology. Proc. of Crypto’82, pages 39–50. Plenum Press N. Y., 1983. Crypto’82, Santa Barbara, CA, August 1982.
R. A. Croft and S. P. Harris. Public-key cryptography and re-usable shared secrets. In H. Beker and F. Piper, editors, Cryptography and coding, pages 189–201. Clarendon Press, 1989. Royal Agricultural College, Cirencester, December 15–17, 1986.
B. Chor and E. Kushilevitz. Secret sharing over infinite domains. In G. Brassard, editor, Advances in Cryptology — Crypto’ 89, Proceedings (Lecture Notes in Computer Science 435), pages 299–306. Springer-Verlag, 1990. Santa Barbara, California, U.S.A., August 20–24.
G. I. Davida. Chosen signature cryptanalysis of the RSA (MIT) public key cryptosystem. Tech. Report TR-CS-82-2, University of Wisconsin-Milwaukee, October 1982.
D. E. R. Denning. Digital signatures with RSA and other public-key cryptosystems. Comm. ACM 27, pages 388–392, 1984.
Y. Desmedt. Abuse-free cryptosystems: Particularly subliminal-free authentication and signature. Submitted to the Journal of Cryptology, under revision, April 1989.
Y. Desmedt and Y. Frankel. Unconditionally secure threshold authentication. In preparation (Available from authors when completed).
Y. Desmedt and Y. Frankel. Threshold cryptosystems. Santa Barbara, California, U.S.A., August 20–24, 1990.
Y. Desmedt and Y. Frankel. Perfect zero-knowledge sharing schemes over any finite Abelian group. Presented at Sequences’ 91, June 17–22, 1991, Positano, Italy, to appear in: the Proceedings Springer-Verlag, 1991.
W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. Inform. Theory, IT-22(6):644–654, November 1976.
W. de Jonge and D. Chaum. Attacks on some RSA signatures. In Advances in Cryptology: Crypto’ 85, Proceedings (Lecture Notes in Computer Science 218), pages 18–27. Springer-Verlag, New York, 1986. Santa Barbara, California, U.S.A., August 18–22, 1985.
M. De Soete, J.-J. Quisquater, and K. Vedder. A signature with shared verification scheme. In G. Brassard, editor, Advances in Cryptology — Crypto’ 89, Proceedings (Lecture Notes in Computer Science 435), pages 253–262. Springer-Verlag, 1990. Santa Barbara, California, U.S.A., August 20–24.
R. G. Gallager. Information theory and reliable communication. John Wiley and Sons, New York, 1968.
S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. Siam J. Comput., 17(2):281–308, April 1988.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proceedings of the Nineteenth ACM Symp. Theory of Computing, STOC, pages 218–229, May 25–27, 1987.
O. Goldreich. Two remarks concerning the Goldwasser-Micali-Rivest signature scheme. In A. Odlyzko, editor, Advances in Cryptology, Proc. of Crypto’86 (Lecture Notes in Computer Science 263), pages 104–110. Springer-Verlag, 1987. Santa Barbara, California, U.S.A., August 11–15, 1986.
N. Jacobson. Basic Algebra I, volume 1. W. H. Freeman and Company, 2nd edition, 1985.
N. Jacobson. Basic Algebra II, volume 2. W. H. Freeman and Company, 2nd edition, 1989.
D. E. Knuth. The Art of Computer Programming, Vol. 2, Seminumerical Algorithms. Addison-Wesley, Reading, MA, 1981.
J. H. Moore. Protocol failures in cryptosystems. Proc. IEEE, 76(5):594–602, May 1988.
A. Menezes, S. Vanstone, and T. Okamoto. Reducing elliptic curve logarithms to logarithms in a finite field. In Proceedings of the Twenty third annual ACM Symp. Theory of Computing, STOC, pages 80–89, 1991.
A. M. Odlyzko. Discrete logs in a finite field and their cryptographic significance. In N. Cot T. Beth and I. Ingemarsson. editors, Advances in Cryptology, Proc. of Eurocrypt’84 (Lecture Notes in Computer Science 209), pages 224–314. Springer-Verlag, 1984. Paris, France April 1984.
R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public key cryptosystems. Commun. ACM, 21:294–299, April 1978.
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
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Desmedt, Y., Frankel, Y. (1992). Shared generation of authenticators and signatures. In: Feigenbaum, J. (eds) Advances in Cryptology — CRYPTO ’91. CRYPTO 1991. Lecture Notes in Computer Science, vol 576. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46766-1_37
Download citation
DOI: https://doi.org/10.1007/3-540-46766-1_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55188-1
Online ISBN: 978-3-540-46766-3
eBook Packages: Springer Book Archive