4
$\begingroup$

Suppose we have an RSA groug $G=\mathbb{Z}^{*}_{N}$, where $N=pq$ , where $p,q$ are primes. Let $g$ be a random element of $G$ and $t\in \mathbb{Z}^{*}_{N}$. Having $g$ and $g^t$, it seems to be very hard to find $g^{t^{-1}}$, supposing discrete logarithm problem (DLP) is hard. My question is that is this really hard?

In a prime order group, let's say in $\mathbb{Z}^{*}_p$ , $g^{t^{-1}}$ = $g^{p-2}$ : here we don`t have to face DLP, so finding $g^{t^{-1}}$ is easy.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Actually, in a prime order group, computing $g^{t^{-1}}$ is known to be equivalent to the computational Diffie-Hellman problem; that is believed to be a hard problem in some prime-order groups. $\endgroup$ – poncho Dec 2 '15 at 23:14
  • $\begingroup$ Just adding a reference to @poncho: citeseerx.ist.psu.edu/viewdoc/…. However, it appears to me that the reduction works in prime-order groups where all values are generators (except for the unity). It doesn't appear to work otherwise (unless you can show that a non-negligible number are generators). $\endgroup$ – Yehuda Lindell Dec 3 '15 at 11:32
  • $\begingroup$ Multiplication modulo an RSA number is not a group, because multiples of $p$ and $q$ are not invertible mod $N$. RSA numbers instead form a ring. $\endgroup$ – Myria May 11 '20 at 19:09
  • $\begingroup$ Also, isn't this question equivalent to the RSA problem? If $t^{-1}$ exists mod $\phi(n)$, then $t$ is an RSA public exponent and $t^{-1}$ is its matching private exponent. $\endgroup$ – Myria May 11 '20 at 19:16
2
$\begingroup$

I know that I am not exactly answering your question, but I am pointing you in a potentially interesting research direction. Your question is not standard in the area of discrete log and Diffie-Hellman problems since you are considering a cyclic group of order $p\cdot q$ where $p$ and $q$ are primes. (Typically, we like looking at group of prime order.)

Your question is actually asking whether you can reduce this problem to solving the discrete log problem. I don't have any answer to that, but it reminds of an old paper by Biham, Boneh and Reingold that shows that the Diffie-Hellman problem modulo $N=pq$ (for Blum integers) is actually equivalent to factoring. This isn't the same thing, but there's something similar. The paper is here: https://omereingold.files.wordpress.com/2014/10/cgdh.pdf.

Improve this answer
$\endgroup$

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.