Suppose we have a group $G$ cyclic of order $pq$ , where $p,q$ are primes. Let $g$ be a generator of $G$ and $t\in \mathbb{Z}_{pq}$. 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 : is this really hard?

In order prime , let say $p$ , $g^{t^{-1}}$ = $g^{p-2}$ : here we don`t have to face DLP , so finding $g^{t^{-1}}$ is easy.

  • $\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

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.


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.