5
$\begingroup$

I've (finally) implemented the answer to this question in our library, which stated how to transform montgomery curves (and points) to weierstrass curves (and points).

Now, for scalar multiplication, we currently use our Weierstrass code, but want to replace it in the long run. Clearly the Montgomery ladder is the algorithm of choice when it comes to scalar multiplication on Montgomery / Edwards curves. However the ladder usually is given very simplified (always double and add but swap what is doubled and what is added based on the bit in question).

I'm asking for the best, side-channel resistant technique to implement scalar multiplication on Montgomery / Edwards curves.

Note:

  • Same-base pre-computation speed-ups are welcomed.
  • Advanced projective coordinate tricks (tripling and such) are welcomed as long as they don't break side-channel resistance.

My definition of the "best" technique: It should be as fast as possible and as side-channel resistant as possible (side-channel resistance has priority).

Improve this question
$\endgroup$
1
  • $\begingroup$ Note to anybody reading this: ia.cr/2007/286 $\endgroup$
    – SEJPM
    Dec 27, 2015 at 19:40

1 Answer 1

Reset to default
2
$\begingroup$

As you suggest, you can speedup the exponentiation using pre-computed values. However, you will face the following problems:

  • the table with the precomputed values can become rather large, and
  • the table lookup is in general not constant time.

An example of how these problems can be addressed can be found in the Ed25519 implementation of Bernstein et al.; details are discussed on page 13 of their paper. They use a Brickell exponentiation with a standard trick to reduce the size of the table by 50%, and they use constant-time table lookup (where all possible values are loaded from memory and then combined with logical operations).

Note that because the cost of constant time table lookup is proportional to the size of the table, it is not efficient to represent the exponent as a series of larger chunks (e.g. 16bit->65536 elements in the table). It is more efficient to represent the exponent as a series of smaller chunks (e.g. 4bit).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Could you please be so kind and actually link to the topics you're referring to? (which Ed25519 implementation? What is Brickell exponentiation? Is it the fastest exponentiation technique at the moment or did DJB just use it because it's rather simple? Is the implementation DJB uses limited to the Ed25519 curve? What is the "standard trick" you mentioned?) $\endgroup$
    – SEJPM
    Dec 13, 2015 at 21:48

Your Answer

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

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