The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme
Abstract We introduce a new class of computational problems which we call the "one-more-RSAinversion " 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. We show how 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. Since the appearence of the preliminary version of this paper, the new problems we have introduced have found other uses as well.