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

Question

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.

Answer 1

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