# How can I solve the discrete logarithm modulo 2q+1 if I can solve it in the subgroup of order q?

As part of my cryptography course I came across an exercise that neither me or my friends could figure out.

The problem statement is as follows:

Let $p$ be a large prime of the form $p = 2q + 1$ with $q$ also prime. Let $g$ be a generator of $\mathbb Z^∗_p$ and consider the discrete logarithm problem: given $h = g^x$, find $x$.

Let $G_q$ denote the subgroup of order $q$ and assume you have access to an oracle $O : G_q ×G_q \to \{0, 1\}$ that on input two elements $s, t \in G_q$ with $t = s^y$ returns the least significant bit of $y$. Design an algorithm (using the oracle) to solve the DLP in $G_q$ and an algorithm (again using the oracle) to solve the DLP in $\mathbb Z^∗_p$.

The first part of the question is fairly easy (solve DLP in $G_q$ with the oracle). However, we cannot figure out the second part.

I have solved the first part as follows:

Run the oracle on $t$. On output 0 you know that the LSB of $y$ is 0, hence $y$ is even. $s^y$ can therefor be written as $s^{2*y'}$, which is still equal to $t$. By taking the square root of $t$, $\sqrt(t) = s^{y'}$ I no longer now the LSB of $y'$, but I know it's 1 bit smaller than $y$.

Similarly if the LSB of $y$ is 1 I know I can write $t = s^{y} = s^{y'+1} = s^{y}s$, hence dividing $t$ by $s$ gives me a new pair $s',t'$ on which I can unleash the oracle.

If I repeat the steps above $log_2(q)$ times and store all the LSB's I have found $y$.

Any hints/clues/advice will be most appreciated :).

-
Welcome to Cryptography Stack Exchange. I edited your question to use some TeX formatting, and tried to give a better title. Feel free to revert or edit again. –  Paŭlo Ebermann Jun 20 '12 at 17:51
It might help if you describe your solution to the first part ... I suppose the second part either is a variation of the first one, or based on it. –  Paŭlo Ebermann Jun 20 '12 at 17:51

Ok, lets try again from scratch. First, some group theory definitions:

• A group is a set of elements and an operation $\times$ which satisfies a specific set of properties (closure, associativity, an identity element, inverses)

• A subgroup is a subset of elements of a group which, along with the group operation from the main group, satisfies those same set of properties (closure, associativity, an identity element, inverses). Note that the subgroup uses the exact same group operation $\times$, except that it restricts the operands to the subset.

For a finite group $G$, a subset of elements $H$ is a subgroup iff the subgroup is closed; that is, if you take any two elements $h_1, h_2$, then $h_1 \times h_2$ is also an element of $H$.

Now, $\mathbb Z^∗_p$ is a group with $p-1$ elements; the operation $a \times b$ is defined to be $ab \bmod p$; this satisfies all the group properties.

Now, consider only those elements $x$ of $\mathbb Z^∗_p$ that can be represented as $x = y^2 \mod p$ for some value of $y$ (or, in other words, that quadratic equation has at least one solution for $y$). This turns out to be closed; that is, if we have two such elements $a = c^2$ and $b = d^2$, then $a \times b = ab = c^2d^2 = (cd)^2$ is also within this subset, and so these elements make up a subgroup. It turns out that this subgroup has $(p-1)/2 = q$ elements (and is the only subgroup of that size), and hence is the "subgroup of order q" of the question.

With that background in place, the question under discussion is: suppose we had an oracle that could, given values $s$ and $t$ that were point a part of this subgroup (that is, there are some values $u$ and $v$ such that $s = u^2$, $t = v^2$) it could give us the value $x$ such that $t = s^x \bmod p$ (note: this is $\bmod p$, not $\bmod q$, because the subgroup shares the same operator with the main group). Now, with such an oracle, how can we solve the DLP in the full group, that is, given $u$ and $v$, either of which may or may not be a member of the subgroup, how can we solve $v = u^x \bmod p$?

The first thing to note is if we define $s = u^2$ and $t = v^2$, both $s$ and $t$ are members of this subgroup. Hence, we can use the oracle to find $y$ with $t = s^y \bmod p$. Replacing the definitions for $s$ and $t$, we get $v^2 = u^{2y} \bmod p$. Now, if there is a solution $v = u^x \bmod p$, we know that $v^2 = u^{2x \mod p-1}$ (Fermat's Little Theorem), we know that either $2y = 2x \bmod p-1$, and since $p-1$ is even, either $y = x$ or $y + (p-1)/2 = x$

-
Thanks, that clears it all up. –  bambinoh Jun 21 '12 at 8:50

Ok, here's a hint: suppose you know that $t = s^y$ where you only know the lsbit of $y$.

Consider $t^2 = s^z$ (for some unknown $z$); you can use the oracle to find the lsbit of z. How are $y$ and $z$ related? How can you use your knowledge of the lsbit of $z$ to recover more information about $y$?

And, how can this observation be used repeatedly to recover all the bits of $y$? Hint: doing this trick $\log_2 q$ times is sufficient.

-
I see how to use your hint to get to the first solution (more or less), but I already had that :). I still don't see how to use it to calculate mod (2q+1) –  bambinoh Jun 20 '12 at 18:22
Oh, that's easy; if you have an oracle to solve the DLP in the subgroup of size $q$, you can solve the DLP problem in the full group. Hint: if you have the general DLP $t = s^y \bmod p$, consider the problem in $G_q$ $(t^2) = (s^2)^z \bmod p$. This is in $G_q$, as both $t^2$ and $s^2$ are quadratic residues. Now, how are $z$ and $y$ related? If we ask the oracle for $z$, how can we immediately find $y$? –  poncho Jun 20 '12 at 18:28
I'm not seeing it yet, but just for clarity, you mean $(t^2) = (s^2)^z\,mod\,q$, not $mod\,p$, right? –  bambinoh Jun 20 '12 at 18:37
@bambinoh: no, I mean $\bmod p$. $G_q$ is a subgroup of $\mathbb Z^∗_p$, hence the operations of elements within $G_q$ are also the operations within $\mathbb Z^∗_p$; that operation is $x \times y \bmod p$. The thing that distinguishes $G_q$ from $\mathbb Z^∗_p$ is that the elements within $G_q$ are a subset of the elements of $\mathbb Z^∗_p$ (specifically, the quadratic residues) –  poncho Jun 20 '12 at 18:54
Then how can I use my oracle in the subgroup? I think I'm missing some algebra to comprehend what you're trying to say –  bambinoh Jun 20 '12 at 18:56