2
$\begingroup$

Let's say I have an elliptic curve where generator $G_1$ has prime order $q$. Let's also say I have committed to a point $A_1 = a \cdot G_1$. Could I use the scheme below to prove that $a < \frac{q}{2}$?


Suppose the order of the curve is $2q$ (the order is even) and there is another generator $G_2$ such that $G_1 = 2 \cdot G_2$. The order of the group for this generator is then the same as the order of the curve ($2q$). To prove that $a < \frac{q}{2}$:

  1. I compute $A_2 = (4a - 1) \cdot G_2$ and send it to the verifier.
  2. The verifier can then check whether $\frac{A_2+G_2}{2} = A_1$, and if so, accept my proof.

The thinking is that points generated by $G_1$ are equal to points generated by $G_2$ only for even multiples of $G_2$. So, unless $A_2+G_2$ is even, it won't match a point in $G_1$. And then, the checking equation becomes:

$$ \frac{(4a - 1) \cdot G_2 + G_2}{2} = 2a \cdot G_2 = a \cdot G_1 $$

I don't think I need to worry about overflow here since the division should take care of that.


The biggest thing I'm not sure about is how division by 2 would work on an elliptic curve of even order:

  • What would happen if we try to compute $\frac{3 \cdot G_2}{2}$ - would the result be undefined?
  • What would happen if we try to divide a "negative" point by 2? For example: $\frac{-2 \cdot G_2}{2} = -1 \cdot G_2$ and at the same time $\frac{-2 \cdot G_2}{2} = \frac{(2q-2) \cdot G_2}{2} = (q - 1) \cdot G_2$. But $q - 1 \neq -1 \bmod 2q$.

I must be missing something here.

$\endgroup$
  • $\begingroup$ Why the order of $G_2$ is $2q$. With this you can find an order greater then the group order. It should be $q/2$? $\endgroup$ – kelalaka Dec 26 '18 at 10:56
  • $\begingroup$ Also, are you sure that generators as $G_2$ actually exist? I have never heard of anything like that but that could be just my lack of knowledge. Why not use an existing range-proof on $A$? $\endgroup$ – VincBreaker Dec 26 '18 at 11:44
  • 1
    $\begingroup$ OP probably means that the curve's order is (a multiple of) $2q$ and that $G_2$ has order $2q$. In this case $G_1 = 2\cdot G_2$ does indeed have order $q$. $\endgroup$ – fkraiem Dec 26 '18 at 11:59
  • $\begingroup$ @fkraiem - indeed, that's what I've meant. I've updated the question to make this more clear. $\endgroup$ – irakliy Dec 26 '18 at 17:29
  • 1
    $\begingroup$ The thing that is confusing you is that, for $xG_2$ ($x$ even), there are two solutions to the point halving problem, $(x/2)G_2$ and $(x/2 + q)G_2$. Which one you get would depend on the exact algorithm you use to compute point halving (unless your algorithm returns both) $\endgroup$ – poncho Dec 26 '18 at 21: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.