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&gt;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.
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&gt;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.