Optimal same-base exponentiation? 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).
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).