Relations between RSA and Generalized Diffie-Hellman (GDH), factoring and GDH

Question

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:

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.
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.
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$.)

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). — cpast, Commented Jan 3, 2015 at 17:24
@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. — poncho, Commented Jan 3, 2015 at 17:49
@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. — cpast, Commented Jan 3, 2015 at 18:09
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 — Squeamish Ossifrage, Commented Mar 8, 2019 at 6:02

István András Seres · Accepted Answer · 2020-05-11 19:12:59Z

2

Breaking the Generalized Diffie-Hellman (GDH) assumption is known to imply Factoring for Blum-integers. This is a result by Biham et al.
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.

answered May 11, 2020 at 14:13

1,1941 gold badge9 silver badges23 bronze badges

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
Commented May 11, 2020 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
Commented May 11, 2020 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
Commented May 11, 2020 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
Commented May 11, 2020 at 19:10

Add a comment |

1 Answer 1