3
$\begingroup$

Definition: (The generalized Diffie-Hellman problem)

Let $n=pq$ for two large primes $p,q$. Given $x, x^a, x^b,n$, find $x^{ab}\pmod{n}$.

(1) Is there a known reduction from the GDH problem to the RSA problem (i.e. finding $m$ from $m^e\pmod{n}$)?

(2) Is there a known reduction from the GDH problem to integer factorization?

(That is, given an oracle which solves the second problem mentioned in (1)/(2), can you find an efficient algorithm which solves the GDH problem?)

Side-notes:

  1. There is of course a reduction from GDH to DLOG, but I do not know of a reduction from DLOG to integer factorization or to the RSA problem.

  2. It is known that the RSA problem limited to $e=2$ (i.e. finding square roots modulo $p$) can be reduced to integer factorization, but this is a non-interesting case. For a general $e$, AFAIK such reduction is not known.

  3. Also, I am just as interested to hear about DH instead of GDH. (The DH problem is the same as GDH, but with a prime $p$ instead of semiprime $n$.)

$\endgroup$
  • $\begingroup$ Unless I'm mistaken, the RSA problem is simple to reduce to integer factorization (factor $n$, compute $\varphi(n)$ with the factorization, compute $d=e^{-1}\pmod{\varphi(n)}$, compute $m=(m^e)^d\pmod{n}$; this is exactly how decrypting RSA is actually done). $\endgroup$ – cpast Jan 3 '15 at 17:24
  • 2
    $\begingroup$ @cpast: however, that reduction is the wrong direction; if you have a black box that solves the RSA problem, there is no known way to use it to efficiently factor. This leaves open the possibility that the RSA problem is easier than factoring. $\endgroup$ – poncho Jan 3 '15 at 17:49
  • $\begingroup$ @poncho Then the statement should be "there is no known way to reduce factorization to RSA," not vice versa. So if DLOG reduced to RSA it would reduce to factoring, but not necessarily vice versa. $\endgroup$ – cpast Jan 3 '15 at 18:09
  • $\begingroup$ Who says $e = 2$ is non-interesting? $e = 2$ is great! Best performance (when $p \equiv q \equiv 3 \pmod 4$, anyway), clearest connection to factoring, More: cr.yp.to/papers.html#rwsota $\endgroup$ – Squeamish Ossifrage Mar 8 at 6:02

Your Answer

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

Browse other questions tagged or ask your own question.