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 '15 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 '15 at 11:49

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$ Jan 26 '15 at 12:36

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.