Montgomery Ladder for multiple scalars and a single point on Kummer line

68 Views Asked by At

Let $E$ be an elliptic curve over $\mathbb{F}_{q}$ in Montgomery coordinates with points defined on the Kummer line. In this scenario, there are very efficient formulas for computing additions and doublings of points and thus there exist very fast implementations of the Montgomery ladder algorithm using only projective (X:Z)-coordinates, which allow the computation of $(X_{[a]P}:Z_{[a]P})$ from $a$ and $(X_P:Z_P)$; cf. e.g. eprint.iacr.org/2017/212.pdf. In the same source, there is also a two-point ladder allowing the computation of $(X_{[a]P+[b]Q},Z_{[a]P+[b]Q})$ from $(X_P:Z_P)$, $(X_Q:Z_Q)$ and $a$ and $b$. The caveat of the Kummer line approach however is that the points do not longer define a group and that the (pseudo-)addition needs three inputs to be unique, i.e. in order to compute $(X_{P+Q}:Z_{P+Q})$, we need to know $(X_P:Z_P)$, $(X_Q:Z_Q)$ and $(X_{P-Q}:Z_{P-Q})$. So, one has to keep track of differences of the additions performed in the Montgomery ladder.

My question is, if there is an efficient way, of using this or a similar approach to compute many multiples of a single point, i.e. which takes as input a point $P=(X_P:Z_P)$ and a set of scalars $a_1,\dots,a_n$ and returns $(X_{[a_1]P}:Z_{[a_1]P}),\dots,(X_{[a_n]P}:Z_{[a_n]P})$.

Classically (i.e. not on the Kummer line) I see this approach as more or less straightforward, where on would double $Q$ as far as needed, and then add the appropriate multiples together for the different $a_i$. This could be optimized by choosing the order of addition so that parts of multiple $[a_i]P$ would be computed at the same time instead of repeating the additions from scratch for each $a_i$. The problem I see on the Kummer line approach is that we'd need to keep track of many differences to be able to use the pseudo-addition formulas. Especially, if we want to optimize the order of addition we would also need a lot of variables to store these differences, potentially making this approach quite inefficient.

I suppose that there should already be something about this in the literature somewhere, but I haven't been able to find it. Alternatively, maybe there is a good idea, that I'm missing to see how these many variables could be circumvented. Any help is greatly appreciated!