Abstract
We describe an RSA-based signing scheme which combines essentially optimal efficiency with attractive security properties. Signing takes one RSA decryption plus some hashing, verification takes one RSA encryption plus some hashing, and the size of the signature is the size of the modulus. Assuming the underlying hash functions are ideal, our schemes are not only provably secure, but are so in a tight way—an ability to forge signatures with a certain amount of computational resources implies the ability to invert RSA (on the same size modulus) with about the same computational effort. Furthermore, we provide a second scheme which maintains all of the above features and in addition provides message recovery. These ideas extend to provide schemes for Rabin signatures with analogous properties; in particular their security can be tightly related to the hardness of factoring.
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
D. Balenson, “Privacy Enhancement for Internet Electronic Mail: Part III: Algorithms, Modes, and Identifiers,” IETF RFC 1423, February 1993.
M. Bellare and S. Micali, “How to sign given any trapdoor permutation,” JACM Vol. 39, No. 1, 214–233, January 1992.
M. Bellare and P. Rogaway, “Random oracles are practical: a paradigm for designing efficient protocols,” Proceedings of the First Annual Conference on Computer and Communications Security, ACM, 1993.
M. Bbellare and P. Rogaway, “Optimal Asymmetric Encryption,” Advances in Cryptology — Eurocrypt 94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed., Springer-Verlag, 1994.
W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Trans. Info. Theory IT-22, 644–654, November 1976.
C. Dwork and M. Naor. An efficient existentially unforgeable signature scheme and its applications. Advances in Cryptology — Crypto 94 Proceedings, Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed., Springer-Verlag, 1994.
T. El Gamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Transactions on Information Theory, Vol. 31, No. 4, July 1985.
A. Fiat and A. Shamir, “How to prove yourself: practical solutions to identification and signature problems,” Advances in Cryptology — Crypto 86 Proceedings, Lecture Notes in Computer Science Vol. 263, A. Odlyzko ed., Springer-Verlag, 1986.
S. Goldwasser, S. Micali and R. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks,” SIAM Journal of Computing, 17(2):281–308, April 1988.
ISO/IEC 9796, “Information Technology Security Techniques — Digital Signature Scheme Giving Message Recovery,” International Organization for Standards, 1991.
M. Naor and M. Yung, “Universal one-way hash functions and their cryptographic applications,” Proceedings of the 21st Annual Symposium on Theory of Computing, ACM, 1989.
A. Lenstra and H. Lenstra (eds.), “The development of the number field sieve,” Lecture Notes in Mathematics, vol 1554, Springer-Verlag, 1993.
D. Pointcheval and J. Stern, “Security proofs for signatures,” Advances in cryptology — Eurocrypt 96 Proceedings, Lecture Notes in Computer Science, U. Maurer ed., Springer-Verlag, 1996.
R. Rivest, “The MD5 Message-Digest Algorithm,” IETF RFC 1321, April 1992.
R. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures and public key cryptosystems,” CACM 21 (1978).
RSA Data Security, Inc., “PKCS #1: RSA Encryption Standard (Version 1.4).” June 1991.
RSA Data Security, Inc., “PKCS #7: Cryptographic Message Syntax Standard (version 1.4).” June 1991.
M. Rabin, “Digital signatures,” in Foundations of secure computation, R. A. Millo et. al. eds, Academic Press, 1978.
M. Rabin., “Digital signatures and public key functions as intractable as factorization,” MIT Laboratory for Computer Science Report TR-212, January 1979.
J. Rompel, “One-Way Functions are Necessary and Sufficient for Secure Signatures,” Proceedings of the 22nd Annual Symposium on Theory of Computing, ACM, 1990.
H. Williams, “A modification of the RSA public key encryption procedure,” IEEE Transactions on Information Theory, Vol. IT-26, No. 6, November 1980.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Rogaway, P. (1996). The Exact Security of Digital Signatures-How to Sign with RSA and Rabin. In: Maurer, U. (eds) Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68339-9_34
Download citation
DOI: https://doi.org/10.1007/3-540-68339-9_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61186-8
Online ISBN: 978-3-540-68339-1
eBook Packages: Springer Book Archive