2
$\begingroup$

I am studying a script on the mathematical foundations of cryptography as part of which I am currently trying to wrap my head around some basic cryptographic reductions. I am stuck on one problem that I would like to request some help / advice on how to proceed:

Consider the (D)iscrete (L)ogarithm problem for a group $H = \, < \negmedspace h \negmedspace >$ of even cardinality $\lvert H \rvert = 2 n$. Show that there exists an efficient algorithm that computes the LSB of $x$ in the DL problem $y = h^x$.

So far the only thing I managed to come up with is the following: We can determine the order of $y$ and find $c$ s.t. $y^c = h^{x c}= 1$. Since the group caridnality is even we conclude that $x c = m 2 n$. If $c$ is odd we can therefore conclude that $x$ must be even and hence the LSB of $x$ is zero. How can I proceed from here? The only additional insight I can present is, that due to Lagrange, we know that $c$ divides $2 n$.

$\endgroup$
1
$\begingroup$

Write $x=x_0+2x_1$ for $x_0\in\left\{0,1\right\}$, so that the goal becomes determining $x_0$. Now compute $y^n$ (in terms of $h$, $x_0$ and $x_1$), and determine its order. What happens when $x_0=0$ and when $x_0=1$? Can we easily differentiate between them?

Note that this is the idea underlying the Pohlig-Hellman algorithm, so it may help to have a look at that.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for this insightful answer! I must confess given the elegance of the argument I wish I had arrived at this result myself ;) $\endgroup$ – R.G. Nov 26 '16 at 13:31
  • $\begingroup$ Yes it is indeed an elegant argument, there is still much satisfaction to be gained by generalizing this! Can you find the two least significant bits when $|H|=2^2n$? How about an analogue when $|H|=2^{1000}n$? How about $|H|=p^mn$ for some prime $p$ and integer $m$? You are then very close to explaining how the Pohlig-Hellman algorithm works, which is great! $\endgroup$ – CurveEnthusiast Nov 26 '16 at 13:41
  • $\begingroup$ Thanks for this information. Sounds enticing; I'll have a look into it as soon as I'll find the time. $\endgroup$ – R.G. Nov 26 '16 at 13:44

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.