2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much @fgrieu $\endgroup$ – Bob Traver May 18 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.