Finding a solution to a (sort of) discrete logarithm by asking questions Let $p = kq + 1$ and $q$ be primes such that $log$ $q = n$, $log$ $k = n$ and such that the bit size of every prime factor of $k$ is bounded
  by $log$ $n$. Let $g$ be a generator of the unique subgroup of $Z^*_p$
  of order $q$.
  
  $x \in$ $Z_q$ is picked randomly and you get $y = g^x$. 
  
  You may ask any number of questions of the form $u \in Z^*_p$, which
  will be answered by $u^x$ $mod$ $p$.
  
  How would you go ahead to compute $x$ efficiently?


Solving the discrete logarithm problem would be nice, but I guess that's out of the question.. :) 

I don't get which properties that's given to use, (probably all of them) Any ideas/hints? Appreciate it!
I'll give a sketch of the solution to a quite similar problem (that makes more sense to me). The purpose of this modified problem is to show that it is essential to take $g$ of order exactly $q$ in the given setup, as one otherwise gets an oracle returning $u^x$ given $u$ as in your problem. (I'll show the connection between both problems (yours and mine) at the end of my answer.)


  Let $p = kq + 1$ and $q$ be primes such that $\log{q} \approx n$, $\log{k} \approx n$ and such that the bit size of every prime factor of $k$ is bounded
  by $\log{n}$. Let $g$ be an element of $Z^*_p$ of order $k'q = p-1$, where $k'\mid k$.
  
  $x \in$ $Z_q$ is picked randomly and you get $g$ and $y = g^x$. 
  
  How would you go ahead to compute $x$ efficiently?


1) Write $k = \prod_i r_i$ as product of (pairwise coprime) prime powers r_i.

As $k$ has only small prime factors, you can find this factorization.

2) Define $g_i := g^\frac{kq}{r_i} = g^\frac{p-1}{r_i}$, and find its order $s_i$ in $Z^*_p$, which has to be a divisor of $r_i$.

3) Set $y_i := y^\frac{kq}{r_i} = y^\frac{p-1}{r_i} \in \langle g_i\rangle$ and determine $x_i \in \{0, 1, \dots, s_i-1\}$ with $g_i^{x_i} = y_i$.

As $s_i$ is the power of a small prime $p_i$, you can find $x_i$ by finding first $x_i \bmod p_i$, then $x_i \bmod p_i^2, \dots$ (please tell me, if you need a further hint for this).

4) Convince yourself that $x_i = x \bmod s_i$ for all $i$, and use the Chinese remainder theorem to find $x'$ with $x' = x \bmod \prod_i s_i$ (by definition $k'=\prod_i s_i$). As $x &lt; q$ (we chose $x \in Z^*_p$), there are not many candidates $x' + l\cdot k'$ for $x$ as long as $\log k' \approx \log q$ (if $k' &gt; q$ one has $x = x'$).



You can get from your problem to mine by finding a generator $u$ of $Z^*_p$ (you are able to find this generators as you know/can find the factorization of $p-1$), and applying once your oracle to obtain $u^x$ (with the nice extra property $k=k'$). I use then the relation between $g$ and $y$ to get a special oracle: $g_i$ corresponds to $u$, and $y_i$ to $u^x$.



Final remark: Instead of picking the random $x$ in $\{0, \dots, q-1\}$ one can could pick $x \in \{0, \dots, p-2\}$ to prevent anyone from finding $x \bmod q$, but giving away unnecessarily information about one's random source doesn't feel good and wastes resources...