Welcome to the resource topic for 2020/437
Title:
Faster Montgomery and double-add ladders for short Weierstrass curves
Authors: Mike Hamburg
Abstract:The Montgomery ladder and Joye 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} 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 prime-order 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 4-way vectorization. We also discuss curve invariants, exceptional points, side-channel 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 GitHub - bitwiseshiftleft/ladder_formulas: Faster Montgomery and Joye ladder formulas for short Weierstrass elliptic curves.
ePrint: https://eprint.iacr.org/2020/437
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .