1
$\begingroup$

Studying the Baby-Step/Giant-Step Algorithm, I have some questions:

  1. In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\rfloor$, rather than something else like $\lfloor {p/2}\rfloor$?

  2. (a) The time complexity is $O(\sqrt{p})$. If we make sufficient large $p$, then why is it difficult for compute the discrete logarithm computation in group $G$ of such order $p$?
    (b) It is said that the discrete logarithm computation is hard in group of prime order, particularly in subgroup (order $q$) of group of strong prime order (like order $p = 2*q + 1$, $q$ and $p$ is prime); why is that?

$\endgroup$
  • $\begingroup$ can you explain more detail about 2(b) ? I read the Polih-Hellman, is it because subgroup of prime order q is hard to compute , thus it cannot apply the Chinese remainder theorem to recover the final solution x ?Is there no any efficient algorithm to solve DLP in group of prime order? $\endgroup$ – Laura Apr 2 at 14:13
3
$\begingroup$
  1. In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\rfloor$, rather than something else like $\lfloor {p/2}\rfloor$?

The time taken by Big Step-Little Step is $O( m + p/m )$ (the $O(m)$ term comes from the time taken iterating through the various $k$ values, the $O(p/m)$ term comes from the time taken iterating through the various $i$ values.

It should be easy to see that that time is minimized if $m \approx \sqrt{p}$

  1. (a) The time complexity is $O(\sqrt{p})$. If we make sufficient large $p$, then why is it difficult for compute the discrete logarithm computation in group $G$ of such order $p$?

If $p$ is quite large, then $\sqrt{p}$ is also large (even if it isn't as large as $p$); for example, if we want $\sqrt{p} \ge 2^{128}$ so that the number of steps that Big Step-Little Step takes is infeasibly large, we just take $p \ge 2^{256}$.

Just one note: if we're working in the group $\mathbb{Z}^*_p$, then there are other attacks against the Discrete Log problem other than the generic Big Step-Little Step (and Rho) algorithms; hence we generally need a much larger $p$

  1. (b) It is said that the discrete logarithm computation is hard in group of prime order, particularly in subgroup (order $q$) of group of strong prime order (like order $p = 2*q + 1$, $q$ and $p$ is prime); why is that?

If we are working in the group $\mathbb{Z}^*_p$ (that is, the multiplicative group modulo $p$), well, that group has a size $p-1$; any prime subgroup will have a size $q$ which is a divisor of $p-1$. One way (but not the only way) to make sure that there is a good $q$ is to make $p$ a "safe prime", that is, a prime such that $q = (p-1)/2$ is also prime.

On the other hand, that applies only to the group $\mathbb{Z}^*_p$; if you go to (say) Elliptic Curve groups, there is no corresponding reason to prefer safe primes (either for the characteristic or the group size).

$\endgroup$
  • $\begingroup$ Thank you for your answer!But I still confuse that why discrete logarithm computation is hard in group of prime order ? is it because from which we cannot use efficient algorithm like Rho algorithms? $\endgroup$ – Laura Apr 3 at 11:19
  • $\begingroup$ @Laura: why the dlog problem is hard for some groups? Well, no one really knows that; all we know is that there are groups where the best known algorithm is infeasible. Now, if we're working on a group with a composite order of known factorization, we can solve it by solving the dlog group in the various prime subgroups; hence it is considerably easier than a group of prime order of about the same size; hence we prefer groups of prime order. BTW: the (Pollard) Rho algorithm is a generic one; it takes a constant factor more computation than Big Step/Little Step, but takes far less memory... $\endgroup$ – poncho Apr 3 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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