Abstract
Given only an interactive protocol of a certain type as a primitive, we can build a (non-interactive) signature scheme that is secure in the strongest sense of Goldwasser, Micali and Rivest (see [11]): not existentially forgeable under adaptively chosen message attacks. There are numerous examples of primitives that satisfy our conditions, e.g. Feige-Fiat-Shamir, Schnorr, Guillou-Quisquater, Okamoto and Brickell-Mc.Curley ([9], [17], [12], [15], [3]).
A main consequence is that efficient and secure signature schemes can now also be based on computationally difficult problems other than factoring (see [11]), such as the discrete logarithm problem.
In fact, the existence of one-way group homomorphisms is a sufficient assumption to support our construction. As we also demonstrate that our construction can be based on claw-free pairs of trapdoor permutations, our results can be viewed as a generalization of [11].
Basic Research in Computer Science, Centre of the Danish National Research Foundation
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
M. Abadi, E. Allender, A. Broder, J. Feigenbaum and L. Hemachandra: On Generating Solved Instances of Computational Problems, Proc. of Crypto 88, Springer Verlag LNCS series.
J. Bos and D. Chaum: Provably Unforgeable Signatures, Proc. of Crypto 92, Springer Verlag LNCS series.
E. F. Brickell and K. S. McCurley: An Interactive Identification Scheme Based on Discrete Logarithms and Factoring, Journal of Cryptology, 5(1), pp.29–39, 1992.
I. Damgård: Collision Free Hash Functions and Public-Key Signature Schemes, Proc. of EuroCrypt 87, Springer Verlag LNCS series.
R. Cramer, I. Damgård: Secure Signature Schemes based on Interactive Protocols, BRICS report series, RS-94-29, September 1994, Aarhus University.
R. Cramer: On Shared Randomness and the Size of Secure Signatures, CWI technical report CS-R9530, April 1995.
C. Dwork, M. Naor: An Efficient Existentially Unforgeable Signature Scheme and its Applications, Proceedings of Crypto’94, Santa Barbara, August 1994, Springer Verlag LNCS series, pp. 234–246.
U. Feige, A. Shamir: Witness Indistinguishable and Witness Hiding Protocols, Proc. of STOC 90.
U. Feige, A. Fiat and A. Shamir: Zero-Knowledge Proofs of Identity, Journal of Cryptology 1 (1988) 77–94.
O. Goldreich: Two Remarks concerning the GMR Signature Scheme, Proc. of Crypto 86, Springer Verlag LNCS series.
S. Goldwasser, S. Micali and R. Rivest: A Digital Signature Scheme Secure Against Chosen Message Attacks, SIAM Journal on Computing, 17(2): 281–308, 1988.
L. Guillou and J.-J. Quisquater: A Practical Zero-Knowledge Protocol fitted to Security Microprocessor Minimizing both Transmission and Memory, Proc. of EuroCrypt’ 88, Springer Verlag LNCS series.
R.C. Merkle: A Digital Signature Based on a Conventional Encryption Function, Proc. of Crypto 87, Springer Verlag LNCS series.
M. Naor and M. Yung: Universal One-Way Hash Functions and their Cryptographic Applications, Proc. of STOC 89.
T. Okamoto: Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes, Proc. of Crypto’ 92, pp.31–53, Santa Barbara, August 1992.
J. Rompel: One-Way Functions are Necessary and Sufficient for Secure Signatures, Proc. of STOC 90.
C.P. Schnorr: Efficient Signature Generation by Smart Cards, Journal of Cryptology, 4(3):161–174, 1991.
M. Tompa and H. Woll: Random Self-Reducibility and Zero-Knowledge Proof of Information Possession, Proc. of FOCS 87.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cramer, R., Damgård, I. (1995). Secure Signature Schemes based on Interactive Protocols. In: Coppersmith, D. (eds) Advances in Cryptology — CRYPT0’ 95. CRYPTO 1995. Lecture Notes in Computer Science, vol 963. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44750-4_24
Download citation
DOI: https://doi.org/10.1007/3-540-44750-4_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60221-7
Online ISBN: 978-3-540-44750-4
eBook Packages: Springer Book Archive