0
$\begingroup$

Simple question : given a randomly selected point $P$ belonging on a given Edwards curve defined on a prime field, does 2 scalars $S1$ $S2$ exist such as :

  • $packed(S1\cdot P)= packed(S2\cdot P$) (where packed means keeping only $x$ and dropping the $y$ coordinate but remember this is an edward’s curve where the negation of a coordinate is $(−x,y)$)
  • $S1≠S2$
  • Both $S1$ $S2$ are <targetcurve.Suborder (the largest prime factor of the composite curve’s order or the curve order if the curve is a prime which also appears to be the order of any randomly sample points)
  • if $S1$ and/or $S2$ are <0, then either S1+=targetcurve.Suborder and/or S2+=targetcurve.Suborder which of course is aking to saying they can’t be negative.

If yes, is it possible to compute such integer pair using a easier method than solving the elliptic curve’s discrete logarithm ?

$\endgroup$
8
  • $\begingroup$ (Suborder of the finite field used by the curve) curve order or in general order of points are unrelated to the finite field's order. If they are related this is a problem and not secure due to MOV attack. $\endgroup$
    – kelalaka
    Commented Jul 4 at 18:33
  • $\begingroup$ @kelalaka in my case, the suborder is equal to $2736030358979909402780800718157159386076813972158567259200215660948447373041$ which is less than the prime field of $21888242871839275222246405745257275088696311157297823662689037894645226208583$. But I’m interested in other Edwards curves too : not just Babyjub. $\endgroup$ Commented Jul 4 at 18:37
  • $\begingroup$ Some unclear things: what exactly is $\operatorname{targetcurve.Suborder}$? Is it bound to be a prime? Is $P$ chosen on the curve (as stated), or in the subgroup of which $\operatorname{targetcurve.Suborder}$ is the order? Notice that in the former case,$(\operatorname{targetcurve.Suborder}+1)\cdot P$ might not be $P$, making the last criteria strange. Do the last two criteria boil down to $S_1,S_2\in[0,\operatorname{targetcurve.Suborder})$? Isn't "negation of coordinate" intended to be coordinate of the inverse ? $\endgroup$
    – fgrieu
    Commented Jul 7 at 5:21
  • $\begingroup$ @fgrieu Ok : I found the real reason. It appears the curves being used have composite orders and that the Suborder is simply the largest prime factor of the curve’s order. $\endgroup$ Commented Jul 8 at 7:06
  • $\begingroup$ If $n=\operatorname{targetcurve.Suborder}$ is the largest prime factor of the curve's order, then a random point on the curve can't typically have order $n$. Proof: if $(x,y)$ has order that $n$, then $(x,-y)$ has order $2n$, not $n$; hence for a random point on the curve the probability of having order $n$ can't be more than $1/2$. It's actually less than $1/4$. Are you picking $P$ at random in the subgroup of order $n$, rather than on the curve as stated in the question? That would simplify a lot! Then there remains only case 1 in my answer, and the point $(0,1)$ (case 3 with $j=1$). $\endgroup$
    – fgrieu
    Commented Jul 8 at 20:12

2 Answers 2

2
+50
$\begingroup$

Consider an Edwards curve with equation $x^2+y^2=d\,x^2y^2$ in the field $\mathbb F_p$, with prime $p\bmod 4=1$, integer $d$ with $d^{(p-1)/2}\bmod p=p-1$. The group law is $$\bigl(x_1,y_1\bigr)+\bigl(x_2,y_2\bigr)=\bigl((x_1y_2+y_1x_2)/(1+d\,x_1x_2y_1y_2),(y_1y_2-x_1x_2)/(1-d\,x_1x_2y_1y_2)\bigr)$$ We note scalar multiplication $k\cdot P=\underbrace{P+P+\cdots+P}_{k\text{ terms}}$.

The order (number of elements) of that curve can be uniquely written as $h\,n$ with $n$ it's largest prime factor. $n$ is the question's "targetcurve.Suborder". The cofactor $h$ is a multiple of $4$, and $n$ is odd. For curves commonly used in cryptography, $h\in\{4,8\}$ and $n\gg h$.

