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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.