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?

  • 1
    $\begingroup$ How does this prove that $a < \text{Order}(G)$? $\endgroup$ – poncho Jan 21 '19 at 18:29
  • $\begingroup$ 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$? $\endgroup$ – yyyyyyy Jan 21 '19 at 18:30
  • $\begingroup$ @poncho - I don't think it does. Would that be a problem? $\endgroup$ – irakliy Jan 21 '19 at 18:48
  • $\begingroup$ @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. $\endgroup$ – irakliy Jan 21 '19 at 19:00
  • 1
    $\begingroup$ 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... $\endgroup$ – poncho Jan 21 '19 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.