The only element of order $1$ is the group's unit $\mathcal O=(0,1)$. The only element of order $2$ is $(0,-1)$. The only two elements of order $4$ are $(\pm1,0)$. There are $n-1$ element of order $n$. The opposite of $(x,y)$ is $-(x,y)=(-x,y)$. Define the reflect of $(x,y)$ as $\overline{(x,y)}=(x,-y)$. For all $U$ on the curve, $\overline U$ is on the curve, $\overline{\overline U}=U$, and $U+\overline U=(0,-1)$.


The question asks if given a random point $P$ on the curve, there exists distinct integers $s_1$ and $s_2$ in $[0,n)$ such that $s_1\cdot P$ and $s_2\cdot P$ have the same $x$ coordinate, that is are equal or/and one is the reflect of the other. And if so, asks if we can compute $s_1$ and $s_2$.

That depends on $P$, and more precisely on the order $j$ of $P$, that is the smallest integer $j>0$ with $j\cdot P=\mathcal O$. In practice we can efficiently compute $j$ given the coordinates of $P$, because $j$ divides $h\,n$, leaving few choices.

  1. If $j=n$, then no. That's when $P$ happens to be in the subgroup of order $n$ and is not the unit. This is with probability $(1-1/n)/h$, nearly 25% or 12.5% for curves of interest. Proof by contradiction:

    • If $s_1\cdot P$ and $s_2\cdot P$ were equal, we'd have $(s_2-s_1)\cdot P=\mathcal O$, thus $(s_2-s_1)\bmod n=0$ since $P$ has order $n$, contradicting "distinct integers $s_1$ and $s_2$ in $[0,n)$".
    • If $s_1\cdot P$ was the reflect of $s_2\cdot P$, we'd have $s_1\cdot P+s_2\cdot P=(0,-1)$, thus $(s_1+s_2)\cdot P=(0,-1)$, thus the order of $(0,-1)$ would divide the order of $P$, thus $2$ would divide $n$, a contradiction with $n$ being an odd prime.
  2. If $j=2n$, then yes: any $s_1\in[1,n)$ and $s_2=n-s_1$ will do. That's when $\overline P$ has order $n$. This is with the same probability as above. Proof: $s_1\in[1,n)$ and $s_2=n-s_1$ implies $s_1\ne s_2$ and $s_1,s_2\in[0,n)$, and $s_2\cdot P=(n-s_1)P=n\cdot P-s_1\cdot P=(-1,0)-(s_1\cdot P)$, that is $s_2\cdot P=\overline{s_1\cdot P}$. Hence all requirements are met.

  3. If $j<n$, then yes: any $s_1\in[0,n-j)$ and $s_2=s_1+j$ will do. Argument: we'll have $s_1\cdot P=s_2\cdot P$. Other solutions with $s_2\cdot P=\overline{s_1\cdot P}$ are also possible.

  4. There are other cases, e.g. $j=4n$. I believe the answer is no, at least for $h\in\{4,8\}$ and $n>2h$. Tentative proof:

    • The condition for $s_1\cdot P=s_2\cdot P$ is $s_1\equiv s_2\pmod j$, and that's incompatible with the other constraints on $s_1$ and $s_2$.
    • The condition for $\overline{s_1\cdot P}=s_2\cdot P$ is perhaps $s_1+s_2\equiv j/2\pmod j$, and that's incompatible with the other constraints on $s_1$ and $s_2$.
$\endgroup$
7
  • $\begingroup$ I’m using babyjubjub, so In the specific case the order of the random $P$ is the Suborder of the curve which is a 76 digits number compared to the prime number used for defining the field which is a 255bits number… So I suppose the answer to my question is it can’t be done ? $\endgroup$ Commented Jul 8 at 18:41
  • $\begingroup$ I also have the same problem on a second instance but that uses JubJub (which that time is twisted Edwards) $\endgroup$ Commented Jul 8 at 18:47
  • $\begingroup$ @user2284570: my answer is for Edwards curves, not twisted Edwards curves. But for either kind, the order is always a multiple of 4. Therefore the order of a uniformly random element of the curve is a prime with probability <25%. Therefore the question's newly added "the largest prime factor of the composite curve’s order or the curve order if the curve is a prime which also appears to be the order of any randomly sample points", however I read it, can't be right. $\endgroup$
    – fgrieu
    Commented Jul 9 at 4:52
  • 1
    $\begingroup$ @user2284570: quite possible, but then the part of the problem statement "given a randomly selected point P belonging on a given Edwards curve defined on a prime field" becomes given a randomly selected point P belonging to a large and prime order subgroup of a given Edwards curve defined on a prime field. So in my answer that rules out cases 2 and 4, and within the rare case 3 we only have the even rarest j=1, that is the point (0,1). $\endgroup$
    – fgrieu
    Commented Jul 10 at 6:33
  • 1
    $\begingroup$ @user: the point at infinity belongs to every subgroup, thus if we generate a random point in a group of order targetcurve.Suborder, it mathematically can be the point at infinity. Granted, for curves of practical interest, this is so improbable that it won't ever happen. Perhaps your question really is for a point of order targetcurve.Suborder. If so, we only have my case 1, thus the simple answer is: no there exists no suitable $s_1$, $s_2$. $\endgroup$
    – fgrieu
    Commented Jul 10 at 7:42
