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

Question

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 :).

Answer 1

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$

Answer 2

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.