Authors: M. Bellare, C. Namprempre, D. Pointcheval and M. Semanko
Abstract: We introduce a new class of RSA-related computational problems which we call the ``one-more-RSA-inversion'' problems. Our main result is that two problems in this class, which we call the chosen-target and known-target inversion problems respectively, have polynomially-equivalent computational complexity. This leads to a proof of security for Chaum's RSA-based blind signature scheme in the random oracle model based on the assumed hardness of either of these problems. We define and prove analogous results for ``one-more-discrete-logarithm'' problems.
Ref: Journal of Cryptology, Vol. 16, No. 3, 2003, pp. 185-215. Extended abstract of the preliminary version appeared in Financial Cryptography 01, Lecture Notes in Computer Science Vol. 2339, P. Syverson ed, Springer-Verlag, 2001. Full paper available below.
Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).