Paper 2001/002

The Power of RSA Inversion Oracles

M. Bellare and C. Namprempre and D. Pointcheval and M. Semanko

Abstract

Blind signatures are the central cryptographic component of digital cash schemes. In this paper, we investigate the security of the first such scheme proposed, namely Chaum's RSA-based blind signature scheme, in the random-oracle model. This leads us to formulate and investigate 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, have polynomially-equivalent computational complexity. This leads to a proof of security for Chaum's scheme in the random oracle model based on the assumed hardness of either of these problems.