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

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

Paper 2001/002

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

M. Bellare, C. Namprempre, 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.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. 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.
Keywords: Blind digital signature schemes digital cash RSA
Contact author(s): cnamprem @ cs ucsd edu
History: 2002-06-17: last of 5 revisions; 2001-01-05: received; See all versions
Short URL: https://ia.cr/2001/002
License: CC BY

BibTeX

@misc{cryptoeprint:2001/002,
      author = {M.  Bellare and C.  Namprempre and D.  Pointcheval and M.  Semanko},
      title = {The One-More-{RSA}-Inversion Problems and the Security of Chaum's Blind Signature Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2001/002},
      year = {2001},
      url = {https://eprint.iacr.org/2001/002}
}