3
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I Got it, thanks! $\endgroup$ – user77340 Feb 16 at 11:47
2
$\begingroup$

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.

enter image description here

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

enter image description here

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

$\endgroup$
1
  • $\begingroup$ I got it, thanks! $\endgroup$ – user77340 Feb 16 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.