Abstract
Even, Goldreich and Micali showed at Crypto'89 that the existence of signature schemes secure against known message attacks implies the existence of schemes secure against adaptively chosen message attacks. Unfortunately, this transformation leads to a rather impractical scheme. We exhibit a similar security amplification, which takes the given scheme to a new signature scheme that is not even existentially forgeable under adaptively chosen message attacks. Additionally, however, our transformation will be practical: The complexity of the resulting scheme is twice that of the original scheme.
The principles of both transformations carry over to block encryption systems. It is shown how they can be used to convert a block encryption system secure against known plaintext attacks to a system secure against chosen plaintext attacks. For both schemes it is shown that if the transformed scheme can be broken given a number, T, of encryptions of adaptively chosen plaintexts, then the original scheme can be broken given encryptions of T uniformly chosen plaintexts. In this case, however, the application of the technique of Even, Goldreich and Micali leads to the more efficient scheme. The transformed scheme has the same key length as the original, and ciphertexts are doubled in length. As an example, when applied to DES the transformed scheme is secure against differential cryptanalysis, which relies on the ability to get encryptions of plaintext pairs with proper differences.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Bellare, S. Micali: How to Sign Given Any Trapdoor Function. Proceedings of STOC '88, pp.32–42.
E. Biham, A. Shamir: Differential Cryptanalysis of DES-like Cryptosystems. Proceedings of Crypto'90, pp. 2–21.
S. Even, O. Goldreich and S. Micali: On-Line/Off-Line Digital Signatures. Proceedings of Crypto '89, pp.263–275.
R. Cramer, I. Damgård, B. Schoenmakers,: “Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols”, Proceedings of Crypto '94, pp. 174–187.
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.R. Knudsen. Personal communication.
M. Naor, C. Dwork: An Efficient Existentially Unforgeable Signature Scheme and its Applications. Proceedings of Crypto '94, pp.234–246.
M. Naor, M. Yung: Universal One Way Hash functions and their Cryptographic Applications. Proceedings of STOC '89, pp.33–43.
National Bureau of Standards. Data encryption standard. Federal Information Processing Standard (FIPS), Publication 46, National Bureau of Standards, U.S. Department of Commerce, Washington DC, January 1977.
J. Rompel: One Way Functions are Necessary and Sufficient for signatures. Proceedings of STOC '90, pp.387–394.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cramer, R., Damgård, I., Pedersen, T. (1997). Efficient and provable security amplifications. In: Lomas, M. (eds) Security Protocols. Security Protocols 1996. Lecture Notes in Computer Science, vol 1189. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62494-5_9
Download citation
DOI: https://doi.org/10.1007/3-540-62494-5_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62494-3
Online ISBN: 978-3-540-68047-5
eBook Packages: Springer Book Archive