Paper 2020/437

Faster Montgomery and double-add ladders for short Weierstrass curves

Mike Hamburg

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 $5\mathbf{M} + 4\mathbf{S} + 1\mathbf{m} + 8\mathbf{A}$, and 6 field registers. Here $(\mathbf{M},\mathbf{S},\mathbf{m},\mathbf{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 $9\mathbf{M}+5\mathbf{S}+18\mathbf{A}$ per bit. In 2017, Kim et al. improved this for the Montgomery ladder only to $8\mathbf{M}+4\mathbf{S}+12\mathbf{A}+1\mathbf{H}$ per bit using 9 registers, where the $\mathbf{H}$ represents a halving. Hamburg simplified Kim et al.'s formulas to $8\mathbf{M}+4\mathbf{S}+8\mathbf{A}+1\mathbf{H}$ using 6 registers. Here we present improved formulas which compute the Montgomery ladder on short Weierstrass curves using $8\mathbf{M}+3\mathbf{S}+7\mathbf{A}$ per bit, and requiring 6 registers. We also give formulas for the Joye ladder that use $9\mathbf{M}+3\mathbf{S}+7\mathbf{A}$ 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.

Note: The conference version of this paper includes supplementary material, which is not supported by ePrint. The supplementary material is a SAGE prototype implementation of the new Montgomery and Joye ladder formulas with the new zero-avoidance technique. The second version corrects an error in Figure 2; thanks to Ruggero Susella for pointing this out. The third version corrects a typo; thanks to Cyril Hugounenq. The third version also improves the clarity of the additional ladder in the appendix.