Why the trace of the Elliptic curve should be positive?

mehdi mahdavi oliaiy

1/3/23, 3:39 PM

In https://eprint.iacr.org/2014/130.pdf , has been suggested to select the positive trace. What is the reason for this? What happened if we select the negative trace? Is there any security problem for negative traces? How for Edward curves?

1 + 0

elliptic-curves

Score:4

Crypto

Fractalice

1/4/23, 4:03 PM

The cause I see in the paper is:

To ease implementation, we demand that r < p for all curves, i.e. we choose the curve with positive trace

The prime $p$ is chosen as very close but below a power of 2 (e.g. $2^{384}$). Positive trace ensures that the number of points $r = p+1-t$ is less than $p$ and so does not overflow the chosen power of 2. This avoids e.g. arithmetic mod $2^{384}+\epsilon$ which would waste an extra 32-/64-bit word.

0 + 3

mehdi mahdavi oliaiy

1/5/23, 6:10 AM

Thank you very much. This means that, the negative $t$ doesn't have security problem but implementation problem. Is it right?

mehdi mahdavi oliaiy

1/5/23, 7:06 PM

Your answer is valid for weierstrass curves. It doesn't seem to be valid for Edward curves. Because in these curves, we work on subgroup $r$, not in $4r$ or $8r$. In this case, the bits of the scaler is always less than $p$'s bits.

Fractalice

1/5/23, 9:04 PM

In Sec. 4.3 of the paper you can note that they use an "updated" scalar of the shape $4(ar + k)$ for the purpose of having the same bitlength for all initial scalars $k$. So, while the cofactor is 4, it is not excluded in the computations but actually added explicitly. I guess to force the resulting point to be in the target subgroup.