The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme
type: Item
instance of: scholarly article
title: The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme
zbMATH Open document ID: 1045.94012
author: M. Bellare
author: M. Semanko
author: Chanathip Namprempre
author: David Pointcheval
published in: Journal of Cryptology
publication date: 2003-08-27T00:00:00Z
review text: A new useful class of computational problems for public-key cryptology is introduced and studied. There are two well-known functions which are associated with RSA public key protocol \(\text{RSA}_{N,e}(x)= x^e\bmod N\) and \(\text{RSA}^{-1}_{N,e}(y)= y^d\bmod N\), where \(x\), \(y\) are natural integers, \(e\) is an encryption parameter, \(d\) is a decryption parameter, \(ed\equiv 1\bmod \varphi(N)\). The function \(\text{RSA}^{-1}\) is called RSA-inverse. The adversary has access to an oracle for the inverse RSA function in a given target point \(y\). The oracle returns \(y^d\text{\,mod\,}N\) without revealing the integer \(d\). The problems are as follows. In the known-target inversion problem, the adversary, to win, must output the inverses of all given target points, using a number of decryption oracle queries that is one fewer than the number of target points. In the chosen-target inversion problem, the adversary can choose to invert any number of target points and wins as long as the number of decryption oracle queries that it makes is strictly fewer than the number of target points it correctly inverts. The main result is that these two problems have polynomially equivalent complexity. It is shown how this leads to a proof of security for Chaum's RSA-based blind signature scheme. Analogous results are proved for ``one-more-discrete-logarithm'' problems.
reviewed by: Anatoly V. Anisimov
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1971857
zbMATH Keywords: Blind digital signature schemes
zbMATH Keywords: Digital cash
zbMATH Keywords: RSA
MaRDI profile type: Publication
full work available at URL: s00145-002-0120-1
OpenAlex ID: W2054482077
Wikidata QID: Q56921345
DBLP publication ID: journals/joc/BellareNPS03
DOI: 10.1007/S00145-002-0120-1
description: scientific article; zbMATH DE number 1971857