Score:5

Why is Montgomery Ladder fast on Montgomery Curves?

id flag

When I look at the Montgomery Ladder algorithm, I don't find anything that is specific to the Montgomery curve. We are dealing with the points all the time i.e. we are either adding two points or doubling a point. For all I know, those points can belong to any form of elliptic curve. Why is it that in many papers, it is claimed that the Montgomery ladder is fastest on Montgomery curves? What am I missing?

kelalaka avatar
in flag
Because it is side-channel free and has faster arithmetic..
kelalaka avatar
in flag
https://eprint.iacr.org/2017/1081.pdf
kelalaka avatar
in flag
[Montgomery curves and the Montgomery ladder](https://eprint.iacr.org/2017/293.pdf)
kelalaka avatar
in flag
Does this answer your question? [Can Montgomery ladder multiplication be used with secp256k1?](https://crypto.stackexchange.com/questions/56503/can-montgomery-ladder-multiplication-be-used-with-secp256k1)
kelalaka avatar
in flag
Don't you think that the answer in the duplicated question answers your questions?
Gautham Krishna avatar
id flag
@kelalaka From what I understood from your sources, Montgomery curves have easily computable expressions for point addition. What my doubt is, can I use any point addition expression, such as weistrass curve and make use of the constant time computing for side channel resistance.
Score:1
tl flag

Elliptic curves can be represented in different form. The most basic equation, in which every elliptic curve can be represented is the Weierstraß equation:

$$ y^2 = x^3 + ax + b$$

For a Montgomery curve it must be able to be represented in the following form:

$$ (b)y^2 = x^3 + ax^2 + x$$

For every Montgomery curve it is possible to transform its equation to Weierstraß, but not vice versa. Therefore not every elliptic curve is a Montgomery curve.

The Montgomery ladder can only be used by Montgomery curves and can be viewed as a Double and Add-procedure variant with constant time. Such variants and ladders exist for multiple different elliptic curves, but should have different names (e.g. see SafeCurves).

kelalaka avatar
in flag
Not every elliptic curve can be represented with the short Weierstraß equation. This is only valid if $p \neq 2,3$. For a curve to be represented in Montgomery form there must be an element of order 2. All answer for the Op is written in [Squeamish's answer](https://crypto.stackexchange.com/a/56508/18298)
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.