The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme (Q1402372)

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.