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 prime 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.
Take a look at SNARGs, e.g. Bulletproofs (which are range proofs).
The proof may be slightly too large though.

Assuming that $a \in \{0, \ldots, q-1\}$ is your representative,
you want to prove is that you know a bit decomposition of $a$ with
$a = a_1 d_1 + a_2 d_2 + ... + a_k d_k$
where all $d_i$ are even and $\sum d_i = p-1$.
E.g. $d_i = 2^i$ but $d_k &lt; 2^k$ otherwise you can get wraparound.
This trick is found in some range-proof paper(s).
Without this, it may be possible to find, for odd $a$, a bit decomposition $a_i$ 
with $a' = \sum a_i d_i$, 
and $a'$ even (due to wraparound, $a = a' \mod q$).
Hence you don't get a proof for "(representative of) a is even".

One question though: Why is the last bit zero? If you just want to split
the exponents into two groups, using squares and non-squares is more efficient w.r.t. ZK.
It's simple and efficient to prove that $a = b^2$ (with standard sigma
protocols).

It seems hard to somehow express "is divisible by 2" efficiently,
because all calculations happen over finite fields, 
hence every (non-zero) element is invertible. 
So there is no such thing as "even and odd".
(Also: $1$ is odd, $1 + p$ is even, but $1 + q \equiv 1 (q)$.)
But: Polynomials make sense, e.g. squares $f(x, y) = x^2 - y$ 
or bits $f(b) = b (b-1)$. 
The vanishing/zero sets of polynomials are "algebraic", 
which helps in the group setting.