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 1


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$ Commented 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$ Commented 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$
    – Fractalice
    Commented Sep 5, 2021 at 21:04

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.