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.
Category / Keywords: Digital Signatures, RSA, Hash and Sign, The Random Oracle Paradigm, Smooth Numbers, Chameleon Hashing. Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. Date: received April 19, 1999. Contact author: shaih at watson ibm com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Short URL: ia.cr/1999/013 Discussion forum: Show discussion | Start new discussion