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 Answer
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.
-
1$\begingroup$ Thank you very much. This means that, the negative $t$ doesn't have security problem but implementation problem. Is it right? $\endgroup$ Sep 5, 2021 at 6:10
-
$\begingroup$ 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. $\endgroup$ Sep 5, 2021 at 19:06
-
$\begingroup$ 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. $\endgroup$ Sep 5, 2021 at 21:04