Informally, the hardness of RSA/Strong RSA assumption lies in the hardness of factoring a large composite number $N$ having two large primes as its factors. If RSA modulus $N$ is a prime number, then the system is trivially breakable.

But, what about this variant of the Strong RSA problem presented in Ben Lynn's PhD dissertation? Here it says, given $c$, it's hard to find a pair $(g,a)$ such that $c = g^a$. RSA modulus $N$ hasn't been talked about here.

Are the above two notions synonymous?

  • $\begingroup$ What about just outputting $\:(c,\hspace{-0.04 in}1)\;$? $\;\;\;\;$ $\endgroup$
    – user991
    Jan 26, 2015 at 11:46
  • $\begingroup$ @RickyDemer That actually seems to be an error in Ben Lynn's PhD thesis: It talks about $a$ being chosen from $\mathbb Z_{r-1}^+$, which includes $1$. Therefore, the "strong RSA problem" as defined in the thesis is trivial. Do I miss something here? $\endgroup$
    – yyyyyyy
    Jan 26, 2015 at 11:49

1 Answer 1


The modulus $N$ is implicit in the group $\mathbb Z_N^\ast$ that $c$ and $g$ are chosen from. That is, in this context, $g^a$ is taken to mean "the residue class represented by $x^a\bmod N$ where $x$ denotes some representant of $g$'s residue class".

Therefore, when additionally requiring that $a\geq3$ and odd, this notion is equivalent to the strong RSA assumption as defined in Rivest's paper.

  • 1
    $\begingroup$ It sounds like a generic version of Quadratic Residue problem. I wonder whether there's any nomenclature for that. $\endgroup$
    – sherlock
    Jan 26, 2015 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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