Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
    
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
1  
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
show 7 more comments

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.