3
$\begingroup$

In discrete log we employ sophie germain primes $p=2q+1$ where $q$ is a prime.

Then we know least significant bit $x_0$ in $$g^{2x+x_0}=h\bmod p$$ where $2x+x_0$ is discrete logarithm of known $h\bmod p$ with respect to known generator $g$.

  1. Suppose $g^2=r\bmod p$ then why cannot I reduce the problem to $$r^{x}=hg^{-x_0}\bmod p$$ and let $x=2x'+x'_{0}$ where $x'_0$ is lsb of $x$ and recursive solve the problem of finding $2x+x_0$ which is discrete log of $h\bmod p$ with respect to generator $g$?

  2. Suppose I know $x_0$ in $g^{3x+x_0}=h\bmod p$ where $x_0\in\{0,1,2\}$ holds (that is if it were easy to solve for the last ternary digit of discrete logarithm when $p=2q+1$ would the problem be any easier?

$\endgroup$
5
$\begingroup$

If $p = 2q+1$ where $q$ is prime, and then we can efficiently solve for $x_0 \in \{0, 1\}$ for $g^{2x+x_0} = h \pmod p$, if $g$ is a generator.

This is true; this is a special case of the observation "if $g$ has order $a \times b$ with $b$ small, then if $g^y = h$, then we can find $y \bmod b$ quickly (specifically, in $O(\sqrt{b})$ time).

As $g$ is a generator for the entire group, it has order $2q$, and so we can find $y \bmod 2$ quickly (or, as you put it, find $x_0$ where $y = 2x + x_0$)

Suppose $g^2 = r$, then why cannot I reduce the problem to $r^x = hg^{-x_0} \pmod p$

Well, I suppose you could, but solving that would be as difficult as the DLog problem (actually, that's provable; given an Oracle to do that, you can solve the entire DLog problem). The previous observation doesn't help you solve this problem; $r$ has order $q$, which is a prime; it doesn't provide any magic ways to compute $x \bmod 2$; the best it can do is find $x \bmod q$ in $O(\sqrt{q})$ time, and we have more efficient ways than that.

Suppose I know $x_0$ in $g^{3x+x_0} = h \pmod p$, which $x \in \{ 0, 1, 2 \}$, would that help.

Yes, if you had an Oracle that could find $y \bmod 3$, then you could efficiently solve the DLog problem. That said, we don't know any way to do that efficiently (assuming that the order of the group wasn't a multiple of 3).

$\endgroup$
  • $\begingroup$ I do not see how to solve DLog if you know how to fine $y\bmod 3$. Could you please explain a bit? $\endgroup$ – Turbo Apr 23 '17 at 17:31
  • $\begingroup$ @Turbo: well, you would find $y \bmod 3$, and then compute $h' = (h g^{-(y \bmod 3)})^{3^{-1} \bmod q} = g^{\lfloor y/3\rfloor}$ ($q$ is the size of the group). Then, giving $h'$ to the Oracle will give the next ternary digit, and repeat until you've read the entire value of $y$ in ternary. $\endgroup$ – poncho Apr 23 '17 at 17:36
  • $\begingroup$ you mean $\bmod (p-1)$ instead of $\bmod (q-1)$? $\endgroup$ – Turbo Apr 23 '17 at 17:42
  • $\begingroup$ @Turbo: I mean the size of the group; I tried to edit it to be $p-1$, but the 5 minutes edit limit had passed... $\endgroup$ – poncho Apr 23 '17 at 17:43
  • $\begingroup$ are there discrete logarithm schemes where even the last bit is secure? Or is that bit always insecure? $\endgroup$ – Turbo Jun 2 '17 at 1:40

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.