Proving that a point on elliptic curve is smaller than half of group's order

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.

• 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$? – kelalaka Dec 26 '18 at 10:56
• 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$? – VincBreaker Dec 26 '18 at 11:44
• 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$. – fkraiem Dec 26 '18 at 11:59
• @fkraiem - indeed, that's what I've meant. I've updated the question to make this more clear. – irakliy Dec 26 '18 at 17:29
• 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) – poncho Dec 26 '18 at 21:03