Score:1

Is f(G) uniform under the described condition in ECDSA?

ie flag

In ECDSA, $f(G)=r$, where $r$ is the $$-coordinate of group element $G$. Now it is known that $f(G)$ is not uniform(Why isn't $f(G)$ uniform in ECDSA?). Then in which range $f(G)$ is uniform?

Let $\langle G\rangle$ be a cyclic group on the ECDSA elliptic curve with the generator $G$, and $S=\{x|f(W)=x,\forall W\in\langle G\rangle\}$. My question is: for any $W\overset{\\\$}{\leftarrow}\langle G\rangle$, is $f(W)$ uniform in $S$?

fgrieu avatar
ng flag
Hint: the question is _not_ an exact duplicate of the linked one, at least as understood in my [answer](https://crypto.stackexchange.com/a/88281/555). In the present question, $S$ is the set of $x$ actually reached by $f(W)$, when I answered about uniformity over the full base field (e.g. $[0,p)$ for secp256k1).
kelalaka avatar
in flag
@fgrieu my mistake, for $F_p$ one needs $p$ points to have a trivial uniformity, though, such curves are not secure at all.
user77340 avatar
ie flag
@fgrieu I have modified the title. How about now? The range just refers to the output of f.
kelalaka avatar
in flag
In general, it is not uniform, that is why we apply hash to mitigate those...
Score:3
ng flag

$f$ is defined as a function from the Elliptic Curve group to the finite field used to define the curve, yielding the X coordinate of the point considered. For the purpose of that definition, I'll assume the neutral of the group law (aka point at infinity, and noted $\infty$) has coordinates $(z,z)$, with $z$ a fixed element of the field such that for $x=z$ the curve's equation has no solution $y$ (for all standard curves over a prime field $\mathbb F_p$, and AFAIK all others, we can take $z=0$, where $0$ is the field's neutral).

The set $S$ is the image of the whole group $\langle G\rangle$ by $f$, thus a subset of the field including $z$.

$f$ is almost exactly uniform on $S$: the set $S$ has $(n-1)/2$ elements where $n$ is the (prime) order of $\langle G\rangle$, and each element of $S$ except $z$ has precisely two antecedents by $f$, sharing the same X coordinate. $z$ has a single antecedent, and that's $\infty$. From a cryptographic standpoint (thus with $n$ large enough that $\sqrt n$ is not enumerable), probability that an enumerable number of independent and uniformly random elements $W_i$ of $\langle G\rangle$ include $\infty$, collide, or have colliding $f(W_i)$ is negligible, and the $f(W_i)$ are (indistinguishable from) independent and uniformly random elements of $S$.

Argument: for a given $x$ in the field, the curve's equation becomes a fixed second degree equation, which in a finite field has zero, one or two distinct solutions. When $x\in S$, the case zero solutions occurs only for $x=z$, by definition of $f$ and $S$. The case of one solution does not happen for standard curves over a prime field (I know no exception for others¹, and if there was it would be exceptional anyway). That leaves two solutions as the only (or at least the overwhelmingly most common) case for $x\ne z$.


¹ That holds for curves with equation $y^2=x^3+ax+b$, which is the case for ECDSA using a prime field. Proof that holds for any ECDSA curve, or refutation, are appreciated.

Ruggero avatar
kr flag
Regarding ¹: those are points with $y=0$ and have order 2. I think that since we are discussing ECDSA, which requires invertible $k$, it makes sense to define it on a large prime order subgroup (given by the generator), otherwise some $k$ might not be invertible. In such subgroups there are no order 2 points.
fgrieu avatar
ng flag
@Ruggero: I follow you for curves with equation $y^2=x^3+ax+b$, which is the case for [ECDSA using prime field](https://www.secg.org/sec1-v2.pdf#subsubsection.2.2.1). However these is also $y^2+x\,y=x^3+ax^2+b$, which is the case for [ECDSA using binary field](https://www.secg.org/sec1-v2.pdf#subsubsection.2.2.2).
user77340 avatar
ie flag
Thank you for your answer! I just missed the fact that an x corresponds to two group elements.
Ruggero avatar
kr flag
@fgrieu You are right, sorry I missed that.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.