2
$\begingroup$

Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e>2$, with $n$ being a composite integer and unknown $x$.

Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to factor $n$, in the same way that the multiplicative order of $x \space modulo\space n$ can be used to factor $n$ like in the classical part of Shor's algorithm?

$\endgroup$

1 Answer 1

2
$\begingroup$

The RSA problem, which you describe, is not known to be equivalent to factoring and there is evidence both ways. In [BV] it is shown that this barrier might be inherent: using a black-box separation technique called meta-reductions, they show that certain restricted class of reductions are not possible. On the other hand, it was shown later in [AM] that in the generic ring model (see [JS]), these problems are equivalent. That is, any speed-up in breaking RSA has to exploit the representation of $\mathbb{Z}_N^*$.

You can read about more related works in §1.3 in [AM].

[BV]: Boneh and Venkateshan, Breaking RSA may not be equivalent to factoring, Eurocrypt'98

[AM]: Aggarwal and Maurer, Breaking RSA Generically Is Equivalent to Factoring, Eurocrypt'09

[JS]: Jager and Schwenk, On the Analysis of Cryptographic Assumptions in theGeneric Ring Model, Asiacrypt'09

$\endgroup$
1
  • $\begingroup$ Thank you very much. $\endgroup$ Commented Jul 10, 2020 at 7:21

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.