Paper 2020/437
Faster Montgomery and doubleadd ladders for short Weierstrass curves
Mike Hamburg
Abstract
The Montgomery ladder and Joye ladder are wellknown 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}$ per scalar bit, and 6 field registers. Here $(\mathbf{M},\mathbf{S},\mathbf{m},\mathbf{A})$ represent respectively field $\mathbf{M}$ultiplications, $\mathbf{S}$quarings, $\mathbf{m}$ultiplications by a curve constant, and $\mathbf{A}$dditions 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 primeorder curves in short Weierstrass form. These have historically been much slower, with ladders costing at least 14 multiplications or squarings per bit: $8\mathbf{M}+6\mathbf{S}+27\mathbf{A}$ for the Montgomery ladder and $8\mathbf{M}+6\mathbf{S}+30\mathbf{A}$ for the Joye ladder. In 2017, Kim et al. improved the Montgomery ladder 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}$ per bit 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. One of our new formulas supports very efficient 4way vectorization. We also discuss curve invariants, exceptional points, sidechannel protection and how to set up and finish these ladder operations. Finally, we 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. A sample implementation of these techniques is given in the supplementary material, also posted at https://github.com/bitwiseshiftleft/ladder_formulas.
Note: CHES 2020 cameraready version, plus one typo fixed (thanks Shiping Cai). Supplementary material is available at https://github.com/bitwiseshiftleft/ladder_formulas.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in TCHES 2020
 Keywords
 Elliptic Curve CryptographyMontgomery LadderJoye LadderShort Weierstrass CurveScalar Multiplication
 Contact author(s)
 mhamburg @ rambus com
 History
 20200720: last of 7 revisions
 20200419: received
 See all versions
 Short URL
 https://ia.cr/2020/437
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/437, author = {Mike Hamburg}, title = {Faster Montgomery and doubleadd ladders for short Weierstrass curves}, howpublished = {Cryptology ePrint Archive, Paper 2020/437}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/437}}, url = {https://eprint.iacr.org/2020/437} }