On the Impossibility of Proving Security of Strong-RSA Signatures via the RSA Assumption

We pose a question whether or not the standard RSA assumption is sufficient to prove the security of the strong RSA-based (SRSA-based, for short) signatures. In this paper, we show a negative circumstantial evidence for the question. Namely, several SRSA-based signatures cannot be proven to be sEUF-CMA, or even EUF-KOA, under the RSA assumption as far as a modulus-preserving algebraic reduction is concerned. Our result is obtained as an important application of the adaptive pseudo-free group introduced by Catalano, Fiore and Warinschi that can be regarded as an abstract framework of signatures. We in fact show that the adaptive pseudo-freeness of the RSA group Z(N)(x) cannot be proven from the RSA assumption via such reductions.