# 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!

-
Is "$log$" the base-2 logarithm $log_2$? Is "$log$ $k =$$> n$" equivalent to "$k\ge q$"? –  fgrieu May 21 '12 at 10:59
yes, $log_2$ and the second one is a typo, supposed to be $log$ $k = n$ (wasn't even a typo the block quote > messed it up.. –  Sup3rgnu May 21 '12 at 13:06
If $log_2(q)=n$ and $log_2(k)=n$, we have $q=k$. Is that supposed to be $\lceil log_2(q)\rceil=\lceil log_2(k)\rceil=n$ or something on that tune? –  fgrieu May 21 '12 at 13:19
If "the bit size of every prime factor of $k$ is bounded by $log_2(log_2(k))$" (give or take a few roundings to integer), then $k$ is exceptionally smooth; e.g. if $k$ has 1024 bits, all its factors are at most 1021. Is that meant? –  fgrieu May 21 '12 at 13:30
The property that you can use to find $x$ is the smoothness of $k$ pointed out by fgrieu, as you can solve the discrete logarithm problem in very small subgroups of $\mathbb{F}_p^\times$ (your notation: $Z_p^*$) by inspection, and assemble those using the CRT. –  j.p. May 21 '12 at 16:26

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 < 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' > 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...

-
Thanks man, I don't fully get it but def have a better picture now, thanks a lot appreciate it! –  Sup3rgnu May 25 '12 at 20:26
@Sup3rgnu: You're welcome. If you have specific questions to any of the steps, you can leave a comment here, which I'll try to answer. –  j.p. May 26 '12 at 11:59