4
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\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).

Improve this answer
$\endgroup$
12
  • $\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$ Commented Apr 23, 2017 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$ Commented Apr 23, 2017 at 17:36
  • $\begingroup$ you mean $\bmod (p-1)$ instead of $\bmod (q-1)$? $\endgroup$ Commented Apr 23, 2017 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$ Commented Apr 23, 2017 at 17:43
  • $\begingroup$ are there discrete logarithm schemes where even the last bit is secure? Or is that bit always insecure? $\endgroup$ Commented Jun 2, 2017 at 1:40

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.