I have been struggling to find the algorithm $\mathcal{A}$ in the following. Let $(G,g,q)$ be the group parameter, $p << q$, $x\in \mathbb{Z}_q$, can we build the following algorithm:
$$\mathcal{A}(g,g^x,g^{x^k},p,q) = g^{y^k} \text{ where } y = \bigg \lfloor x \cdot \frac{p}{q}\bigg\rfloor \in \mathbb{Z}_p$$
can we build the following algorithm:
$$\mathcal{A}(g,g^x,g^{x^k},p,q) = g^{y^k} \text{ where } y = \bigg \lfloor x \cdot \frac{p}{q}\bigg\rfloor \in \mathbb{Z}_p$$
It would appear that such an algorithm that works for any input would allow us to compute discrete logs (hence we hope the answer is "no" in general, however it might be possible for certain inputs (although I personally have my doubts).
One way to do this to evaluate the discrete log of $g^x$ would be to start with evaluating $\mathcal{A}(g, g^x, g^x, 2, q)$ (that is, with $k=1$); if $x < q/2$, this evaluates to $g^0$, if $x \ge q/2$, this evaluates to $g^1$, thus halving the range of where $x$ might be.
Then, we would follow it up with $\mathcal{A}(g, g^x, g^x, 4, q)$, which would allow us to further halve the possible range of $x$. We could keep on going until we've recovered all of $x$, hence solving the DLog problem.
