# RSA and the strong RSA assumptions

The RSA assumption:

Given a randomly generated RSA modulus $$n$$, exponent $$r$$ and a random $$z \in \mathbb{Z}_n^{*}$$, find $$y$$ such that $$y^r=z$$.

The strong RSA assumption:

Given a randomly chosen RSA modulus $$n$$, and a random $$z \in \mathbb{Z}_n^{*}$$, find $$r>1$$ and $$y \in \mathbb{Z}_n^{*}$$ such that $$y^r=z$$.

In the strong RSA assumption usually they say that "$$r$$ may be chosen in a way dependent on $$z$$, while in the usual RSA assumption $$r$$ can be chosen in a way independent of $$z$$".

What is meant by in a way dependent on $$z$$? How can one achieve such dependancy? I'm very grateful if someone can explain this.

Even by substituting some values to $$n$$, $$z$$ etc. would be great and would help me to understand more.

Thanks a lot in advance.

## 1 Answer

What is meant by "$$r$$ may be chosen in a way dependent on $$z$$"?

An hypothetical algorithm $$\mathcal A_2$$ breaking the strong RSA assumption has input¹ $$(n,z)$$ with $$n$$ generated by the RSA key generation procedure, and outputs² $$(r,y)$$ such that $$y^r\equiv z\pmod n$$, with the only other constraint on $$r$$ that $$r>1$$. Contrast with an hypothetical algorithm $$\mathcal A_1$$ breaking the RSA assumption, which has input¹ $$(n,r,z)$$ with $$(n,r)$$ generated by the RSA key generation procedure, and outputs² $$y$$ such that $$y^r\equiv z\pmod n$$.

The distinction makes the problems different: an hypothetical algorithm $$\mathcal A_2$$ that builds $$r$$ as $$r\gets n$$ is of no obvious use to break RSA, since that choice of $$r$$ is never used by a standard RSA key generation procedure³. Same if $$\mathcal A_2$$ was generating $$r$$ as a function of $$z$$, e.g. $$r\gets2\,\lfloor z/7\rfloor+3$$, because that $$r$$ has vanishingly low probability to match the $$r$$ generated by an RSA key generation procedure.

In the other direction, we can turn an hypothetical algorithm of the $$\mathcal A_1$$ kind into one of the $$\mathcal A_2$$ kind, e.g. by repeatedly trying incremental odd $$r\ge3$$, submitting $$(n,r,z)$$ to $$\mathcal A_1$$ used as a subprogram, and if within some time limit it outputs an $$y$$, giving $$(r,y)$$ as output of our $$\mathcal A_2$$.

The strong RSA assumption (which is that there exists no algorithm² $$\mathcal A_2$$) is thus a no weaker assumption than the RSA assumption (which is that there exists no algorithm² $$\mathcal A_1$$). These different notions are soundly named!

¹ Making implicit the security parameter which can be taken as the bit size of $$n$$, and the random input for randomized algorithms.

² With non-vanishing probability of success within time polynomial w.r.t. the security parameter.

³ It is used by the C.C. Cocks cryptosystem, which predates RSA, and is believed just as secure.

• Thank you very much @fgrieu – Bob Traver May 18 '20 at 7:37