Cryptology ePrint Archive: Report 2001/002

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

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

Abstract: We introduce a new class of 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. 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.

Category / Keywords: public-key cryptography / Blind digital signature schemes, digital cash, RSA

Publication Info: An extended abstract of this paper, entitled ``The power of RSA inversion oracles and the security of Chaum's RSA-based blind signature scheme,'' appears in the Proceedings of the Financial Cryptography 01 conference. The full version here is to appear in the Journal of Cryptology.

Date: received 5 Jan 2001, last revised 16 Jun 2002

Contact author: cnamprem at cs ucsd edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20020617:060552 (All versions of this report)

Short URL: ia.cr/2001/002

Discussion forum: Show discussion | Start new discussion