The difficulty of following discrete logarithm problem. For $m,m′$, is it possible to find $r, s, t$ such that $r^s = m$ and $r^t = m'$ for some $r, s, t$ in modulo of large $G$?
Can this problem be considered equally hard as the ordinary discrete logarithm problem? Or is there an easier way to generate such $r, s, t$ from the arbitrary $m$ and $m'$? 
 A: If you are willing to additionally require that $r$ is of order $p$ modulo $G$ for a known (large) prime $p$ (this can be guaranteed, e.g., by switching your setting and working in a group $G$ of prime order), it can be shown by a reduction that your problem is at least as hard as the discrete logarithm problem: Assume $\mathcal{A}$ is an algorithm that efficiently solves your problem. You can use $\mathcal{A}$ to compute the discrete logarithm of an element $h$ to the base $g$ as follows: Invoke $\mathcal{A}$ on input $m = g$ and $m' = h$. $\mathcal{A}$ will return $r$, $s$, and $t$ such that $r^s \equiv g$ and $r^t \equiv h$ modulo $G$. Now compute a number $x$ such that $x \cdot s \equiv 1 \pmod{p}$ (this can be done efficiently using the extended euclidean algorithm because $p$ is prime and therefore $s$ and $p$ are coprime). Then,
$$g^{x \cdot t} \equiv (r^s)^{x \cdot t} \equiv (r^{x\cdot s})^t \equiv r^t \equiv h \pmod{G}.$$
Hence, $x\cdot t$ is the discrete logarithm of $h$ to the base $g$.
Note that the discrete logarithm problem is at least as hard as your problem since if you can compute discrete logarithms to some base $r$, you can find $s$ and $t$ for given $m$ and $m'$ such that $r^s \equiv m$ and $r^t \equiv m'$ modulo $G$. Hence, the two problems are equally hard under the assumption that $r$ is of order $p$.
