Secure Hash-and-Sign Signatures without the Random Oracle

Rosario Gennaro; Shai Halevi; Tal Rabin

Paper 1999/013

Secure Hash-and-Sign Signatures without the Random Oracle

Rosario Gennaro, Shai Halevi, and Tal Rabin

Abstract

We present a new signature scheme which is existentially unforgeable under chosen message attacks, assuming some variant of the RSA conjecture. This scheme is not based on "signature trees", and instead it uses the so called "hash-and-sign" paradigm. It is unique in that the assumptions made on the cryptographic hash function in use are well defined and reasonable (although non-standard). In particular, we do not model this function as a random oracle. We construct our proof of security in steps. First we describe and prove a construction which operates in the random oracle model. Then we show that the random oracle in this construction can be replaced by a hash function which satisfies some strong (but well defined!) computational assumptions. Finally, we demonstrate that these assumptions are reasonable, by proving that a function satisfying them exists under standard intractability assumptions.

Metadata

Available format(s): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords: Digital Signatures RSA Hash and Sign The Random Oracle Paradigm Smooth Numbers Chameleon Hashing.
Contact author(s): shaih @ watson ibm com
History: 1999-04-19: received
Short URL: https://ia.cr/1999/013
License: CC BY

BibTeX

@misc{cryptoeprint:1999/013,
      author = {Rosario Gennaro and Shai Halevi and Tal Rabin},
      title = {Secure Hash-and-Sign Signatures without the Random Oracle},
      howpublished = {Cryptology ePrint Archive, Paper 1999/013},
      year = {1999},
      note = {\url{https://eprint.iacr.org/1999/013}},
      url = {https://eprint.iacr.org/1999/013}
}