Given $g^X\bmod q$ for a prime $q$ where $g$ has odd order and an integer is it possible to compute $g^{a^X}\bmod p$ using polynomially many Diffie-Hellman operations and $\{+,-,\times,/\}$ operations?
$X$ is positive and at most order of $g$.
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I assume the question is asked for unknown $X$.
In general, $g^{(a^X)}\bmod q$ is not uniquely defined given prime $q$, $g$ of odd order $n$, $a$, and $g^X\bmod q$. That makes it impossible to reliably compute $g^{(a^X)}\bmod q$ from these givens.
Example: $q=71$, $g=57$, $a=2$, $g^X\bmod q=25$: $g^{(a^X)}\bmod p$ can be any of $5$ (e.g. for $X=18$), $25$ (e.g. for $X=3$), $54$ (e.g. for $X=13$), or $57$ (e.g. for $X=8$).
Therefore something must be missing from the question. Perhaps: that $X$ is in $[1,n]$, which makes $X$ uniquely defined.
Also, the question becomes easy if we can find $X$, and nothing in the question implies this is hard. So we are probably missing that the order $n$ of $g$ has a large-enough prime factor $p$ to defeat attacks of cost $\mathcal O(k\sqrt p)$ group operations (where $k$ is the multiplicity of $p$ and in practice small); and that $q$ is large enough to defeat NFS.
Yet other conditions are required to make the problem hard, like $(a\bmod n)\not\in\{0,1\}$.
When enough appropriate conditions are met, we don't know a significantly better method than finding $X$ by whatever method works best considering the magnitude of $q$ and the factorization of the order $n$ of $g$, then $Y=a^X\bmod n$, then $g^{(a^X)}\bmod q=g^Y\bmod q$.
