# Why isn't f(G) uniform in ECDSA?

In ECDSA, $$f(G)=r$$, where $$r$$ is the $$x$$-coordinate of group element $$G$$. My question is, how to prove this $$f$$ is not uniform? In other words, how to prove that, given a random element $$G$$ with different x-coordinates on an elliptic curve, $$r=f(G)$$ is not uniform over $$\mathbb{Z}_q$$? I would like to stress that here we see the group elements that share the same x-coordinate as the same ones.

I know in the paper ''On the Provable Security of (EC)DSA Signatures'', the author has talked about this. But I could not understand what they mean("On elliptic curves, for only about every second $$x$$-value a corresponding curve point exists; this is responsible for a huge bias of the $$x \bmod q$$ function"?). Can anybody give a more clear explanation?

Hasse's bound tells that the order $$n$$ of [that is, number of elements in] an Elliptic Curve group is about the same as the order $$p$$ of the underlying field [note: $$x$$ and $$y$$ coordinates are elements of the field, points $$(x,y)$$ are elements of the group].

For every $$x$$ in the field with $$(x,y)$$ in the group, there is exactly one other point in the group with the same $$x$$: $$(x,-y)$$.

Therefore, about one value of $$x$$ in the field out of two is such that there exist $$y$$ in the field with $$(x,y)$$ [and $$(x,-y)$$] in the group. Like, if you have $$n$$ nuts and $$p$$ persons, with $$n\approx p$$, and you give two nuts to each person, then only about half the persons get a nut.

Therefore, $$f$$ as defined in the question is not uniform in the field, for it only reaches about half of the field elements.

• I Got it, thanks! – user77340 Feb 16 at 11:47

In Elliptic Curves for every point $$P=(x,y)$$ (here represented in Affine Coordinates), has the negative (or reflected) point $$-P = (x,-y)$$, there is one if $$y=0$$. Therefore for every $$x$$ satisfies the equation appears two times (almost). This can be seen from the short Weierstrass equation;

$$y^2 = x^3 + ax +b$$

If $$y$$ is a solution with the $$x$$ then $$-y$$ is also a solution and can be seen from the graph as the symmetry.

Or you can see it from the discrete case, too. See the symmetry around the middle line.

Therefore, every $$x$$ that satisfies the equation has a double change to occur, however, some $$x$$ values don't satisfy the equation at all. The exact number depends on the curve, however, there is a Hasse Bound for this

$$|\#|E(q)| - (q+1)| \le 2 \sqrt{q}$$

• I got it, thanks! – user77340 Feb 16 at 11:47