# Given $g,g^t$ in a cyclic group of order $pq$, is it hard to compute $g^{t^{-1}}$?

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.

• 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. – poncho Dec 2 '15 at 23:14
• 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). – 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.