Abstract
Sharing signature power may be required in many occasions. Moreover a multisigning operation may be required to be performed simultaneously (in some sense) by all the involved cosigning parties.
We describe a complete cooperation-based signature scheme achieving such requirements. It is based on mental games and in particular on the Guillou-Quisquater zero-knowledge scheme. In our scheme, the cosigners interact with an intermediate entity, the combiner, to produce a multisignature. Only one interactive exchange is required. The scheme is practical and secure. A cheating combiner can only prevent the operation from happening but it will be immediately detected. No impersonation, substitution, or coalition attacks are possible.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Bengio, G. Brassard, Y. Desmedt, C. Goutier and J.-J. Quisquater. Secure Implementation of Identification Systems. Journal of Cryptology (1991) 4, pp. 175–183.
M. Ben-Or, S. Goldwasser, J. Killian and A. Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the twentieth annual ACM Symp. Theory of Computing, STOC, pp. 113–131, May 2–4,1988.
M. V. D. Burmester and Y. G. Desmedt. Remarks on Soundness of Proofs. Electronic letters, 26th October 1989, Vol. 25, N∘ 22, pp. 1509–1510.
M. V. D. Burmester. To appear.
I. B. Damgård. Collision-Free Hash Functions and Public-Key Signature schemes. Advances in cryptology, Proceedings of EUROCRYPT '87, Lecture Notes in Computer Science, N∘ 304, pp. 203–216, Springer-Verlag, 1988.
Y. Desmedt and Y. Frankel. Shared Generation of Authenticators and Signatures. Advances in cryptology, Proceedings of CRYPTO '91, Lecture Notes in Computer Science, N∘ 576, pp. 457–469, Springer-Verlag, 1992.
Y. Desmedt and J.-J. Quisquater. Public-key systems based on the difficulty of tampering. Advances in cryptology, Proceedings of CRYPTO '86, Lecture Notes in Computer Science, N∘ 263, pp. 186–194, Springer-Verlag, 1987.
D. de Waleffe and J.-J. Quisquater. Better login protocols for computer networks. Proceedings of ESORICS '90, pp. 163–172, October 1990.
Ph. Flajolet and A. M. Odlyzko. Random Mapping Statistics. Advances in cryptology, Proceedings of EUROCRYPT '89, Lecture Notes in Computer Science, N∘ 434, pp. 329–354, Springer-Verlag.
S. Goldwasser, S. Micali and C. Rackoff. The Knowledge Complexity of Interactive Proof Systems. Siam. J. Comput., 1989, Vol. 18, N∘ 1, pp. 186–208.
L. C. Guillou and J.-J. Quisquater. Efficient digital public-key signatures with shadow. Advances in cryptology, Proceedings of CRYPTO '87, Lecture Notes in Computer Science, N∘ 304, p. 223, Springer-Verlag, 1988.
L. C. Guillou and J.-J. Quisquater. A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In C. G. Günther, editor, Advances in Cryptology, Proceedings of EUROCRYPT '88, Lecture Notes in Computer Science, N∘ 330, pp. 123–128, Springer-Verlag, May 1988. Davos, Switzerland.
L. C. Guillou and J.-J. Quisquater. A “paradoxical” identity-based signature scheme resulting from zero-knowledge. In Advances in cryptology, Proceedings of CRYPTO '88, N∘ 403, pp. 216–231, Springer-Verlag, 1989.
L. C. Guillou, M. Ugon and J.-J. Quisquater. The Smart Card: A standardized Security Device Dedicated to Public Cryptology. Contemporary Cryptology: The Science Information Integrity, edited by G. J. Simmons, IEEE Press, 1991.
M.O. Rabin. Probabilistic algorithms for testing primality. J. Number theory, Vol. 12, pp. 128–138, 1980.
A. Shamir. Identity-based cryptosystems and signatures schemes. Advances in cryptology, Proceedings of CRYPTO '84, Lecture Notes in Computer Science, N∘ 196, pp. 47–53, Springer-Verlag, 1985.
A. Shamir, R. Rivest and L. Adleman. Mental Poker. The Mathematical Gardner, edited by D. A. Klarner, Wadsworth International, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Delos, O., Quisquater, JJ. (1994). Efficient multi-signature schemes for cooperating entities. In: Cohen, G., Litsyn, S., Lobstein, A., Zémor, G. (eds) Algebraic Coding. Algebraic Coding 1993. Lecture Notes in Computer Science, vol 781. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57843-9_9
Download citation
DOI: https://doi.org/10.1007/3-540-57843-9_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57843-7
Online ISBN: 978-3-540-48357-1
eBook Packages: Springer Book Archive