2
$\begingroup$

does 2 scalars $S1$ $S2$ exist such as

  1. $packed(S1\cdot P)= packed(S2\cdot P$)

$S1 = S2$ is equivalent to the statement that $S1 - S2$ is an integer multiple of the order of $P$.

  1. $S1 \ne S2$

If that multiple is not zero, this criteria is met.

Both $S1$ $S2$ are >targetcurve.Suborder

I'm not exactly sure what you mean by that, but arbitrarily large $S1, S2$ exist, so it appears to say "yes"

If yes, is it possible to compute such integer pair using a easier method than solving the elliptical curve’s discrete logarithm ?

Not only possible, but easy:

  • Select an arbitrary integer $S1$ that meets your criteria 3

  • Select an arbitrary positive integer $n$ and set $S2 = S1 + nq$ (where $q$ is the order of $P$ - if you don't know that, you can safely use the order of the curve)

And you are done...


Now, with the corrected condition (3), and assuming that the scalars cannot be negative, then it is impossible to have $S1\cdot P = S2 \cdot P$ if $S1 \ne S2$, and $0 < S1, S2 < q$ (where $q$ is the order of $P$).

On the other hand, that's not what you asked for; you asked for $packed(S1\cdot P) = packed(S2\cdot P)$

So, is it possible to have the $packed$ process encode two different points into the same value?

It may be. The most obvious case for this is if $packet$ depends only on the $x$ coordinate of the point. In this case, we have $packed(S1 \cdot P) = packed( (q-S1) \cdot P)$, even though (obviously) $S1 \cdot P \ne (q-S1) \cdot P$.

If this is the case, then producing such a pair $S1, S2$ is easy.

On the other hand, if $packed$ uniquely identifies the encoded point, then what you're asking for is impossible - there will not be any such $S1, S2$ pairs.

$\endgroup$
9
  • $\begingroup$ The suborder of a curve is a curve’s parameter that has value below the prime Group. For example in Babyjubjub, it’s equal to $2736030358979909402780800718157159386076813972158567259200215660948447373041$ which is less than the prime field of $21888242871839275222246405745257275088696311157297823662689037894645226208583$. So it’s not trivial $\endgroup$ Commented Jul 3 at 19:46
  • $\begingroup$ @user2284570: ok, how about $S1 = 1$ and $S2 = 2736030358979909402780800718157159386076813972158567259200215660948447373042$. There, we have $S1\cdot P = S2 \cdot P$ (assuming that $P$ has that 'suborder') $\endgroup$
    – poncho
    Commented Jul 3 at 19:50
  • $\begingroup$ Then the value of S2 is above by 1 than the subOrder instead of below. It’s like the Generator point : the finite field used for the curve is still $21888242871839275222246405745257275088696311157297823662689037894645226208583$ $\endgroup$ Commented Jul 3 at 19:57
  • $\begingroup$ @user2284570: then in your question, you should ask that the both be below the suborder, rather than above it... $\endgroup$
    – poncho
    Commented Jul 3 at 19:58
  • $\begingroup$ That’s right : by point packing I’m meaning keeping only $x$ and dropping $y$. But Edwards curves have the coordinate that can be both negative or positive on $x$ instead of $y$ (the reverse of Weistrass curves). $\endgroup$ Commented Jul 4 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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