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

Question

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?

Answer 1

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.

Answer 2

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}$$