# Proving that the least significant bit of an elliptic curve discrete logarithm is $0$

Suppose I have a secret value $$a$$ which maps to a public point on an elliptic curve $$A = a \cdot G$$, where $$G$$ is a generator of the elliptic curve of primer order $$q$$.

Can I prove to someone that the least significant bit of $$a$$ is $$0$$ using a non-interactive proof that does not expose the value of $$a$$? If I can, what would be the most efficient (in terms of proof size) way to do it?

Edit: this can probably be done using bit commitments (something similar to Confidential Transactions), but in this case, proof sizes are likely to be close to 10KB. Is there a way to do this more efficiently? Maybe somehow relying on the fact that $$a$$ is even?

Edit2: I've been reading a bit about Division Polynomials and I'm wondering if it is possible to use them somehow to prove that $$a$$ is even.

## This question has an open bounty worth +100 reputation from irakliy ending in 3 days.

This question has not received enough attention.

I'm looking for a proof that is less than 1KB in size.

• I assume $A$ is public? You can certainly do this using standard generic zero-knowledge proofs, since this is an NP statement. There might be a much more efficient way for this specific example, though. – Noah Stephens-Davidowitz Jan 11 at 7:42
• Yes - $A$ is public. I updated the question with this and one other clarification. – irakliy Jan 11 at 8:12
• How are considering to do this with CT? – Youssef El Housni Jan 15 at 10:09

Maybe this works. Let $$A=aG$$ and $$a=a_0+a_12+a_22^2+\dots+a_{k-1}2^{k-1}$$. You want to prove that $$a_0=0$$. If it is true, then $$A=2P$$ with $$P$$ some point on the curve, otherwise $$A=G+2P'$$ with $$P'$$ some other point in the curve. So for the proof you just give the point $$P$$ and the verifier checks that $$A-2P=\mathcal{O}$$. You get the $$P$$ point when computing $$A$$ using double-and-add algorithm.
• If $a_0=1$ then there is still a point $P$ s.t. $A-2P=\mathcal{O}$. You just have to compute $P=\frac{a}{2}*G$ with $\frac{a}{2}=a*2^{-1} \mod q$ – Ruggero Jan 15 at 11:40
• This doesn't quite work. Here is an example. For $q=11$, $a = 5$, and $p = 8$, we still get $A-2 \cdot P=\mathcal{O}$ because $(5 - 2 \cdot 8) \bmod 11 = 0$. – irakliy Jan 15 at 17:11
• @irakliy $P$ is a point not the base field modulus $p$. Anyway, it is not working. – Youssef El Housni Jan 15 at 17:14