Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
Is it hard to get Least Significant Bit for Elliptic Curve Discrete Logarithms?
For which cases is it hard to get Least Significant Bit for Discrete Logarithms?
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.
