Abstract
With a fail-stop signature scheme, the supposed signer of a forged signature can prove to everybody else that it was a forgery. Thus the signer is secure even against computationally unrestricted forgers. Until recently, efficient constructions were only known for restricted cases, but at Eurocrypt ’92, van Heijst and Pedersen presented an efficient general scheme, where the unforgeability is based on the discrete logarithm.
We present a similar scheme based on factoring: Signing a message block requires approximately one modular exponentiation, and testing it requires a little more than two exponentiations. It is useful to have such alternative constructions in case one of the unproven assumptions is broken.
With all fail-stop signatures so far, the size of the secret key is linear in the number of messages to be signed. In one sense, we prove that this cannot be avoided: The signer needs so many secretly chosen random bits. However, this does not imply that these bits ever have to be secretly stored at the same time: We present a practical construction with only logarithmic secret storage and a less practical one where the amount of secret storage is constant.
We also prove rather small lower bounds for the length of public keys and signatures. All three lower bounds are within a small factor of what can be achieved with one of the known schemes.
Finally, we prove that with unconditionally secure signatures, like those presented by Chaum and Roijakkers at Crypto ’90, the length of a signature is at least linear in the number of participants who can test it. This shows that such schemes cannot be as efficient as fail-stop signatures.
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
Gerrit Bleumer, Birgit Pfitzmann, Michael Waidner: A remark on a signature scheme where forgery can be proved; Eurocrypt’ 90, LNCS 473, Springer-Verlag, Berlin 1991, 441–445.
David Chaum, Hans van Antwerpen: Undeniable signatures; Crypto’ 89, LNCS 435, Springer-Verlag, Heidelberg 1990, 212–216.
David Chaum, Eugène van Heijst, Birgit Pfitzmann: Cryptographically Strong Undeniable Signatures, Unconditionally Secure for the Signer; Crypto’ 91, LNCS 576, Springer-Verlag, Berlin 1992, 470–484.
David Chaum, Sandra Roijkakkers: Unconditionally Secure Digital Signatures; Crypto’ 90, LNCS 537, Springer-Verlag, Berlin 1991, 206–214.
Ivan Bjerre Damgård: Collision free hash functions and public key signature schemes; Eurocrypt’ 87, LNCS 304, Springer-Verlag, Berlin 1988, 203–216.
Whitfield Diffie, Martin E. Hellman: New Directions in Cryptography; IEEE Transactions on Information Theory 22/6 (1976) 644–654.
William Feller: An Introduction to Probability Theory and Its Applications, Vol. II (2nd. ed.); John Wiley & Sons, New York 1971.
Robert G. Gallager: Information Theory and Reliable Communication; John Wiley & Sons, New York 1968.
Oded Goldreich: Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme; Crypto’ 86, LNCS 263, Springer-Verlag, Berlin 1987, 104–110.
Shafi Goldwasser, Silvio Micali, Ronald L. Rivest: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks; SIAM J. Comput. 17/2 (1988) 281–308.
Jeroen van de Graaf, René Peralta: A simple and secure way to show the validity of your public key; Crypto’ 87, LNCS 293, Springer-Verlag, Berlin 1988, 128–134.
Eugène van Heijst, Torben Pryds Pedersen: How to Make Efficient Fail-stop Signatures; Eurocrypt’ 92, Extended Abstracts, 24.–28. 5. 1992, Balatonfüred, Hungary, 337–346.
Leslie Lamport: Constructing Digital Signatures from a One-Way Function; SRI Intl. CSL-98, Oct. 1979.
Ralph C. Merkle: Protocols for Public Key Cryptosystems; Proc. 1980 Symposium on Security and Privacy, Oakland 1980, 122–134.
Ralph C. Merkle: A digital signature based on a conventional encryption function; Crypto’ 87, LNCS 293, Springer-Verlag, Berlin 1988, 369–378.
Birgit Pfitzmann: Fail-stop Signatures; Principles and Applications; Proc. Compsec’ 91, 8th world conference on computer security, audit and control, Elsevier, Oxford 1991, 125–134.
Birgit Pfitzmann, Michael Waidner: Formal Aspects of Fail-stop Signatures; Fakultät für Informatik, University Karlsruhe, Report 22/90, Dec. 1990.
Birgit Pfitzmann, Michael Waidner: Fail-stop Signatures and their Application; Securicom 91, Paris, 19.–22. March 1991, 145–160.
Birgit Pfitzmann, Michael Waidner: Unconditional Byzantine Agreement for any Number of Faulty Processors; STACS 92, LNCS 577, Springer-Verlag, Berlin 1992, 339–350.
Claude E. Shannon: Communication in the Presence of Noise; Proceedings of the Institute of Radio Engineers 37/1 (1949) 10–21.
Michael Waidner, Birgit Pfitzmann: The Dining Cryptographers in the Disco: Unconditional Sender and Recipient Untraceability with Computationally Secure Serviceability; Eurocrypt’ 89, LNCS 434, Springer-Verlag, Berlin 1990, 690. (Full version: Unconditional Sender and Recipient Untraceability in spite of Active Attacks — Some Remarks; Fakultät für Informatik, University Karlsruhe, Report 5/89, March 1989.)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Heijst, E., Pedersen, T.P., Pfitzmann, B. (1993). New Constructions of Fail-Stop Signatures and Lower Bounds. In: Brickell, E.F. (eds) Advances in Cryptology — CRYPTO’ 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48071-4_2
Download citation
DOI: https://doi.org/10.1007/3-540-48071-4_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57340-1
Online ISBN: 978-3-540-48071-6
eBook Packages: Springer Book Archive