# Using division polynomials to prove that EC discrete log is even

This question is related to the other question I recently asked. I'm trying to figure out if it is possible to use division polynomials to prove that knowing $$A = a \cdot G$$ we can prove that $$a$$ is even without disclosing the value of $$a$$.

One useful property of division polynomials that I've observed is that:

$$\psi_{nk}(G) = \psi_k(G)^{n^2} \cdot \psi_n(k \cdot G)$$

For even division polynomials this can be re-written as:

$$\psi_{2k}(G) = \psi_k(G)^4 \cdot \psi_2(k \cdot G)$$

If we define $$a = 2k$$ and $$A' = A / 2$$, and assuming coordinates of $$A'$$ are $$(x_{a'}, y_{a'})$$, we can re-write this as:

$$\psi_{a}(G) = \psi_k(G)^4 \cdot \psi_2(A') = \psi_k(G)^4 \cdot 2y_{a'}$$

Using this we can prove that $$a$$ is even by doing the following:

1. Prover computes $$s = \psi_{a}(G)$$ and $$v =\psi_k(G)$$ and shares $$(s, v)$$ with the verifier.
2. The verifier computes $$A/2$$ and verifies that $$s = v^4 \cdot 2y_{a'}$$

Are there any flaws in this approach?

• How does this prove that $a < \text{Order}(G)$? – poncho Jan 21 '19 at 18:29
• Can't I just pick any random $v$ and compute $s$ to make the verification equation work? How would the verifier check that indeed $s=\psi_a(G)$ and $v=\psi_k(G)$ without knowing $a$ or $k$? – yyyyyyy Jan 21 '19 at 18:30
• @poncho - I don't think it does. Would that be a problem? – irakliy Jan 21 '19 at 18:48
• @yyyyyyy I thought it would be possible to prove these using relation $x_a = x_g - \frac{\psi_{a-1}(G) \cdot \psi_{a+1}(G)}{\psi_a(G)^2}$ - though, I haven't thought it through completely. – irakliy Jan 21 '19 at 19:00
• It would be a problem; after all, given $a$ s.t. $A = a \ G$, we have $a' = a + \text{Order}(G)$ where we also have $A = a' \ G$, and (assuming the order of $G$ is odd), one of $a, a'$ is even and the other odd. So, if the original $a$ happens to be odd, he could substitute $a'$, and the protocol would claim that "a" is even... – poncho Jan 21 '19 at 22:03