The One-More-RSA-Inversion Problems and the security of Chaum's Blind Signature Scheme

Note: The preliminary version of this paper had the title: The Power of RSA Inversion Oracles and the Security of Chaum's RSA-Based Blind Signature Scheme

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).