recent papers

Faster Montgomery and double-add ladders for short Weierstrass curves

Abstract:

The Montgomery ladder and Joye double-add ladder are well-known algorithms for elliptic curve scalar multiplication with a regular structure. The Montgomery ladder is best known for its implementation on Montgomery curves, which requires 5M + 4S + 1m + 8A, and 6 field registers. Here (M, S, m, A) represent respectively field multiplications, squarings, multiplications by a curve constant, and additions or subtractions. This ladder is also complete, meaning that it works on all input points and all scalars.

Many protocols do not use Montgomery curves, but instead use prime-order curves in short Weierstrass form. As of 2011, the fastest formulas for the Montgomery and Joye ladders on these curves each required 9M + 5S + 18A per bit. In 2017, Kim et al. improved this for the Montgomery ladder only to 8M + 4S + 12A + 1H per bit using 9 registers, where the H represents a halving. Hamburg simplified Kim et al.’s formulas to 8M + 4S + 8A + 1H using 6 registers.

Here we present improved formulas which compute the Montgomery ladder on short Weierstrass curves using 8M + 3S + 7A per bit, and requiring 6 registers. We also give formulas for the Joye ladder that use 9M + 3S + 7A per bit, requiring 5 registers. We also show a novel technique to make these ladders complete when the curve order is not divisible by 2 or 3, at a modest increase in cost. Finally, we discuss curve invariants, exceptional points, side-channel protection and how to set up and finish these ladder operations.