Paper 2024/1582

Halving differential additions on Kummer lines

Abstract

We study differential additions formulas on Kummer lines that factorize through a degree $2$ isogeny $\varphi$. We call the resulting formulas half differential additions: from the knowledge of $\varphi (P),\varphi (Q)$ and $P-Q$, the half differential addition allows to recover $P+Q$. We explain how Mumford's theta group theory allows, in any model of Kummer lines, to find a basis of the half differential relations. This involves studying the dimension $2$ isogeny $(P,Q)\mapsto (P+Q,P-Q)$. We then use the half differential addition formulas to build a new type of Montgomery ladder, called the half-ladder, using a time-memory trade-off. On a Montgomery curve with full rational $$-torsion, our half ladder first build a succession of isogeny images $$, which only depends on the base point $$ and not the scalar $$, for a pre-computation cost of $$ by bit. Then we use half doublings and half differential additions to compute any scalar multiplication $$, for a cost of $$ by bit. The total cost is then $$, even when the base point $$ is not normalized. By contrast, the usual Montgomery ladder costs $$ by bit, for a normalized point. In the appendix, we extend our approach to higher dimensional ladders in theta coordinates or twisted theta coordinates. In dimension $$, after a pre-computation step which depends on the base point $$, our half ladder only costs $$, compared to $$ for the standard ladder.

Note: Expand the appendix on dimension 2, give formulas for twisted theta coordinates, typos