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

• 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 '19 at 7:42
• Yes - $A$ is public. I updated the question with this and one other clarification. – irakliy Jan 11 '19 at 8:12
• How are considering to do this with CT? – Youssef El Housni Jan 15 '19 at 10:09

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.
• Using bit decomposition will work - but I was trying to see if there is a more efficient way to do it somehow (it appears there might not be). The reason I wanted to do this is: if $a$ is divisible by 2, then $a/2 < q / 2$. This makes commitment to $a$ additively homomorphic. Meaning, I can check that $A + B = C$ and not worry about overflows and underflows as long as each of these points is backed by values that is less than $q/2$. – irakliy Jan 21 '19 at 7:58