It is hard to get Least Significant Bit for Discrete Logarithm systems with composite moduli. However this is because of the hardness of the factoring problem.

  1. Is it hard to get Least Significant Bit for Elliptic Curve Discrete Logarithms?

  2. For which cases is it hard to get Least Significant Bit for Discrete Logarithms?

  • 2
    $\begingroup$ There are not a lot of even primes, this might make the LSB easy to get in some cases $\endgroup$ – daniel Jul 15 '17 at 12:51

For any discrete log problem where the order of the generator is even and known, then the lsbit is easy to recover.

Notation I'll use:

  • I'll be writing things in additive notation (the notation we typically use for Elliptic Curves). This is just notation; these ideas translate directly to multiplicative groups.

  • I'll designate the generator used as $G$, and the order of $G$ as $n$; the problem we're given is, given $H$, find $x$ (or the lsbit of $x$) with $H = xG$

And, in this subcase, we assume $n$ is even.

So, to recover the lsbit of $x$, we just compute $(n/2)H$; if this is the identity element, this $x$ must be even; if this is not, then $x$ must be odd.

Next case; for any discrete log problem where the order of the generator is odd and known, then the lsbit is a 'hard bit'; that is, recovering that lsbit is as hard as recovering the entire exponent.

We show this by demonstrating that, if we were given an Oracle that gave us the lsbit, we can use that to recover the the entire exponent.

We start by finding the lsbit of $x$; given $H$, we can query the Oracle directly, giving us $x \bmod 2$.

Now, to find the next bit; we compute $H' = (2^{-1} \bmod n)(H - (x \bmod 2)G) = (\lfloor x/2 \rfloor) G$; we can then query the Oracle with $H'$; this gives us the second bit of $x$.

We can repeat this process, and read all the bits of $x$ in succession.

(This is a bit more complex if the Oracle we get is probabilistic; I won't bother you with the details)

The last subcase is if the order of the generator is unknown. If we're talking about multiplication modulo a composite, then if the generator has a Jacobi symbol of -1, then it is easy (compute the Jacobi symbol of $H$; if it is 1, then $x$ is even, if it is -1, then $x$ is odd).

And, as Geoffroy Couteau points out, in the case that the Jacobi symbol is 1, this is reducible to the quadratic residuosity assumption:

  • If the generator $G$ is a quadratic nonresidue, then $H$ will be a quadratic residue iff the lsbit of $x$ is even; an oracle that is able to determine the lsbit of $x$ will allow us to the test whether $H$ is a quadratic residue.

  • If we had an oracle which worked in the case that $G$ is a quadratic residue (but not if it is a QNR, as above, that's a hard problem), then that could be used as a test to determine whether $G$ is a quadratic residue; generate a random value $x$, compute $H = G^x$, and give $G, H$ to the oracle; if it gives us the correct lsbit of $x$ on a consistent basis, then $G$ must be a quadratic residue.

  • $\begingroup$ 1. if the oracle is probabilistic do we use randomized self reduction? $\endgroup$ – 1.. Jul 15 '17 at 23:47
  • $\begingroup$ 2. how hard is it compute Jacobi symbol (say if moduli is rsa semiprime $pq$)? $\endgroup$ – 1.. Jul 15 '17 at 23:49
  • $\begingroup$ @Turbo: it's easy (polynomial time, circa the same amount of time as to do a modular exponentiation) to compute the Jacobi symbol. $\endgroup$ – poncho Jul 16 '17 at 3:01
  • $\begingroup$ @poncho: when the Jacobi symbol is 1, isn't finding out whether the exponent is odd or even exactly the quadratic residuosity assumption? $\endgroup$ – Geoffroy Couteau Jul 16 '17 at 9:30
  • $\begingroup$ @GeoffroyCouteau: good point; in the case where the generator is a NQR, that's precisely the case, and in the case where the generator is a QR, any such method that worked could be used as a test to see if the generator is a QR. $\endgroup$ – poncho Jul 16 '17 at 16:08

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.