Separation Results on the ``One-More'' Computational Problems.

E. Bresson, J. Monnerat and D. Vergnaud

In 2001, Bellare, Namprempre, Pointcheval and Semanko introduced the notion
of "one-more" computational problems. Since their introduction, these
problems have found numerous applications in cryptography. For instance,
Bellare et al. showed how they lead to a proof of security for Chaum's
RSA-based blind signature scheme in the random oracle model.

In this paper, we provide separation results for the computational hierarchy
of a large class of algebraic "one-more" computational problems (e. g. the
one-more discrete logarithm problem, the one-more RSA problem and the
one-more static Computational Diffie-Hellman problem in a bilinear setting).
We also give some cryptographic implications of these results and, in
particular, we prove that it is very unlikely, that one will ever be able to
prove the unforgeability of Chaum's RSA-based blind signature scheme under
the sole RSA assumption.

Keywords. "One-more" problems, Black-box reductions, Random self-reducible
problems, Algebraic algorithms.