5
$\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 '19 at 6:02
2
$\begingroup$
  1. Breaking the Generalized Diffie-Hellman (GDH) assumption is known to imply Factoring for Blum-integers. This is a result by Biham et al.

  2. Since the (non)-equivalence of the RSA and Factoring assumptions is one of the biggest open questions in the RSA literature, it would be really surprising if there was a reduction from GDH to the RSA assumption, because then we would have the equivalence of the RSA and Factoring assumptions for Blum-integers given the result of Biham et al.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Nit: Biham et al did not show equivalence (nor did they claim it); instead, they showed that factoring reduces to the GDH problem - however, they did not show the other way around (and it would appear to be difficult to show; being able to factor N certainly does not imply you can solve the GDH problem modulo N; otherwise, an attacker wanting to solve the DH problem modulo a prime $p$ can pick a $q$, map the DH problem to a GDH problem modulo $pq$, and solve that using the known factorization of $pq$). Perhaps factoring other composites would help you solve GDH - it looks unlikely... $\endgroup$ – poncho May 11 at 18:48
  • $\begingroup$ If you can factor, then you can also compute DLOGs modulo N (www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf), hence you can break the GDH...no? $\endgroup$ – István András Seres May 11 at 18:56
  • $\begingroup$ Nope: the closest that paper comes is "if you can factor AND compute the DLOG modulo the primes, you can compute DLOGs modulo the composite" (that's point 3 of the abstract). It never says "if you can factor, you can compute DLOGs" (and indeed, being able to say that would be a significant advance) $\endgroup$ – poncho May 11 at 19:00
  • $\begingroup$ Aaahh...Thanks! so this was my misunderstanding. I thought Factoring and DLogs are equivalent in an RSA group. Updated the answer! $\endgroup$ – István András Seres May 11 at 19:10

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.